Database Reference
In-Depth Information
(a)
(b)
s
d(s) = a b*
d(a) = c
d(c) =
d(b) = ef+
d(e) = b g
d(f) =
d(g) =
|
a
b
R(D)
ε
|
c
e
f
ε
ε
Σ
\ R(D)
g
Fig. 5.
(a) DTD
D
=(
d, s
) and (b) A graph representation of
D
1. If
lb
[1]
∈ Σ \ R
(
D
), then goto step 2. Otherwise, goto step 3.
2. Run the algorithm in this section for input (
q, D
). While running the al-
gorithm, if the following two conditions hold, then the context node moves
from
Σ \ R
(
D
)to
R
(
D
), thus set
q
=
/ax
[
i
+1]:
lb
[
i
+1]
/ ···/ax
[
m
]::
lb
[
m
]
and
D
=(
d, lb
[
i
+ 1]) and goto step 3.
-
The current label
lb
[
i
]
∈ Σ \ R
(
D
) but the next label
lb
[
i
+1]
∈ R
(
D
).
-
If there is an index
k ≥
2 such that
ax
[
i
+2]
, ··· ,ax
[
i
+
k
] are all sibling
axes but that
ax
[
i
+
k
+ 1] is not a sibling axis, then
lb
[
i
+
k
]
∈ R
(
D
).
3. Run the algorithm in the previous section for input (
q, D
). While running
the algorithm, if the current label
lb
[
i
]
∈ R
(
D
) but the next label
lb
[
i
+
1]
∈ Σ \ R
(
D
), then set
q
=
/ax
[
i
+1] :
lb
[
i
+1]
/ ···/ax
[
m
]::
lb
[
m
]and
D
=(
d, lb
[
i
+ 1]) and goto step 2.
It is clear that the above method runs in polynomial time. We have the following.
Theorem 4.
Let
D
be a fixed DTD and
q
=
/ax
[1] ::
lb
[1]
/ ···/ax
[
m
]::
lb
[
m
]
∈
XP
{↓,↓
∗
,↑,↑
∗
,→
+
,←
+
}
be a query. If one of the following conditions hold, then the
satisfiability of
q
under
D
can be determined in polynomial time.
-
D
is nonrecursive.
-
For every location step
ax
[
i
]::
lb
[
i
]
of
q
,if
ax
[
i
]
∈{↑, ↑
∗
}
, then neither
lb
[
i −
1]
nor
lb
[
i
]
is in
R
(
D
)
.
6Con lu on
In this paper, we have considered the XPath satisfiability problem under
fixed DTDs. We first have shown that SAT(XP
{↓,↑}
) is NP-complete under
fixed DTDs We have next shown that SAT(XP
{↓,↓
∗
,→
+
,←
+
}
) is in PTIME un-
der fixed DTDs. Finally, we have presented sucient conditions under which
SAT(XP
{↓,↓
∗
,↑,↑
∗
,→
+
,←
+
}
) is in PTIME under fixed DTDs.
There are many things to do as future works. First, the XPath fragments
considered in this paper are restricted in the sense that only a label is allowed