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
 
Search WWH ::




Custom Search