Database Reference
In-Depth Information
a solution with respect to the composition of
M 12 and
M 23 , it should also not satisfy
ϕ
.
This explains why all such dependencies are included into
Σ 13 (line 4).
Another aim of the preprocessing phase is to include in the target patterns all information
that can be inferred from the schema D 2 . For instance, if D 2 declares that each a -labeled
node has a b -labeled child, we include this information into a target pattern r / a ( x ) by
replacing it with r / a ( x ) / b ( y ),where y is a fresh variable. In the relational case, there is no
information to infer, so this step is not needed. In general, we use the operation cpl D 2 from
Chapter 13 . The operationwas designed for patterns without function symbols, but it can be
directly applied to patterns with function symbols. The obtained pattern will often contain
new variables (e.g., y in the example above). We eliminate them by standard Skolemization,
replacing variables with fresh function symbols. As in Lemma 13.13 , which generalizes
naturally, the resulting set of st-tgds is equivalent to the original. Thus, without loss of
generality we can assume that the algorithm starts with
Σ 12 = Σ 12 . In particular, we assume
that no new function symbols are introduced by Algorithm 19.2 .
The operation cpl D 2 only adds information about the nodes that are enforced by D 2 ,
but are not mentioned in the target side patterns of
M 12 . Another kind of information that
one can infer from D 2 is that some nodes of the pattern are always matched in the same
node of the tree. For instance, if D 2 says that the root has exactly one a -labeled child, then
r [ a ( x ) / b , a ( y ) / c ] can be replaced with a more informative pattern r / a ( x )[ b , c ]
x = y .This
kind of information is extracted by the merge operation, mrg D 2 ,definedin Chapter 13 .Just
like cpl D 2 , the merge operation can be applied to patterns with function symbols without
any modifications, and Lemmas 13.14 and 13.15 generalize in a straightforward way. By
defining
ρ η
as mrg D 2 (
ψ 1 ∧···∧ ψ k ) inline8,weensurethat
ρ η
expresses all the
information that can be extracted from
ψ 1 ∧···∧ ψ k and D 2 .
Note that in the example above not only is the structure of the pattern changed, but
also a new equality x = y is introduced. This equality, just like any equality present in
ψ 1 ∧···∧ ψ k , imposes a restriction on source instances that have solutions, and needs to
be included in the composition. It is done in line 9. Such new equalities enforced by the
intermediate schema can occur even if the original patterns do not use equalities. This
shows that without equality on the target side, XML schema mappings are not closed by
composition.
In the following two lemmas we show formally that Algorithm 19.2 is correct.
Lemma 19.22
If ( T 1 , T 2 )
M 12
and ( T 2 , T 3 )
M 23
with a witnessing valuation of
function symbols f, then ( T 1 , T 3 )
with the same witnessing valuation f.
M 13
Proof Pick a constraint from
Σ 13 . Suppose first that it is of the form
ϕ −→ ⊥
,
then it is also present in
Σ 12 . Hence, T 1 does not satisfy
ϕ
for any valuation, and so ( T 1 , T 3 )
satisfies the constraint.
Search WWH ::




Custom Search