Database Reference
In-Depth Information
representation has to provide the capability to insert a new element as the first-child
or the next-sibling of the current context element, and in addition it might optionally
provide the capability to copy whole sub-trees from a source to a target document.
In the remainder of this section, we first explain for each task, i.e. XPath evaluation
and copying sub-trees from the source document to the target document, how this task
is solved in the generic part, and then discuss for two XML representations - uncom-
pressed XML on the one hand and Succinct Compression [4] on the other hand - how
the representation specific part is solved for these XML representations.
2.2 XPath Evaluation
Generic XPath Evaluation.
We follow the idea of [5] and use an automata-based
approach to XPath evaluation. We reduce the set of axes to the basic binary axes first-
child, next-sibling, end-of-parent, and self::label, where label is the label of any XML
element or '*'. We assume that each XML representation produces binary XML
events of the form first-child, next-sibling, end-of-parent or self::label when passing
through the XML representation. That is, when we navigate from the current context
node to its first-child that carries the label 'lab', this sends two events to the
automaton: a first-child::* event followed by the event self::lab.
For each XPath forward axis, we provide an atomic automaton using the basic bi-
nary axes. Fig. 2 shows the atomic XPath automata for the location steps (a) child::e
and (b) descendant::f and (c) a combined automaton for the XPath expression
/child::e/descendant::f .
Fig. 2.
XPath automata for (a) child::e (b) descendant::f, and (c) /child::e/descendant::f
According to the order of the location steps within the XPath expression XP, the
atomic automata for all location steps are concatenated to form the XPath automaton
of the whole XPath expression XP. As these automata only contain forward axes, they
allow evaluating the XPath expression within a single pass through the document.
More details on the automata-based XPath evaluation are described in [5].
In contrast to [5], which handles the evaluation of absolute queries only, we have
to handle absolute and relative XPath expressions. In order to evaluate all XPath ex-
pressions XPA1, …, XPAn, XPR1, …, XPRm occurring in the given XQuery expres-
sion, where each XPAi is an absolute XPath expression and each XPRj is a relative
XPath expression, we generate one XPath automaton for each absolute or relative
XPath expression XP. When parsing of the XML representation starts, only the auto-
mata for the absolute expressions XPA1, …, XPAn are active and consume the navi-
gation events of the form first-child, next-sibling, self::label, and end-of-parent that
