Database Reference
In-Depth Information
if T is a universal solution for T under
, then its inlining I NL D OC ( T , D t ) is a solu-
M
tion for I NL D OC ( T , D S ) under I NL M AP (
M
) ;
for every universal solution T for I NL D OC ( T , D s ) under I NL M AP (
M
) there exists an
universal solution T for T under
such that I NL D OC ( T , D t ) is contained in T .
M
15.4 Answering XML queries using relational data exchange
Recall that for conjunctive tree queries that only use the child-relation (i.e., queries from
the class CTQ(
, =), and for mappings that use nested-relational DTDs and child-relation
only in patterns (i.e., mappings from the class SM nr (
, =)), computing certain answers for
a given source tree S is solvable in polynomial time. Thus, for the classes of mappings and
queries we consider, there is no complexity mismatch between XML data exchange and
relational data exchange, restricted to acyclic schemas. Indeed, translations shown here are
correct with respect to query answering: that is, our Requirement 5 is satisfied.
Σ st ) be an XML schema mapping in SM nr (
Proposition 15.11
Let
M
=( D s , D t ,
, =) ,
and Q a conjunctive tree query in CTQ(
, =) . Then, for every XML tree S that conforms to
D s , the certain answers of Q for S under
M
and the certain answers of I NL Q UERY ( Q , D t )
for I NL D OC ( S , D s ) over I NL M AP (
M
) coincide:
certain M ( Q , S )= certain I NL M AP ( M ) (I NL Q UERY ( Q , D t ) , I NL D OC ( S , D s )) .
Proof Assume first that a tuple t belongs to the certain answers of a query Q over
atree S under
. Then, clearly, t belongs to the evaluation of Q over the canon-
ical solution C AN S OL ( S ) for S (which,
M
in this case,
is guaranteed to exist under
). Then, by Proposition 15.9 , t belongs to the evaluation of I NL Q UERY ( Q , D t ) over
I NL D OC (C AN S OL ( S ) , D t ). Moreover, from Proposition 15.10 ,I NL D OC (C AN S OL ( S ) , D t )
is an I NL M AP (
M
)-universal solution for I NL D OC ( T , D s ). Hence t belongs to the certain
answers of I NL Q UERY ( Q , D t ) over I NL D OC ( S , D s ) under
M
M
. The other direction is sym-
metric.
The result of Proposition 15.11 , combined with the standard procedure for evaluating
conjunctive queries in relational data exchange, also gives us an algorithm for computing
certain answers.
Combining correctness propositions, we can finally state the main correctness result.
in SM nr (
Theorem 15.12
For XML schema mappings
M
, =) and conjunctive tree
queries Q in CTQ(
, =) , algorithm I NL C ERT A NSW (
M
, Q ) correctly computes certain
answers certain M ( Q , S ) for source documents S.
The algorithm is illustrated in Figure 15.4 , fulfilling our desiderata first outlined in Fig-
ure 15.1 . It is not limited to queries considered here, and can be extended even to some
XML-to-XML queries studied in the previous chapter; we refer the reader to the biblio-
graphic comments for additional information.
Search WWH ::




Custom Search