The complexity of query containment in expressive fragments of XPath 2.0

DOI10.1145/1568318.1568321zbMATH Open1325.68079OpenAlexW2112167310MaRDI QIDQ3452227FDOQ3452227

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

Recommendations

• Containment and equivalence for a fragment of XPath
• On the complexity of XPath containment in the presence of disjunction, DTDs, and variables
• scientific article; zbMATH DE number 1953140
• scientific article; zbMATH DE number 1953139
• Structural properties of XPath fragments

zbMATH Keywords

XMLcomplexitysatisfiabilitycontainmentXPath

Mathematics Subject Classification ID

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

Cited In (16)

• On the minimization of XPath queries
• Deciding twig-definability of node selecting tree automata
• Static analysis of navigational XPath over graph databases
• On the complexity of XPath containment in the presence of disjunction, DTDs, and variables
• On the complexity of tree pattern containment with arithmetic comparisons
• Containment and equivalence for a fragment of XPath
• Least common container of tree pattern queries and its applications
• Title not available (Why is that?)
• Title not available (Why is that?)
• Axiomatizing the logical core of XPath 2.0
• Conjunctive query containment over trees using schema information
• Complete axiomatizations for XPath fragments
• Database Programming Languages
• Logical Foundations of XML and XQuery
• Some modal aspects of XPath
• Title not available (Why is that?)

Uses Software

• XPath

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3452227)