Database Reference
In-Depth Information
2 Our Solution
2.1 Basic Idea
When evaluating XQuery queries over documents given in a compressed or uncom-
pressed XML representation, there are only few parts of the evaluation process that
are specific for the chosen XML representation, whereas most parts are generic and
can be implemented by our approach directly and independently of the chosen XML
representation.
The specific XML representation has to provide the evaluation of absolute and rel-
ative XPath expressions within the source document. Furthermore, the specific XML
representation has to provide inserting new elements as the first-child or as the next-
sibling of the current context node, and copying sub-trees from the source document
to the target document.
But even these tasks contain generic aspects. The evaluation of XPath expressions
can be reduced to navigation via the basic binary axes first-child, next-sibling, and
end-of-parent and the retrieval of the label of the current context node. Copying sub-
trees can be reduced to navigation via the same basic binary axes within the source
document and inserting new elements as first-child or next-sibling into the target
document. Nevertheless, our evaluation has shown that our approach runs faster, if
XPath evaluation and copying sub-trees is optimized according to the specific repre-
sentation instead of using the generic solution via navigation and updates.
To execute a transformation instruction, we parse the transformation instruction
line by line and interpret the lines as follows: Whenever there is a call to an element
constructor (as e.g. <mainland>), we add the constructed element to the target docu-
ment as first-child or as next-sibling of the current context element. Whenever there is
a for-statement FS, we evaluate the absolute or relative XPath expression of FS and
execute the content of FS for each result of the XPath expression. Whenever there is a
let-statement LS, we evaluate the absolute or relative XPath expression of LS, conca-
tenate the results of the XPath expression to a single sequence and bind the whole
sequence to the variable given within LS. In order to minimize the number of passes
through the source document, we do not evaluate the XPath expressions of the for-
and let-statements line by line as they appear in the transformation instruction, but we
first collect all XPath expressions and evaluate all of them in parallel considering the
interdependencies within the queries. Whenever there is a call to a variable $v within
the return-statement, i.e., whenever it is required to output the content of $v to the
target document, we copy the content of $v from the source document to the target
document.
Most tasks that have to be performed in order to transform a source document ac-
cording to an XQuery transformation into a target document are independent of the
XML representation used and can be solved generically. But in order to be transform-
able via our approach, an XML representation has to provide either the navigation via
first-child, next-sibling and end-of-parent, or - in order to be sure that the transforma-
tion requires 2 passes only - it has to provide the evaluation of several absolute and
relative XPath expressions in parallel. If an XML representation does only allow the
sequential evaluation of several XPath expressions, sequential evaluation can be used
as well, but then the transformation requires more than just 2 passes. Furthermore, the
