Database Reference
In-Depth Information
the few exceptions have at least one of the following weaknesses. First, XQueC [2]
suffers from a weaker XML compression and is designed to output uncompressed
XML only. Second, for XQuery evaluation on top of Bisimulation [3], the transforma-
tion of XQuery is limited to a small XQuery subset that only supports XPath
expressions consisting of child-axis location steps only. In comparison, we propose a
generic approach to transform compressed XML documents that is applicable to vari-
ous XML compression techniques that support a basic set of navigation and update
operations on compressed XML data. Furthermore, our transformation on compressed
XML outperforms the indirect approach via decompression, XQuery transformation
and recompression and works as efficiently as other XQuery evaluators that transform
uncompressed XML.
1.2 Contributions
In this paper, we present a generic approach to transforming compressed or uncom-
pressed XML representations that supports a subset of XQuery (c.f. Section 1.3) and
that combines the following properties:
•
It allows transforming each XML representation, and especially each compressed
XML representation, that supports the basic binary navigation operations 'naviga-
tion to the first-child', 'navigation to the next-sibling', and 'navigation to the end-
tag of the parent', and supports the basic update operations 'appending a first-child
to the current end of the document', 'appending a next-sibling to the current end of
the document' and 'closing the current node', i.e., adding an end tag and continu-
ing with the next-sibling or the end-tag of the parent node.
•
Whenever an XML compression technique supports these basic functionalities
directly on a compressed representation c(X) of an XML document X, our ap-
proach allows transforming c(X) into another compressed XML file c(X') corres-
ponding to the new XML structure X' of the transformed XML document X.
Whenever an XML representation not only supports these basic functionalities, but
supports, for example, evaluating XPath queries efficiently or copying compressed
sub-trees from a compressed source document into a compressed target document
without having to decompress the sub-tree, these capabilities are used by our ap-
proach instead. Unnecessary decompression and recompression of the compressed
document is avoided.
•
We have implemented and evaluated our transformation approach for uncompressed
XML in form of a SAX-based XML representation and for compressed XML in form
of Succinct compression [4]. These are examples of XML representations that can be
combined with our approach. All other XML representations that fulfill the above
given requirements can work with our approach as well.
1.3 Query Language
The transformation language used in our approach is a subset of XQuery [1]. It can
be defined by the following EBNF grammar, where
XPATH
is a relative
coreXPath expression containing only the forward axes self, attribute, text, child,
descendant, descendant-or-self, and following-sibling, and where
NAME
,
VARIABLE
,
