Between tree patterns and conjunctive queries: is there tractability beyond acyclicity?

DOI10.1007/978-3-642-32589-2_61MaRDI QIDQ2912769zbMATH OpenOpenAlexFDO

Authors Filip Murlak, Michał Ogiński, Marcin Przybyłko

Publication date 25 September 2012

Published in Mathematical Foundations of Computer Science 2012 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-32589-2_61

Mathematics Subject Classification ID

Database theory (68P15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Conjunctive queries over trees
• Conjunctive query containment over trees
• Optimizing Conjunctive Queries over Trees Using Schema Information
• Conjunctive query containment over trees using schema information
• Hypertree decompositions and tractable queries

Cited in

(6)

• Conjunctive query containment over trees using schema information
• The uniform measure of simple regular sets of infinite trees
• On computing the measures of first-order definable sets of trees
• Conjunctive queries over trees
• On the complexity of enumerating the answers to well-designed pattern trees
• Characterizing XML twig queries with examples

This page was built for publication: Between tree patterns and conjunctive queries: is there tractability beyond acyclicity?

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