Database Reference
In-Depth Information
from
a
and that
b
occurs in
d
(
c
).
D
is
recursive
if there are labels
a, b
in
D
such
that
a
is reachable from
b
and
b
is reachable from
a
.
A
location step
is of the form
ax
::
lb
,where(i)
ax
is either
↓
(the child axis),
↓
∗
(the descendant-or-self axis),
↑
↑
∗
(the ancestor-or-self axis),
(the parent axis),
→
+
(the preceding-sibling axis), and (ii)
lb
is a label. A
query
is of the form
/ls
1
/ls
2
···/ls
n
,where
ls
i
+
(the following-sibling axis), or
←
is a location step.
For example, query
/↓
∗
::
a/→
+
::
b/c
stands for
/
descendant-or-self ::
a/
following-sibling ::
b/
child ::
c.
Let XP be the set of queries. We denote a fragment of XP by listing the axes
supported by the fragment. For example, XP
{↓,↓
∗
}
denotes the set of queries
using only child and descendant-or-self axes.
Let
t
be a tree and
q
be a query. We say that
t
satisfies
q
if the answer of
q
on
t
is nonempty. If there is a tree
t
such that
t
is valid against a DTD
D
and
that
t
satisfies
q
,then
q
is
satisfiable
under
D
. For an XPath fragment XP
S
,
the
XPath satisfiability problem
for XP
S
, denoted SAT(XP
S
), is to decide, for a
DTD
D
and a query
q ∈
XP
S
,if
q
is satisfiable under
D
.
3NP-Comp en s
In this section, we consider the complexity of SAT(XP
{↑,↓}
) under fixed DTDs. It
is shown that SAT(XP
{↑,↓}
) is NP-complete under fixed DTDs if a wildcard is al-
lowed as a node test (Theorem 6.6 of Ref. [1]). It is also shown that SAT(XP
{↑,↓}
)
is NP-complete under unfixed DTDs assuming that only a label is allowed as a
node test (Theorem 1 of Ref. [10]). In this section, we show a slightly more strong
result; SAT(XP
{↑,↓}
) is NP-complete under fixed DTDs even if only a label is
allowed as a node test. This implies that the XPath satisfiability problem is still
intractable under a very restricted setting.
Theorem 1.
SAT(XP
{↑,↓}
)
is NP-complete under fixed DTDs, even if only a
label is allowed as a node test.
Proof.
For a query
q
,aDTD
D
,andatree
t
valid against
D
, it is clear that
whether the answer of
q
on
t
is nonempty can be checked in polynomial time.
Thus SAT(XP
{↑,↓}
)isinNP.
To show the NP-hardness of the problem, we reduce 3SAT to this problem,
similarly to Theorem 6.6 of Ref. [1]. However, our reduction is much more com-
plicated since no wildcard node test is allowed. Let
φ
=
C
1
∧···∧C
n
be an
instance of 3SAT, where
C
1
, ··· ,C
n
are clauses. Let
x
1
, ··· ,x
m
be the variables
in
φ
. Without loss of generality, we assume that for any variable
x
i
, positive
literal
x
i
¬x
i
do not appear in the same clause. From this
instance, we construct an instance of the XPath satisfiability problem under
fixed DTDs, as follows.
and negative literal
