Database Reference
In-Depth Information
but ours is based on an ordered tree model (sibling axes must be handled dif-
ferently). Several studies focused on restricted (unfixed) DTDs and XPath frag-
ments for which the problem is solvable eciently. Montazerian et al. proposed
two subclasses of DTDs called duplicate-free DTDs and covering DTDs, and
showed that satisfiability for some subfragments of XP
{↓,↓
∗
,
[]
,∪,∗}
can be solved
in PTIME under these DTDs [8]. Ishihara et al. proposed a subclasses of cov-
ering DTDs and investigated the tractability of XPath satisfiability under the
subclasses [6]. Suzuki et al. considered some XPath fragments for which satisfi-
ability is in PTIME under unfixed duplicate-free DTDs [10]. Their studies focus
on restricted unfixed DTDs, while this paper assumes that DTDs are fixed but
do not issues such restrictions.
The rest of this paper is organized as follows. Section 2 gives some preliminar-
ies. Section 3 shows the NP-completeness of satisfiability for XP
{↓,↑}
under fixed
DTDs. Section 4 presents a polynomial-time algorithm that solves satisfiability
for XP
{↓,↓
∗
,→
+
,←
+
}
under fixed DTDs. Section 5 shows a polynomial-time algo-
rithm that solves satisfiability for XP
{↓,↓
∗
,↑,↑
∗
,→
+
,←
+
}
under fixed nonrecursive
DTDs. Section 6 summarizes the paper.
2 Definitions
An XML document is modeled as a node-labeled ordered tree (attributes are
omitted). Each node in a tree represents an element. A text node is omitted,
in other words, we assume that each leaf node has a text node implicitly. For a
node
n
in a tree, by
l
(
n
) we mean the label (element name) of
n
. In what follows,
we use the term tree when we mean node-labeled ordered tree unless otherwise
stated.
Let
Σ
be a set of labels. A
DTD
is a tuple
D
=(
d, s
), where
d
is a mapping
from
Σ
to the set of regular expressions over
Σ
and
s ∈ Σ
is the
start label
.For
alabel
a ∈ Σ
,
d
(
a
)isthe
content model
of
a
. For example, the DTD in Sect. 1
is denoted as follows.
graduate)
+
d
(students) = (undergraduate
|
d
(undergraduate) = name
,
email
d
(graduate) = name email supervisor?
d
(name) =
d
(email) =
d
(supervisor) =
Atree
t
is
valid
against
D
if (i) the root of
t
is labeled by
s
and (ii) for each
node
n
in
tl
(
n
1
)
∈ L
(
d
(
l
(
n
))), where
n
1
···n
m
are the children of
n
and
L
(
d
(
l
(
n
))) is the language of
d
(
l
(
n
)).
D
is
no-star
if for any content
model
d
(
a
)of
D
,
d
(
a
)containsno'
···l
(
n
m
)
' operator. For labels
a, b
in
D
,wesaythat
b
is
reachable
from
a
if
b
occurs in
d
(
a
)orthereisalabel
c
such that
c
is reachable
∗
