Database Reference
In-Depth Information
The crucial property of a basis is that it preserves max-descriptions.
Lemma 14.13
If
B
is a basis of
T
, then the sets of max-descriptions of
T
and
B
coincide.
Proof
Take a max-description
π
of
B
. Since it can be mapped into every pattern from
and
ϕ
∈B
B
Mod(
ϕ
), it can also be mapped into every tree from
T
.Now,takeapattern
π
that can be mapped into every tree from
T
. We need to show that it can be mapped
π
can be mapped into every pattern from
into
π
.As
B ⊆ T
,
B
. By the properties of
π
can be mapped into
max-descriptions,
π
.
Conversely, assume that
π
is a max-description of
T
. As it can be mapped into every
pattern of
T
, it can also be mapped into every pattern from
B
. It remains to see that every
pattern that can be mapped into every pattern from
B
can also be mapped into
π
.Picka
π
that can be mapped into every pattern from
pattern
B
. A pattern that can be mapped
π
can also be mapped into every pattern from Mod(
π
). Hence,
π
can be mapped
into
T ⊆
π
∈B
Mod(
into every pattern from
π
).Since
π
is a max-description of
T
,thereisa
π
to
homomorphism from
π
, which ends the proof.
We say that a query
Q preserves bases
if
Q
(
B
) is a basis of
Q
(
T
) whenever
B
is a
basis of
T
. From the lemma above we immediately obtain the following.
Theorem 14.14
If
T
is a set of trees,
B
is its basis, and Q is a query preserving bases,
then certain answers to Q over
T
and over
B
coincide. In particular,
Q
(
T
)=
Q
(
B
)
.
Together with
Theorem 14.11
, this gives a general approach to computing certain an-
swers to queries preserving bases, shown in
Algorithm 14.1
.
Algorithm 14.1 Certain answers to XML-to-XML queries
Require:
T
is a recursively enumerable set of trees,
Q
is a query preserving bases
compute a (small) basis
;
evaluate
Q
naıvely over elements of
B
of
T
B
to compute
Q
(
B
);
compute a max-description
π
of
Q
(
B
);
return
π
.
is guaranteed to be a certain answer. We shall now see
that this recipe can be applied to
TQL
.
The returned max-description
π
Theorem 14.15
TQL
queries preserve bases.
⊆
π
∈
Q
(
B
)
Mod(
Proof
Clearly
Q
(
B
)
⊆
Q
(
T
). It remains to check that
Q
(
T
)
π
).In
other words, for every
T
∈
Q
(
T
) we need some
π
∈
Q
(
B
) that can be mapped into
T
.Let
T
be a tree from
such that
Q
(
T
)=
T
.Since
, there exists
˜
T
B
is a basis of
T
π
∈B
and
a homomorphism
h
:
˜
T
. Let us see that
Q
(
˜
) can be mapped into
T
.
We prove a more general result. Fix a homomorphism
h
:
S
π
→
π
→
T
.
