Weighted hypertree decompositions and optimal query plans

DOI10.1016/J.JCSS.2006.10.010zbMath1115.68068OpenAlexW2057186622MaRDI QIDQ878759

Gianluigi Greco, Nicola Leone, Francesco Scarcello

Publication date: 26 April 2007

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2006.10.010

zbMATH Keywords

computational complexityhypergraphsdecomposition methodsrelational databasesquery processing

Mathematics Subject Classification ID

Database theory (68P15)

Related Items (3)

The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems ⋮ HyperBench ⋮ Uniform Constraint Satisfaction Problems and Database Theory

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hypertree decompositions and tractable queries
• Tree-size bounded alternation
• Decomposing constraint satisfaction problems using database techniques
• Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width.
• Conjunctive query containment revisited
• A comparison of structural CSP decomposition methods
• Conjunctive-query containment and constraint satisfaction
• On the Desirability of Acyclic Database Schemes
• The complexity of acyclic conjunctive queries
• Query evaluation via tree-decompositions
• Graph minors. II. Algorithmic aspects of tree-width
• A complexity theory based on Boolean algebra
• A sufficient condition for backtrack-bounded search
• Power of Natural Semijoins
• Alternation
• The Hardest Context-Free Language
• When is the evaluation of conjunctive queries tractable?
• Graph-Theoretic Concepts in Computer Science
• Computing LOGCFL certificates

This page was built for publication: Weighted hypertree decompositions and optimal query plans