DDO-Free XQuery

XQuery has an order-sensitive semantics in the sense that it requires nodes to be sorted in document order without duplicates (or in Distinct Document Order, DDO for short). This paper shows that for a given XQuery expression and a nested-relational DTD, the input expression can be transformed into an expression that can be evaluated without—potentially costly—ordering operations even if the input query requires its result to be in DDO.

To this end, we propose an XQuery transformation algorithm that consists of simple rewriting rules. The basic idea is inspired by a generate-and-test approach as used in general computational frameworks. We apply this approach when constructing the transformed expression: first, a skeleton query is prepared. This skeleton query can be evaluated without DDO, but it has the ability to return all nodes in DDO for all XML documents that conform to the input DTD. Second, an output expression is generated by injecting conditions extracted from the input expression into the skeleton query. The key to performing both the extraction and injection of conditions in a systematic way is to utilize XQuery transformations that preserve equivalence up-to-DDO.