Database Reference
In-Depth Information
h
preserves the labeling, i.e.,
lab
S
(
v
)=
lab
T
(
h
(
v
));
•
•
h
is the identity on C
ONST
, i.e.,
h
(
c
)=
c
for all
c
∈
C
ONST
;
a
(
h
(
v
)) =
h
(
a
(
v
)) for all
a
if
v
stores
t
then
h
(
v
) stores
h
(
t
), i.e.,
•
ρ
ρ
∈
Att
.
Now that we have the notion of homomorphism, universal solutions are defined just like
in the relational case.
Definition 13.11 (Unordered universal solution) A tree
U
is an
unordered universal so-
lution
for a tree
S
under a mapping
if it is a solution for
S
, and for each other solution
T
there is an unordered homomorphism from
U
to
T
.
M
The following lemma carries over from the relational case.
Lemma 13.12
If U is an unordered universal solution for a source tree S under a map-
ping
M
, and Q
∈
UCTQ(
⇓
,
=)
, then for each tuple a of values in
C
ONST
a
∈
certain
M
(
Q
,
S
)
⇐⇒
a
∈
Q
(
U
)
.
Proof
One implication is obvious, as
U
is a solution itself. Let us focus on the other one.
Take
a
∈
Q
(
U
).Let
π
(
x
,
y
) be a pattern such that
Q
=
∃
y
π
(
x
,
y
).Then
U
|
=
π
(
a
,
y
).Let
h
:
π
→
U
be the witnessing homomorphism. We need to show that
T
|
=
π
(
a
,
y
) for each
solution
T
.By
Definition 13.11
, there exists a homomorphism
g
:
U
→
T
.Since
π
uses
no horizontal axes, the composition
h
◦
g
is a homomorphism from
π
to
T
that witnesses
T
|
=
π
(
a
,
y
).
Fix a mapping
M
=(
D
s
,
D
t
,
Σ
st
) and a source tree
S
. Recall the set of target require-
ments defined as
(
a
,
z
)
ϕ
(
a
,
b
)
Δ
S
,M
=
{
ψ
(
x
,
y
)
→∃
z
ψ
(
x
,
z
)
∈
Σ
st
and
S
|
=
ϕ
}
with variables renamed so that none is used in more than one pattern; the pattern
δ
S
,M
is
obtained by taking the conjunction of all patterns from the modified
Δ
S
,M
.By
Lemma 12.1
,
atree
T
conforming to the target schema is a solution for
S
if and only if
T
|
=
δ
S
,M
.This
SM
nr
(
means that constructing a universal solution for
S
under the mapping
M ∈
↓
,
=)
amounts to finding a “universal” tree satisfying a child-only pattern
(with equalities) and
conforming to a nested-relational DTD
D
. To this end we construct a pattern
π
π
such that
π
,
•
for every
T
,if
T
|
=
D
then
T
|
=
π
iff
T
|
=
•
π
viewed as a tree conforms to
D
.
We construct this pattern by means of two operations: completion and merging.
We say that a pattern
is
complete
with respect to a nested relational DTD
D
if each
of its nodes has all the children required by the DTD. More precisely, a label
ϕ
τ
is
missing
(
t
)[
+
, but no
in a subpattern
σ
π
1
,
π
2
,...,
π
k
] if
τ
occurs in the production for
σ
as
τ
or
τ
formula of the form
τ
[
λ
] occurs among the
π
i
s. A pattern is complete if no label is missing
in its subpatterns.
