Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/959
Title: Satisfiability of XPath Queries with Sibling Axes
Authors: GEERTS, Floris 
Fan, W.
Issue Date: 2005
Publisher: Springer
Source: DATABASE PROGRAMMING LANGUAGES. p. 122-137
Series/Report: LECTURE NOTES IN COMPUTER SCIENCE
Series/Report no.: 3774
Abstract: We study the satisfiability problem for XPath fragments supporting the following-sibling and preceding-sibling axes. Although this problem was recently studied for XPath fragments without sibling axes, little is known about the impact of the sibling axes on the satisfiability analysis. To this end we revisit the satisfiability problem for a variety of XPath fragments with sibling axes, in the presence of DTDs, in the absence of DTDs, and under various restricted DTDs. In these settings we establish complexity bounds ranging from NLOGSPACE to undecidable. Our main conclusion is that in many cases, the presence of sibling axes complicates the satisfiability analysis. Indeed, we show that there are XPath satisfiability problems that are in PTIME and PSPACE in the absence of sibling axes, but that become NP-hard and EXPTIME-hard, respectively, when sibling axes are used instead of the corresponding vertical modalities (e.g., the wildcard and the descendant axis).
Document URI: http://hdl.handle.net/1942/959
ISBN: 3-540-30951-9
ISSN: 0302-9743
DOI: 10.1007/11601524_8
ISI #: 000235803000008
Category: A1
Type: Journal Contribution
Appears in Collections:Research publications

Files in This Item:
File Description SizeFormat 
satisfiability.pdf180.84 kBAdobe PDFView/Open
Show full item record

SCOPUSTM   
Citations

29
checked on Sep 4, 2020

WEB OF SCIENCETM
Citations

32
checked on May 21, 2022

Page view(s)

62
checked on May 25, 2022

Download(s)

154
checked on May 25, 2022

Google ScholarTM

Check

Altmetric


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