Database Reference
In-Depth 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 max-description of Q (
T
).
are equivalent. But if they are to
play the role of certain answers to XML-to-XML queries, we need to view them as XML
trees as well-and then they are all different. What is the certain answer then?
To find canonical forms of max-descriptions 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 max-descriptions 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 child-only 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
child-only 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 max-descriptions, which
confirms the intuition of max-descriptions 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 max-description 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 max-description 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 max-descriptions
π
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
max-descriptions: the core.
In Section 6.4 we learned that homomorphically equivalent structures have isomorphic
cores. This means that all max-descriptions have the same core, which leads to the follow-
ing definition.
Search WWH ::




Custom Search