Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/1420
Full metadata record
DC FieldValueLanguage
dc.contributor.authorNEVEN, Frank-
dc.contributor.authorSchwentick, T-
dc.date.accessioned2007-05-03T09:41:59Z-
dc.date.available2007-05-03T09:41:59Z-
dc.date.issued2006-
dc.identifier.citationLogical Methods in Computer Science, 2(3). p. 1-30-
dc.identifier.urihttp://hdl.handle.net/1942/1420-
dc.description.abstractXPath is a simple language for navigating an XML-tree and returning a set of answer nodes. The focus in this paper is on the complexity of the containment problem for various fragments of XPath. We restrict attention to the most common XPath expressions which navigate along the child and/or descendant axis. In addition to basic expressions using only node tests and simple predicates, we also consider disjunction and variables (ranging over nodes). Further, we investigate the containment problem relative to a given DTD. With respect to variables we study two semantics, (1) the original semantics of XPath, where the values of variables are given by an outer context, and (2) an existential semantics introduced by Deutsch and Tannen, in which the values of variables are existentially quantified. In this framework, we establish an exact classification of the complexity of the containment problem for many XPath fragments-
dc.format.extent364202 bytes-
dc.format.mimetypeapplication/pdf-
dc.language.isoen-
dc.subject.otherXPath, complexity, formal languages, logic-
dc.titleOn The Complexity Of Xpath Containment In The Presence Of Disjunction, Dtds, And Variables-
dc.typeJournal Contribution-
dc.identifier.epage30-
dc.identifier.issue3-
dc.identifier.spage1-
dc.identifier.volume2-
local.bibliographicCitation.jcatA2-
local.type.refereedRefereed-
dc.bibliographicCitation.oldjcatA2-
dc.identifier.doi10.2168/LMCS-2(3:1)2006-
item.accessRightsOpen Access-
item.fulltextWith Fulltext-
item.fullcitationNEVEN, Frank & Schwentick, T (2006) On The Complexity Of Xpath Containment In The Presence Of Disjunction, Dtds, And Variables. In: Logical Methods in Computer Science, 2(3). p. 1-30.-
Appears in Collections:Research publications
Files in This Item:
File Description SizeFormat 
frank1.pdfPostprint355.67 kBAdobe PDFView/Open
Show simple item record

SCOPUSTM   
Citations

67
checked on Sep 2, 2020

WEB OF SCIENCETM
Citations

44
checked on Jun 23, 2022

Page view(s)

50
checked on Jun 26, 2022

Download(s)

86
checked on Jun 26, 2022

Google ScholarTM

Check

Altmetric


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