www.uhasselt.be
DSpace

Document Server@UHasselt >
Research >
All items >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/9692

Title: XPath satisfiability in the presence of DTDs
Authors: Benedikt, Michael
Fan, Wenfei
GEERTS, Floris
Issue Date: 2008
Publisher: ASSOC COMPUTING MACHINERY
Citation: JOURNAL OF THE ACM, 55(2). p. 1-79
Abstract: We study the satisfiability problem associated with XPath in the presence of DTDs. This is the problem of determining, given a query p in an XPath fragment and a DTD D, whether or not there exists an XML document T such that T conforms to D and the answer of p on T is nonempty. We consider a variety of XPath fragments widely used in practice, and investigate the impact of different XPath operators on the satisfiability analysis. We first study the problem for negation-free XPath fragments with and without upward axes, recursion and data-value joins, identifying which factors lead to tractability and which to NP-completeness. We then turn to fragments with negation but without data values, establishing lower and upper bounds in the absence and in the presence of upward modalities and recursion. We show that with negation the complexity ranges from PSPACE to EXPTIME. Moreover, when both data values and negation are in place, we find that the complexity ranges from NEXPTIME to undecidable. Furthermore, we give a finer analysis of the problem for particular classes of DTDs, exploring the impact of various DTD constructs, identifying tractable cases, as well as providing the complexity in the query size alone. Finally, we investigate the problem for XPath fragments with sibling axes, exploring the impact of horizontal modalities on the satisfiability analysis.
Notes: [Benedikt, Michael] Univ Oxford, Comp Lab, Oxford OX1 3QD, England. [Fan, Wenfei; Geerts, Floris] Univ Edinburgh, Edinburgh, Midlothian, Scotland. [Fan, Wenfei] Bell Labs, Murray Hill, NJ 07974 USA. [Geerts, Floris] Transnatl Univ Limburg, Limburg, Belgium.
URI: http://hdl.handle.net/1942/9692
Link to publication: http://doi.acm.org/10.1145/1346330.1346333
DOI: 10.1145/1346330.1346333
ISI #: 000256117000003
ISSN: 0004-5411
Category: A1
Type: Journal Contribution
Validation: ecoom, 2009
Appears in Collections: Databases and Theoretical Computer Science

Files in This Item:

There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.