Database Reference
In-Depth Information
Definition 14.7 The core of all max-descriptions of
T
is called the
core-description of
T
and denoted by
T
.The
core-certain answer
to
Q
over
T
is
Q
(
T
).
Technically speaking, the core-description is the core of the trees associated with the
max-descriptions, but we can always view it as a pattern. Furthermore, the core-description
is always a max-description: being a subpattern of a max-description,
T
is satisfied in
every tree in
T
, and since it is a homomorphic image of a max-description, every pattern
from Th(
) can be mapped into it. Thus the definition gives the canonical certain answer.
Moreover, if we restrict our attention to cores only, or equivalently, quotient the set of
trees by the homomorphic equivalence , the following relation is a partial order:
T
T
if and only if there is a homomorphism from
T
to
T
.
T
≤
By
Theorem 14.6
certain answers could then be defined simply as greatest lower bounds.
Corollary 14.8
A pattern
π
is a max-description of
T
if it is the greatest lower bound
of
T
with respect to the order
≤
.
The canonical certain answer comes at a certain computational cost. Recall that DP is
the class of problems which amount to solving a problem in NP and a (different) problem
in
CO
NP. This class
contains
both NP and
CO
NP; it should not be confused with NP
∩
CO
NP.
π
is the core of
Proposition 14.9
Checking whether
π
is in
DP
. Moreover, there is a
fixed pattern
π
0
such that checking whether
π
0
is the core of
π
is
NP
-complete.
π
is a core, this is done in
CO
NP. Then we check if there is a
Proof
First check if
π
, and an embedding of
π
into
homomorphism from
π
to
π
. Both conditions can be
checked in NP.
A simple reduction from 3-colorability shows NP-hardness: let
π
G
be a pattern with a
child
e
(
u
,
v
) under the root for every edge of the given graph
G
and let
π
be obtained by
π
=
r
[
e
(
x
,
y
)
,
e
(
y
,
x
)
,
e
(
y
,
z
)
,
e
(
z
,
y
)
,
e
(
x
,
z
)
,
e
(
z
,
y
)] at the root; it is easy to
see that
G
is 3-colorable iff
merging
π
G
and
π
is the core of
π
.
Computing cores can be expensive, but the second consequence of homomorphic equiv-
alence comes to the rescue: often it does not matter which certain answer we chose, because
they are indistinguishable to pattern queries and
TQL
queries.
Proposition 14.10
Let T
1
and T
2
be certain answers to Q over
T
. Then they cannot be
distinguished by
TQL
queries: Q
(
T
1
)=
Q
(
T
2
)
for each Q
∈
TQL
.
Proof
In fact, we show more, namely that
T
1
|
=
π
if and only if
T
2
|
=
π
for each
π
∈
Π
p
(C
ONST
,
⇓
,
=). f
T
1
|
=
π
, there is a witnessing homomorphism
h
:
π
→
T
1
.Since
there is also a homomorphism
h
:
T
1
→
T
1
and
T
2
are homomorphically equivalent,
T
2
.
Composing
h
and
h
we get a homomorphism
h
◦
h
:
π
→
T
2
witnessing that
T
2
|
=
π
.
The proposition now follows from this claim by induction on the structure of
Q
.
