Database Reference
In-Depth Information
Satisfiability of Simple XPath Fragments under
Fixed DTDs
Nobutaka Suzuki
University of Tsukuba
1-2, Kasuga, Tsukuba Ibaraki 305-8550, Japan
nsuzuki@slis.tsukuba.ac.jp
Abstract.
The XPath satisfiability problem is to decide, for an XPath
expression
q
and a DTD
D
, if there exists an XML document
t
valid
against
D
such that the answer of
q
on
t
is nonempty. It is shown that the
satisfiability problem is intractable for many XPath fragments. In this
paper, we focus on fixed DTDs and consider the problem under fixed
DTDs. We first show that, for a very restricted XPath fragment, the
satisfiability problem is NP-complete under fixed DTDs. Then we show
several XPath fragments for which satisfiability is in PTIME under fixed
DTDs.
1
Introduction
XPath is a widely accepted query language for XML. For an XPath expression
q
and a DTD
D
,
q
is
satisfiable
under
D
if there exists an XML document
t
valid against
D
such that the answer of
q
on
t
is nonempty. Clearly, evaluat-
ing an unsatisfiable XPath expression is meaningless since such an expression
can always be replaced by an empty set without evaluating it. However, it is
shown that the satisfiability problem is intractable for a large number of XPath
fragments [1,4]. Therefore, it is important to find XPath fragments for which
the satisfiability problem is solvable eciently. In this paper, we focus on fixed
DTDs and consider XPath fragments for which satisfiability can be determined
eciently under fixed DTDs.
Let us show a simple example of an unsatisfiable XPath expression. Let us
consider the following DTD.
<!ELEMENT students (undergraduate|graduate)+>
<!ELEMENT undergraduate (name,email)>
<!ELEMENT graduate
(name,email,supervisor?)>
<!ELEMENT name
(#PCDATA)>
<!ELEMENT email
(#PCDATA)>
<!ELEMENT supervisor
(#PCDATA)>
Let
q
be an XPath expression
//supervisor/parent::undergraduate/name
,
which would return the names of undergraduate students that have a supervi-
sor. However, it is easy to see that
q
is unsatisfiable since an
undergraduate
