Database Reference
In-Depth Information
Lemma 13.14
Let D be a nested-relational DTD, and let
π
be a tree pattern.
1. For each T
|
=
D and for all a
T
|
=
π
(
a
)
iff
T
|
= mrg
D
π
(
a
)
.
2. If
π
is satisfiable with respect to D, then
mrg
D
(
π
)
admits an injective homomorphism
into a tree conforming to D.
The property we postulated follows.
Lemma 13.15
Let
ϕ
be a pattern satisfiable with respect to a nested-relational DTD D.
•
For every T
|
=
D and every a
T
|
=
ϕ
(
a
)
iff
T
|
= mrg
D
(cpl
D
ϕ
)(
a
,
c
)
for some c
.
•
mrg
D
(cpl
D
ϕ
)
viewed as a tree conforms to D.
Let us now return to the construction of a universal solution. Recall the pattern
δ
S
,M
combining all target requirements. Define
η
S
,M
= mrg
D
t
(cpl
D
t
δ
S
,M
)
.
Without loss of generality, we can assume that
η
S
,M
is a pure tree pattern. Indeed, if an
equality says that
v
=
t
, replace each occurrence of
v
with
t
, and remove this equality. If
at some point we obtain an equality between two different constants, the pattern is not
satisfiable and can be replaced with
⊥
.
from
SM
nr
(
Lemma 13.16
For every mapping
M
↓
,
=)
and source tree S, the pattern
η
S
,M
viewed as a tree is a universal solution (unless
η
S
,M
=
⊥
).
Proof
Suppose that
η
S
,M
viewed as a tree, with variables inter-
preted as new data values (nulls). Obviously
U
η
S
,M
=
⊥
and let
U
be
|
=
η
S
,M
.By
Lemma 13.15
,
U
|
=
δ
S
,M
and
U
|
=
D
s
.Using
Lemma 12.1
we conclude that
U
is a solution.
To show that it is universal, take some solution
T
.By
Lemma 13.15
,
T
|
=
η
S
,M
(
z
) and
so there exists a homomorphism from
η
S
,M
are isomorphic, this
gives a homomorphism from
U
to
T
, and proves universality of
U
.
η
S
,M
to
T
.As
U
and
Now we can present the polynomial-time algorithm. It works as follows:
•
first, it computes
η
S
,M
;
•
then it evaluates
Q
over
η
S
,M
;and
•
finally, it removes tuples containing nulls from the result.
Its correctness is an immediate consequence of
Lemmas 13.16
and
13.12
.
