Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/959
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | GEERTS, Floris | - |
dc.contributor.author | Fan, W. | - |
dc.date.accessioned | 2006-05-12T13:11:34Z | - |
dc.date.available | 2006-05-12T13:11:34Z | - |
dc.date.issued | 2005 | - |
dc.identifier.citation | DATABASE PROGRAMMING LANGUAGES. p. 122-137 | - |
dc.identifier.isbn | 3-540-30951-9 | - |
dc.identifier.issn | 0302-9743 | - |
dc.identifier.uri | http://hdl.handle.net/1942/959 | - |
dc.description.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). | - |
dc.format.extent | 185177 bytes | - |
dc.format.mimetype | application/pdf | - |
dc.language.iso | en | - |
dc.publisher | Springer | - |
dc.relation.ispartofseries | LECTURE NOTES IN COMPUTER SCIENCE | - |
dc.title | Satisfiability of XPath Queries with Sibling Axes | - |
dc.type | Journal Contribution | - |
dc.bibliographicCitation.bvolume | 3774 | - |
local.bibliographicCitation.conferencename | DATABASE PROGRAMMING LANGUAGES | - |
local.bibliographicCitation.conferenceplace | Trondheim, NORWAY, AUG 28-29, 2005 | - |
dc.identifier.epage | 137 | - |
dc.identifier.spage | 122 | - |
local.bibliographicCitation.jcat | A1 | - |
local.type.refereed | Refereed | - |
local.type.specified | Article | - |
local.relation.ispartofseriesnr | 3774 | - |
dc.bibliographicCitation.oldjcat | A1 | - |
dc.identifier.doi | 10.1007/11601524_8 | - |
dc.identifier.isi | 000235803000008 | - |
item.accessRights | Open Access | - |
item.fulltext | With Fulltext | - |
item.contributor | GEERTS, Floris | - |
item.contributor | Fan, W. | - |
item.fullcitation | GEERTS, Floris & Fan, W. (2005) Satisfiability of XPath Queries with Sibling Axes. In: DATABASE PROGRAMMING LANGUAGES. p. 122-137. | - |
crisitem.journal.issn | 0302-9743 | - |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
satisfiability.pdf | 180.84 kB | Adobe PDF | View/Open |
SCOPUSTM
Citations
29
checked on Sep 4, 2020
WEB OF SCIENCETM
Citations
32
checked on Mar 27, 2024
Page view(s)
104
checked on Nov 7, 2023
Download(s)
240
checked on Nov 7, 2023
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.