Database Reference
In-Depth Information
and all subpatterns of
π
( a ) of the form //
π 1 satisfying
π 1 Φ
( v j ) or //
π 1 Φ
( v j ) for
some j . The answer is “yes” iff
is the root of the tree.
Let us now consider the data complexity. Tree patterns can be viewed as first-order
queries over signature extended with descendant and following-sibling, and so can be eval-
uated in L OGSPACE provided we can evaluate descendant and following-sibling tests in
L OGSPACE . This can be done since the next-sibling relation graph has outgoing degree
at most one, and for the child relation graph the same holds if we only reverse edges.
L OGSPACE -hardness follows from the hardness of reachability over successor relations;
hence even evaluating r [ a
π
( a )
Φ
(
ε
),where
ε
+ b ] over a tree of height1 is L OGSPACE -hard.
Satisfiability of tree patterns
The satisfiability problem for tree patterns is about finding a tree that satisfies a pattern.
The input consists of a schema
S
(a tree automaton or a DTD) and a pattern
π
( x );the
problem is to check whether there is a tree T that conforms to
S
and has a match for
π
(i.e., T |
=
π
). That is, the problem is formulated as follows:
PROBLEM : ATTERN S AT .
INPUT:
.
QUESTION : Isthereatree T that conforms to
A schema
S
, a tree pattern
π
S
and has a match for
π
?
We are now going to pinpoint the exact complexity of this problem.
Theorem 11.7 The problem P ATTERN S AT is NP -complete.
Furthermore, it remains NP -complete even if the schema is given as a DTD, and the
pattern comes from
Π
(
, ) and has no free variables.
Proof We start with the upper bound. We are going to show that there exists a small
witness for satisfiability. This witness, however, cannot be a tree that conforms to
S
and
satisfies
π
, simply because even the smallest tree that conforms to
S
can be exponential
in the size of
S
(see Exercise 16.3 ). However, to check that a tree T conforms to
S
and satisfies
, we do not need the whole tree, but only a portion of it that happens to be
polynomial in the sizes of
π
S
and
π
. We define it now.
π
Definition 11.8 (Support) The support of a homomorphism h :
T , denoted supp h ,
is the subtree of T obtained by keeping only nodes that have a descendant in the range of
h , or one of their sibling does.
For example, consider a tree pattern r [ // a ,// b / c ,// e ]. This pattern is satisfied by a tree
T given in Figure 11.3 (a) with the obvious homomorphism h which appropriately assigns
subformulae to the encircled nodes. To obtain supp h , we start with the range of h ,thenwe
add all ancestors of these nodes, and finally all siblings of all previously added nodes. The
result is shown in Figure 11.3 (b).
Note that together with each node included in the support we also include all its siblings.
As we shall see shortly, this is convenient if we want to check if a given support can be
extended to a tree conforming to the schema.
Search WWH ::




Custom Search