The complexity of query containment in expressive fragments of XPath 2.0

DOI10.1145/1568318.1568321zbMath1325.68079OpenAlexW2112167310MaRDI QIDQ3452227

Carsten Lutz, Balder ten Cate

Publication date: 11 November 2015

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1568318.1568321

zbMATH Keywords

XMLcomplexitysatisfiabilitycontainmentXPath

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Database theory (68P15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (9)

Deciding twig-definability of node selecting tree automata ⋮ Static analysis of navigational XPath over graph databases ⋮ Some modal aspects of XPath ⋮ On the complexity of tree pattern containment with arithmetic comparisons ⋮ Conjunctive query containment over trees using schema information ⋮ Complete axiomatizations for XPath fragments ⋮ Axiomatizing the logical core of XPath 2.0 ⋮ Least common container of tree pattern queries and its applications ⋮ Logical Foundations of XML and XQuery

Uses Software

• XPath

This page was built for publication: The complexity of query containment in expressive fragments of XPath 2.0