The complexity of query containment in expressive fragments of XPath 2.0

DOI10.1145/1568318.1568321MaRDI QIDQ3452227zbMATH OpenOpenAlexFDO

Authors Balder ten Cate, Carsten Lutz

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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Database theory (68P15)

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

Cited in

(20)

• scientific article; zbMATH DE number 1953125 (Why is no real title available?)
• 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 tree pattern containment with arithmetic comparisons
• On the complexity of XPath containment in the presence of disjunction, DTDs, and variables
• Containment and equivalence for a fragment of XPath
• Least common container of tree pattern queries and its applications
• scientific article; zbMATH DE number 1953139 (Why is no real title available?)
• scientific article; zbMATH DE number 1953140 (Why is no real title available?)
• Axiomatizing the logical core of XPath 2.0
• Limiting Until in ordered tree query languages
• Conjunctive query containment over trees using schema information
• Complete axiomatizations for XPath fragments
• Database Programming Languages
• Logical Foundations of XML and XQuery
• The complexity of XPath query evaluation and XML typing
• XPath satisfiability in the presence of DTDs
• Transitive closure logic, nested tree walking automata, and XPath
• Some modal aspects of XPath

Describes a project that uses

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)