Database Reference
In-Depth Information
14
XML-to-XML queries
So far we have only considered queries returning sets of tuples, but queries in practical
XML languages, like XQuery, return documents, i.e., XML trees rather than sets of tuples.
In this chapter we introduce a simple XML-to-XML query language and examine the chal-
lenges it brings to data exchange tasks. It turns out that the semantics of certain answers
has to be reinvented, as there is no natural analog of the intersection of a set of trees. Under
the new semantics, certain answers can be computed owing to the existence of finite bases
for the sets of solutions. While the complexity could be high in general, for some classes
of mappings the problem can be solved efficiently. Specifically, it can be solved efficiently
for the same child-based mappings that led to efficient algorithms for building solutions
and answering tuple queries.
14.1 XML-to-XML query language
TQL
As in many functional and database query languages, including FLWR (for-let-where-
return) expressions of XQuery, the key construct of the language we use is a compre-
hension. It is of the form
for
π
(
x
)
return
q
(
x
)
where
(
x
) is a pattern and
q
(
x
) defines a forest. We shall formally define both the class
of patterns we use and forest queries below. For now, we explain the class of queries
informally, and give a few examples.
The semantics of the comprehension above is this: given an input tree
T
, for each
tuple
a
such that
T
π
|
(
a
), we construct the forest
q
(
a
) and take the union of all
such forests as the answer to the query. To make a forest into a tree, we just put a
common root above it. Forest expressions can involve subqueries as well, for example
for
π(
x
)
return
for
π
(
x
,
z
)
return
q
(
x
,
z
)
. Then, for each π(
a
) true in an input
T
,
we construct the forest
for
π
(
a
,
z
)
return
q
(
a
,
z
) and take the union of these as the
answer to the query over
T
.
=
π
Example 14.1 Consider the tree
T
countries
shown in
Figure 10.1
, representing a set of
countries with a list of subelements storing their successive rulers.
