IEICE TRANSACTIONS on Information
Satisfiability of Simple XPath Fragments under Duplicate-Free DTDs
Summary :
In this paper, we consider the XPath satisfiability problem under restricted DTDs called “duplicate free”. For an XPath expression q and a DTD D, q is satisfiable under D if there exists an XML document t such that t is valid against D and that the answer of q on t is nonempty. Evaluating 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 XPath satisfiability problem is intractable for a large number of XPath fragments. In this paper, we consider simple XPath fragments under two restrictions: (i) only a label can be specified as a node test and (ii) operators such as qualifier ([]) and path union (∪) are not allowed. We first show that, for some small XPath fragments under the above restrictions, the satisfiability problem is NP-complete under DTDs without any restriction. Then we show that there exist XPath fragments, containing the above small fragments, for which the satisfiability problem is in PTIME under duplicate-free DTDs.
- Publication
- IEICE TRANSACTIONS on Information Vol.E96-D No.5 pp.1029-1042
- Publication Date
- 2013/05/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.E96.D.1029
- Type of Manuscript
- Special Section PAPER (Special Section on Data Engineering and Information Management)
- Category
- XML DB
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Nobutaka SUZUKI, Yuji FUKUSHIMA, Kosetsu IKEDA, "Satisfiability of Simple XPath Fragments under Duplicate-Free DTDs" in IEICE TRANSACTIONS on Information,
vol. E96-D, no. 5, pp. 1029-1042, May 2013, doi: 10.1587/transinf.E96.D.1029.
Abstract: In this paper, we consider the XPath satisfiability problem under restricted DTDs called “duplicate free”. For an XPath expression q and a DTD D, q is satisfiable under D if there exists an XML document t such that t is valid against D and that the answer of q on t is nonempty. Evaluating 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 XPath satisfiability problem is intractable for a large number of XPath fragments. In this paper, we consider simple XPath fragments under two restrictions: (i) only a label can be specified as a node test and (ii) operators such as qualifier ([]) and path union (∪) are not allowed. We first show that, for some small XPath fragments under the above restrictions, the satisfiability problem is NP-complete under DTDs without any restriction. Then we show that there exist XPath fragments, containing the above small fragments, for which the satisfiability problem is in PTIME under duplicate-free DTDs.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E96.D.1029/_p
Copy
@ARTICLE{e96-d_5_1029,
author={Nobutaka SUZUKI, Yuji FUKUSHIMA, Kosetsu IKEDA, },
journal={IEICE TRANSACTIONS on Information},
title={Satisfiability of Simple XPath Fragments under Duplicate-Free DTDs},
year={2013},
volume={E96-D},
number={5},
pages={1029-1042},
abstract={In this paper, we consider the XPath satisfiability problem under restricted DTDs called “duplicate free”. For an XPath expression q and a DTD D, q is satisfiable under D if there exists an XML document t such that t is valid against D and that the answer of q on t is nonempty. Evaluating 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 XPath satisfiability problem is intractable for a large number of XPath fragments. In this paper, we consider simple XPath fragments under two restrictions: (i) only a label can be specified as a node test and (ii) operators such as qualifier ([]) and path union (∪) are not allowed. We first show that, for some small XPath fragments under the above restrictions, the satisfiability problem is NP-complete under DTDs without any restriction. Then we show that there exist XPath fragments, containing the above small fragments, for which the satisfiability problem is in PTIME under duplicate-free DTDs.},
keywords={},
doi={10.1587/transinf.E96.D.1029},
ISSN={1745-1361},
month={May},}
Copy
TY - JOUR
TI - Satisfiability of Simple XPath Fragments under Duplicate-Free DTDs
T2 - IEICE TRANSACTIONS on Information
SP - 1029
EP - 1042
AU - Nobutaka SUZUKI
AU - Yuji FUKUSHIMA
AU - Kosetsu IKEDA
PY - 2013
DO - 10.1587/transinf.E96.D.1029
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E96-D
IS - 5
JA - IEICE TRANSACTIONS on Information
Y1 - May 2013
AB - In this paper, we consider the XPath satisfiability problem under restricted DTDs called “duplicate free”. For an XPath expression q and a DTD D, q is satisfiable under D if there exists an XML document t such that t is valid against D and that the answer of q on t is nonempty. Evaluating 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 XPath satisfiability problem is intractable for a large number of XPath fragments. In this paper, we consider simple XPath fragments under two restrictions: (i) only a label can be specified as a node test and (ii) operators such as qualifier ([]) and path union (∪) are not allowed. We first show that, for some small XPath fragments under the above restrictions, the satisfiability problem is NP-complete under DTDs without any restriction. Then we show that there exist XPath fragments, containing the above small fragments, for which the satisfiability problem is in PTIME under duplicate-free DTDs.
ER -
English
