Computer Science – Databases
Scientific paper
2006-06-14
LMCS 2 (3:1) 2006
Computer Science
Databases
30 pages, will appear in Logical Methods in Computer Science (http://www.lmcs-online.org)
Scientific paper
10.2168/LMCS-2(3:1)2006
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.
Neven Frank
Schwentick Thomas
No associations
LandOfFree
On the complexity of XPath containment in the presence of disjunction, DTDs, and variables does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On the complexity of XPath containment in the presence of disjunction, DTDs, and variables, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the complexity of XPath containment in the presence of disjunction, DTDs, and variables will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-196931