Database Reference
InDepth Information
Definition 14.5 Given a query
Q
and a set
T
of trees, a pattern
π
is a
certain answer to
Q over
T
if it is a maxdescription of
Q
(
T
).
are equivalent. But if they are to
play the role of certain answers to XMLtoXML queries, we need to view them as XML
trees as welland then they are all different. What is
the
certain answer then?
To find canonical forms of maxdescriptions we need to recall the notion of homomor
phisms between XML trees and patterns. As patterns provide a syntax for trees, each pat
tern
Viewed as formulae, all maxdescriptions of a family
T
π
∈
Π
p
(C
ONST
,
↓
,
=) can be viewed as a tree
T
π
(with variables): the tree associ
ated with
(
¯
π
n
] has an
labeled root with attributes
¯
and subtrees
T
π
1
,...,
T
π
n
,
where
T
ε
is the empty tree. Similarly, a tree
T
can be viewed as a childonly pattern with
constants.
Using this correspondence, we can naturally extend the notion of homomorphism be
tween patterns and trees, defined in
Section 11.1
, to trees with variables or equivalently
childonly patterns with constants. A homomorphism maps nodes to nodes and variables
to constants and variables, preserving the root, the child relation and the labeling, and if
u
stores a tuple ¯
α
)[
π
1
,...,
α
α,then
h
(
u
) stores
h
( ¯
α) (of course
h
extends to constants as the identity).
Recall that
T

=
π
iff there exists a homomorphism from
π
to
T
(
Lemma 11.5
). In
particular, Th(
to
every tree
T
∈T
. Then we have the following characterization of maxdescriptions, which
confirms the intuition of maxdescriptions as maximum extractable information from the
certain knowledge we have about
T
) is the set of patterns
π
such that there is a homomorphism from
π
T
.
Theorem 14.6
A pattern
π
is a maxdescription of
T
iff it belongs to
Th(
T
)
and every
pattern in
Th(
T
)
has a homomorphism into it.
Proof
Suppose that
π
∈
Th(
T
), and every pattern from Th(
T
) has a homomorphism
into
).
Pick a tree
T
which satisfies π.By
Lemma 11.5
, there is a homomorphism
h
: π
→
T
.
Pick a pattern
π
. We need to show that every tree satisfying
π
satisfies every pattern from Th(
T
π
from Th(
). By assumption, there exists a homomorphism
h
:
π
→
π
T
.
Hence,
h
◦
h
:
π
→
T
is a homomorphism. By
Lemma 11.5
,
T
satisfies
π
.
Conversely, suppose that
π
is a maxdescription of
T
. Then of course π belongs to
Th(
T
), and we only need to check that every pattern in Th(
T
) has a homomorphism into
π
∈
π
.Takeapattern
Th(
T
). It is obvious that
π
(viewed as a tree) satisfies
π
(viewed as
π
as well. Then, there is a homomorphism
h
:
π
→
π
a pattern). Hence,
π
satisfies
.
π
of a set of trees are
homomorphi
By
Theorem 14.6
every two maxdescriptions
π
and
π
→
π
and
π
→
π
cally equivalent
, as there are homomorphisms
. This has two important
consequences. The first one is that there is a natural canonical representative of all these
maxdescriptions: the core.
In
Section 6.4
we learned that homomorphically equivalent structures have isomorphic
cores. This means that all maxdescriptions have the same core, which leads to the follow
ing definition.