Please use this identifier to cite or link to this item:
Title: On The Complexity Of Xpath Containment In The Presence Of Disjunction, Dtds, And Variables
Authors: NEVEN, Frank 
Schwentick, T
Issue Date: 2006
Source: Logical Methods in Computer Science, 2(3). p. 1-30
Abstract: XPath 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
Keywords: XPath, complexity, formal languages, logic
Document URI:
DOI: 10.2168/LMCS-2(3:1)2006
Category: A2
Type: Journal Contribution
Appears in Collections:Research publications

Files in This Item:
File Description SizeFormat 
frank1.pdfPostprint355.67 kBAdobe PDFView/Open
Show full item record


checked on Sep 2, 2020


checked on May 22, 2022

Page view(s)

checked on May 28, 2022


checked on May 28, 2022

Google ScholarTM



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