This paper investigates a class of transform queries proposed by Xquery Update [6]. A transform query is defined in terms of XML update syntax. When posed on an XML tree T, it returns another XML tree that would be produced by executing its embedded update on T, without destructive impact on T. Transform queries support a variety of applications including XML hypothetical queries, the simulation of updates on virtual views, and the enforcement of XML access control. In light of the wide-range of applications for transform queries, we develop automaton-based techniques for efficiently evaluating transform queries and for computing their compositions with user queries in standard Xquery. We provide (a) three algorithms to implement transform queries without change to existing Xquery processors, (b) a linear-time algorithm, based on a seamless integration of automaton execution and SAX parsing, to evaluate transform queries on large XML documents that are diffi- cult to handle by existing Xquery engines, and (c ) an algorithm to rewrite the composition of user queries and transform queries into a single efficient query in standard Xquery. We also present experimental results comparing the efficiency of our evaluation and composition algorithms for transform queries.
展开▼
