Database Reference
In-Depth Information
Completion
simply extends the pattern with all missing labels and thus makes it com-
plete. As the patterns use only
and =, and DTDs are nested-relational, this can be done
in a unique way. For a DTD
D
the operation cpl
D
on pure patterns is defined inductively as
cpl
D
σ
↓
(
t
)
cpl
D
π
1
,
cpl
D
π
2
,...,
cpl
D
π
k
,
cpl
D
τ
1
(
z
1
)
,
cpl
D
τ
2
(
z
2
)
,...,
cpl
D
τ
m
(
z
m
)
,
π
k
]
=
(
t
)[
π
1
,
π
2
,...,
σ
τ
m
are the missing labels and
z
1
,
z
2
,...,
z
m
are tuples of fresh variables. (If
t
is
where
τ
1
,...,
has
r
attributes, replace
t
with a tuple of fresh variables
z
1
,
z
2
,...,
z
r
.) Since
D
is nonrecursive, the operation terminates and returns a pattern at most single-exponential
in the size of
D
. Note that different occurrences of
empty and
σ
τ
are completed with different variables.
We write cpl
D
(
.
It is fairly easy to see that the completed formula is equivalent to the original one.
π
∧
α
) for cpl
D
(
π
)
∧
α
Lemma 13.13
Let D be a nested-relational DTD, and let
π
be a tree pattern. For each
T
|
=
D and each a
T
|
=
π
(
a
)
iff
T
|
= cpl
D
π
(
a
,
c
)
for some c
.
The aim of
merging
is to merge all subpatterns that are always mapped to the same node
in trees conforming to the given DTD. More precisely, for a given
π
it produces a pattern
π
such that
π
over trees conforming to
D
,
•
π
admits an injective homomorphism into a tree conforming to
D
(or is not satisfiable).
•
π
is equivalent to
) is built inductively, with new
equalities (induced by merging nodes) added to the global set
E
along the way. If at some
point we arrive at an inconsistency between
Fix a nested-relational DTD
D
. The pattern mrg
D
(
π
π
and
D
, we output an unsatisfiable pattern
⊥
.
In the beginning the set
E
is empty.
To obtain mrg
D
(
σ
[
π
1
,...,
π
k
]) proceed as follows.
(
t
)[
1. Return
⊥
whenever
π
i
=
τ
λ
] for some
π
i
and a label
τ
not occurring in the produc-
tion for
σ
.
2. For each
τ
such that
σ
→
...
τ
...
or
σ
→
...
τ
?
...
merge all the
π
i
's starting with
τ
:
(
t
)[
(
t
j
)[
2a. remove all
π
i
's of the form
τ
λ
],say,
π
i
j
=
τ
λ
j
] for 1
≤
j
≤
m
,
(
t
1
)[
2b. add a single pattern mrg
D
(
τ
λ
1
,...,
λ
m
]),
2c. add to
E
equalities
t
1
=
t
j
for 2
m
(where
s
=
t
stands for the conjunction of
≤
j
≤
s
1
=
t
1
,
s
2
=
t
2
,...,
s
d
=
t
d
).
3. Replace all the remaining
π
i
).
4. Return the obtained pattern and the equalities from
E
.
π
i
with mrg
D
(
For a pattern with equalities
.
Again, proving that the new formula satisfies the required properties is straightforward.
π
∧
α
,letmrg
D
(
π
∧
α
)=mrg
D
(
π
)
∧
α
