Query Containment in Very Expressive XPath dialects

Balder ten CateBalder ten Cate, Carsten LutzCarsten Lutz

Download

Balder ten Cate, Carsten Lutz
Query Containment in Very Expressive XPath dialects
In Leonid Libkin, eds., 26th ACM Symposium on Principles of Database Systems (PODS'07), 73-82, 2007. ACM Press

Details
Bibtex

KurzfassungAbstract
Query containment has been studied extensively for fragments of XPath 1.0. For instance, the problem is known to be EXPTIMEcomplete for CoreXPath, the navigational core of XPath 1.0. Much less is known about query containment in (fragments of) the richer language XPath 2.0. In this paper, we consider extensions of CoreXPath with the following operators, which are all part of XPath 2.0 (except the last): path intersection, path equality, path complementation, for-loops, and transitive closure. For each combination of these operators, we determine the complexity of query containment, both with and without DTDs. It turns out to range from EXPTIME (for extensions with path equality) and 2-EXPTIME (for extensions with path intersection) to non-elementary (for extensions with path complementation or for-loops). In almost all cases, adding transitive closure on top has no further impact on the complexity. We also investigate the effect of dropping the upward and/or sibling axes, and show that this sometimes leads to a reduction in complexity. Since the languages we study include negation and conjunction in filters, our complexity results can equivalently be stated in terms of satisfiability. We also analyze the above languages in terms of succinctness.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@inproceedings{ tenCate-Lutz-07,
  author = {Balder ten {Cate} and Carsten {Lutz}},
  booktitle = {26th {ACM} Symposium on Principles of Database Systems (PODS'07)},
  editor = {Leonid {Libkin}},
  pages = {73--82},
  publisher = {ACM Press},
  title = {Query Containment in Very Expressive {XPath} dialects},
  year = {2007},
}