Database Reference
In-Depth Information
⊕
=
K
K
K
a
a
a
b
a
b
a
a
S
1
S
2
T
1
T
2
T
2
T
1
S
1
S
2
Figure 12.2 The operation
⊕
on trees from
L
(
K
)
Definition 12.11 Let
K
be a
D
-kind for some nested-relational DTD
D
. For trees
T
and
S
in
L
(
K
),define
T
L
(
K
) as the tree obtained by substituting at each port
u
in
K
the
forest
S
u
+
T
u
. Since the operation is associative, we will skip the parentheses and write
T
1
⊕
⊕
S
∈
T
2
⊕···⊕
T
n
for
T
1
,
T
2
,...,
T
n
∈
L
(
K
).
An illustration of the operation
is given in
Figure 12.2
.
We now need to check that if we start with a set of partial solutions for all valuations of
target patterns, the operation
⊕
⊕
gives a complete solution. We prove a more general fact.
Lemma 12.12
Fo r a l l T
1
,
T
2
,...,
T
n
∈
L
(
K
)
and every
π
∈
Π
(
⇓
,
∼
)
,
T
1
⊕
T
2
⊕···⊕
T
n
|
=
π
(
a
)
whenever
T
i
|
=
π
(
a
)
for some i
.
Proof
For all
i
,
T
1
⊕
T
n
containing the root. In particular, there exists an unordered homomorphism from
T
i
to
T
1
⊕
T
2
⊕···⊕
T
n
subsumes
T
i
, i.e.,
T
i
is a subtree of
T
1
⊕
T
2
⊕···⊕
T
2
⊕···⊕
T
n
. This means that for all
π
∈
Π
(
⇓
,
∼
), whenever
T
i
|
=
π
(
a
), it also holds
that
T
1
⊕
T
2
⊕···⊕
T
n
|
=
π
(
a
).
Now that we have all the ingredients ready, it remains to put them together. This is done
by
Algorithm 12.2
that shows how to build solutions for mappings in SM
nr
(
⇓
,
∼
).
SM
nr
(
Theorem12.13
For each mapping
)
,
Algorithm 12.2
computes a solution
for a source tree T (or determines that it does not exist) in polynomial time.
M ∈
⇓
,
∼
Proof
Let
D
t
be the target schema of
.By
equation (12.2)
, if there is a solution for
T
,
it agrees with a
D
t
-kind
K
. The size of
K
is at most
=
M
D
t
D
t
. The kind only needs to
use data values from
T
and nulls from a set
{⊥
1
,
⊥
2
,...,
⊥
}⊆{⊥
1
,
⊥
2
,...,
⊥
n
}
. Hence,
we can check such kinds
K
one by one, looking for a solution in
L
(
K
).
For each
δ
(
z
)
∈
Δ
T
,M
we need to find a tree
S
δ
∈
L
(
K
) and a tuple
c
such that
S
|
=
δ
(
c
).
The branching of
S
δ
can be bounded by
: one can safely remove each child
v
that is not enforced by
D
t
and the subtree rooted at
v
has empty intersection with the image
of the homomorphism witnessing that
S
δ
|
D
t
+
δ
=
δ
. Furthermore, arguing like in
Lemma 12.4
