On the complexity of XPath containment in the presence of disjunction, DTDs, and variables
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 descenda...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Logical Methods in Computer Science e.V.
2006-07-01
|
| Series: | Logical Methods in Computer Science |
| Subjects: | |
| Online Access: | https://lmcs.episciences.org/2243/pdf |
| _version_ | 1797268753058103296 |
|---|---|
| author | Frank Neven Thomas Schwentick |
| author_facet | Frank Neven Thomas Schwentick |
| author_sort | Frank Neven |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T01:37:29Z |
| format | Article |
| id | doaj.art-32157932affb440c9e4e164debdb8f8c |
| institution | Directory Open Access Journal |
| issn | 1860-5974 |
| language | English |
| last_indexed | 2024-04-25T01:37:29Z |
| publishDate | 2006-07-01 |
| publisher | Logical Methods in Computer Science e.V. |
| record_format | Article |
| series | Logical Methods in Computer Science |
| spelling | doaj.art-32157932affb440c9e4e164debdb8f8c2024-03-08T08:36:23ZengLogical Methods in Computer Science e.V.Logical Methods in Computer Science1860-59742006-07-01Volume 2, Issue 310.2168/LMCS-2(3:1)20062243On the complexity of XPath containment in the presence of disjunction, DTDs, and variablesFrank Nevenhttps://orcid.org/0000-0002-7143-1903Thomas SchwentickXPath 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.https://lmcs.episciences.org/2243/pdfcomputer science - databasescomputer science - logic in computer scienceh.2i.7.2f.4 |
| spellingShingle | Frank Neven Thomas Schwentick On the complexity of XPath containment in the presence of disjunction, DTDs, and variables Logical Methods in Computer Science computer science - databases computer science - logic in computer science h.2 i.7.2 f.4 |
| title | On the complexity of XPath containment in the presence of disjunction, DTDs, and variables |
| title_full | On the complexity of XPath containment in the presence of disjunction, DTDs, and variables |
| title_fullStr | On the complexity of XPath containment in the presence of disjunction, DTDs, and variables |
| title_full_unstemmed | On the complexity of XPath containment in the presence of disjunction, DTDs, and variables |
| title_short | On the complexity of XPath containment in the presence of disjunction, DTDs, and variables |
| title_sort | on the complexity of xpath containment in the presence of disjunction dtds and variables |
| topic | computer science - databases computer science - logic in computer science h.2 i.7.2 f.4 |
| url | https://lmcs.episciences.org/2243/pdf |
| work_keys_str_mv | AT frankneven onthecomplexityofxpathcontainmentinthepresenceofdisjunctiondtdsandvariables AT thomasschwentick onthecomplexityofxpathcontainmentinthepresenceofdisjunctiondtdsandvariables |