Adding Updates to XQuery: Semantics, Optimization, and Static Analysis
Michael Benedikt, Angela Bonifati, Sergio Flesca, Avinash Vyas · 2005
The need to extend XQuery to support updates has been recognized both in the research and the stan-dards community. Several language proposals and prototype implementations have been put forward, and update language requirements are being defined within the W3C. Most proposals center around the use of update primitives applied to XQuery expres-sions, along with a variant of the FLWR loop con-struct binding variables within a block of basic up-date statements. In defining a precise semantics for such statements a number of issues arise: one must decide how conflicts among updates are to be re-solved, and how query evaluation interacts with up-date application. In this work we provide a frame-work for defining alternative semantics for updates, and identify within this space what is (thus far) the consensus choice: that semantics involves a two-stage execution process, in which query evaluation is performed first, after which a generated sequence of concrete updates is applied in a fixed order deter-mined by query output. This results in a clean de-terministic semantics which facilitates analysis. A drawback is that the evaluation of the language can be inefficient. One would prefer to perform updates eagerly before further evaluation, or to re-order the update operations. We focus on an optimization of the “standard semantics”, in which updates are per-formed as soon as they are generated. We present a static analysis for determining when this optimiza-tion can be exploited. Experiments on the implemen-tation of this analysis, implemented on top of Galax, show that the overhead is minimal. 1