Database Reference
In-Depth Information
13
Answering tuple queries
The ultimate goal of data exchange is to answer queries over the target data in a way
consistent with the source data. In this chapter we focus on queries that return sets of
tuples of data values. The reason for this restriction is twofold:
•
first, for such queries the notion of certain answers is easy to define; and
•
second, already for these queries we shall be able to identify features that need to be
ruled out in order to ensure tractability of query answering.
We deal with a query language based on tree patterns, as it forms a natural analog of
(unions of) conjunctive queries. We show that the problem of finding certain answers is
in
CO
NP, just like for conjunctive queries in the relational case. We then identify several
features specific to XML, such as disjunction in DTDs or the horizontal order, that make
the query answering problem intractable. Finally, we give a polynomial query answering
algorithm that computes certain answers for unions of conjunctive queries that only use
vertical navigation, restricted to schema mappings with nested-relational DTDs.
13.1 The query answering problem
Just like in the relational case, we study conjunctive queries and their unions. As we have
learned, it is convenient to work with tree patterns, which have very similar expressivity to
conjunctive queries. Thus, for querying XML documents we use the same language as for
the dependencies: tree patterns with equalities and inequalities, to capture the analog of
relational conjunctive queries (with inequalities). And, of course, we allow projection.
That is, a query
Q
is an expression of the form
∃
y
π
(
x
,
y
)
,
where π
is a (generalized) tree pattern satisfying the safety condition, i.e., each variable
used in
is connected by a sequence of equalities to a variable used in the pure pattern
underlying
π
π
. The semantics is defined in the standard way:
(
a
,
b
) for some tuple
b
of attribute values
.
T
|
=
∃
y
π
(
a
,
y
)
⇔
T
|
=
π
