Database Reference
In-Depth Information
We have seen that if we stick to child-based mappings, we cannot extend the query lan-
guage. But perhaps we can find a more suitable class of mappings? Observe that the map-
ping in the proof above is very imprecise: the queries use horizontal navigation, and yet
the mapping does not specify it at all. It might seem a good idea to demand more preci-
sion, for instance, by allowing only a [ b
b ], but not a [ b , c ]. Unfortunately, the
reduction above can be modified to obtain hardness for such mappings too (see Exercise
16.3 ). Sibling order in queries inevitably leads to intractability.
In summary, if certain answers are to be tractable, the following conditions must be
imposed:
c ] or a [ c
the schemas should be simple (nested-relational),
st-tgds should not use descendant, wildcard, nor next-sibling, and
queries should not use horizontal navigation nor inequality.
13.4 Tractable query answering
The conclusions of the previous section indicate that, in order to have a chance to achieve
tractable query answering in XML data exchange, we need to impose some restrictions:
mappings should come from the class SM nr (
, =),and
queries should come from the class UCTQ(
, =).
We now show that these restrictions indeed guarantee tractability of query answering.
SM nr (
Theorem 13.9
For each mapping
M ∈
, =) and query Q
UCTQ(
, =) ,the
problem CERTAIN M ( Q ) is solvable in polynomial time.
In the rest of the section we describe the polynomial-time algorithm. The approach, just
like in the relational case, is via universal solutions.
Recall that in data exchange the set of values that may appear in databases/documents
is split into C ONST , the set of constants (data values appearing in source documents), and
V AR , the set of nulls (data values invented to fill in unspecified attributes on the target
side).
In order to carry over the concept of universal solutions to the XML setting, we need
the notion of homomorphisms between XML trees in which we do not care about the
horizontal axes, since the mappings do not use them.
Definition 13.10 (Unordered homomorphism) For two XML trees
S =( U S ,
S ,
S , lab S , (
S
a ) a Att )
T =( U T ,
T ,
T , lab T , (
T
a ) a Att ) ,
ρ
and
ρ
T is a function mapping U S
to U T and C ONST
an unordered homomorphism h : S
V AR
to C ONST
V AR such that
h preserves the root, i.e., h (
ε
)=
ε
;
S w then h ( v )
S h ( w );
h preserves the child relation, i.e., if v
Search WWH ::




Custom Search