From XML Updates to Queries

This paper investigates rewriting of XML updates into queries. That is, given an update u over an XML document T, we derive a query QC_u, referred to as a complement query of u, such that QC_u(T) returns the same document as produced by updating T in place with u. With this ability one can define a (virtual) view in terms of updates while avoiding the destructive impact of updates. Furthermore, this allows us to directly compose queries with updates. The need for this is evident in, e.g. , XML security, integration and update testing. We provide two alternative algorithms for computing complement queries from a class of XML updates commonly found in practice. Moreover, we develop novel algorithms for computing a single complement query from a sequence of updates, based on incremental computation. We show that complement queries computed by our algorithms can be evaluated in time linear in the size of the XML document. These provide the first efficient algorithms for rewriting XML updates into queries. We also present experimental results comparing the efficiency of the rewritten queries produced by our algorithms.