Database Reference
In-Depth Information
•
sizes of trees accepted by a tree automaton and at the same time satisfying a tree pattern;
and
•
sets of data values that appear in trees satisfying
(12.1)
.
We establish these bounds in the next three lemmas, and then use them to provide an
exhaustive search algorithm for building solutions. We begin with the case with no pattern,
i.e., only a tree automaton providing restrictions on trees.
Lemma 12.2
Let
A
be an UNFTA. If L
(
A
)
is nonempty, it contains a tree of height and
branching bounded by
A
.
Proof
Let
Q
be the set of states of
A
. Suppose
L
(
A
) is nonempty and let
T
∈
L
(
A
).
Fix an accepting run
, by the pigeon-hole
principle,
T
contains two nodes
v
,
w
such that
w
is a descendant of
v
and
ρ
of
A
on
T
. If the height of
T
is larger then
|
Q
|
ρ
(
v
)=
ρ
(
w
).
Modify
T
by replacing
T
.
v
(the subtree rooted at
v
) with
T
.
w
.Therun
ρ
can be easily
transformed into an accepting run of
over the modified
T
. Repeating this operation as
long as needed, we obtain a tree of height at most
A
.
Similarly, we can bound the branching. Let
v
be a node with children
v
1
,
v
2
,...,
v
n
,where
n
is greater than the maximum of the numbers of states of the vertical automata. Fix a
witnessing accepting run of the corresponding horizontal automaton. Again one can find
two children,
v
i
and
v
j
,
i
<
j
, that are labeled with the same state of the the horizontal
automaton. If we remove from
T
the subtrees rooted in
v
i
,
v
i
+1
,...,
v
j
−
1
, the resulting tree
is also accepted by
|
Q
|
accepted by
A
. Repeating this operation we obtain an accepted tree whose height
and branching are bounded by
A
A
.
From
Lemma 12.2
it follows immediately that for each regular schema
S
there is an
exponential-size tree conforming to
, or there is no conforming tree at all. This is also
true if we restrict to trees satisfying a given pattern.
S
Lemma 12.3
For a regular schema
S
over
Γ
, a pattern
π
(
x
)
, and a tuple of data values
2+
S
such that T
a, either there exists a tree T of size at most
12
·
π
·S
|
=
S
and
T
|
=
π
(
a
)
, or no tree conforming to
S
satisfies
π
(
a
)
.
Proof
By
Lemma 11.9
, for each pattern
π
satisfiable with respect to a schema
S
over
Γ
, there exists a homomorphism from
π
to some
T
conforming to
S
satisfying
|
supp
h
|≤
2
. Let us take such a tree
T
and homomorphism
h
.Let
12
·
π
·S
A
be the UNFTA
underlying schema
on
T
and take a node
v
of
T
that is a
leaf in supp
h
. It is easy to see that if we replace
T
.
v
with any XML tree
T
such that the
root of
T
is labeled with
lab
T
(
v
) and there is a run of
S
. Fix an accepting run
ρ
of
A
on
T
that assigns state
A
ρ
(
v
) to
the root, we get a tree conforming to
(
a
). Observe that the set of such
trees can be recognized by an automaton of size bounded by
S
and satisfying
π
S
: it is enough to change
the initial state of
A
to
ρ
(
v
) and modify the transition relation by setting
δ
(
ρ
(
v
)
,
)=0
for all
=
lab
T
(
v
). Consequently, by
Lemma 12.2
, we can assume that for each leaf
v
in
supp
h
the subtree
T
.
v
has size at most
S
S
. The total number of nodes in
T
is then
|·S
S
, which proves the lemma.
bounded by
|
supp
h
