Database Reference
In-Depth Information
in
SM
nr
(
Corollary 14.17
,
=)
,a
TQL
query Q, and tree T , one
can compute certain
M
(
Q
,
T
)
in time double-exponential in the size of T .
Given a mapping
M
⇓
Exercise 16.3
shows that even core-certain answer can be exponentially large, which
means there is no chance of answering queries efficiently in the general case. However,
we can do this efficiently if we can efficiently build a universal solution, and we know
cases when we can do so. The reason is that a universal solution constitutes a basis for all
solutions.
Lemma 14.18
If U is a universal solution for a tree T with respect to a mapping
M
,
then Q
(
U
)
is certain
M
(
Q
,
T
)
for each Q
∈
TQL
.
Proof
Let us first prove that for every universal solution
U
,
{
U
}
is a basis for the set
of solutions to
T
,S
OL
M
(
T
). Obviously
{
U
}⊆
S
OL
M
(
T
), so it suffices to prove that
Mod(
U
).Since
U
is a universal solution, for every
T
∈
S
OL
M
(
T
)
⊆
S
OL
M
(
T
) there is a
T
. But this means exactly that
U
viewed as a pattern is satisfied
in
T
.Inotherwordsthat
T
∈
homomorphism
h
:
U
→
Mod(
U
).
{
}
is a singleton basis for
Q
(S
OL
M
(
T
)), and to find the certain
answer to
Q
with respect to
T
and
By
Theorem14.16
,
Q
(
U
)
M
{
}
.For
singleton sets we get a max-description for free:
Q
(
U
) trivially satisfies both conditions for
being a max-description of
it is enough to find a max-description of
Q
(
U
)
{
Q
(
U
)
}
.
Now using the results on the efficient building of universal solutions from
Chapter 12
,
we show that certain answers can be efficiently found if mappings disallow the descendant
relation.
in
SM
nr
(
Corollary 14.19
,
=)
,a
TQL
query Q, and a tree T , one
can compute certain
M
(
Q
,
T
)
in time polynomial in the size of T .
Given a mapping
M
↓
M
Proof
In
Section 13.4
, we showed that for every tree
T
and every mapping
from
SM
nr
(
,
=), one can construct in polynomial time a universal solution
U
:itsufficesto
interpret the pattern mrg
D
t
(cpl
D
t
δ
S
,M
) as a tree. By
Lemma 14.18
,
Q
(
U
) is the certain
answer. By
Theorem 14.3
, we can compute
Q
(
U
) in time polynomial in the size of
U
.
↓
