Query answering exploiting structural properties
- 1 September 2005
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGMOD Record
- Vol. 34 (3), 91-99
- https://doi.org/10.1145/1084805.1084827
Abstract
We review the notion of hypertree width, a measure of the degree of cyclicity of hypergraphs that is useful for identifying and solving efficiently easy instances of hard problems, by exploiting their structural properties. Indeed, a number of relevant problems from different areas, such as database theory, artificial intelligence, and game theory, are tractable when their underlying hypergraphs have small (i.e., bounded by some fixed constant) hypertree width. In particular, we describe how this notion may be used for identifying tractable classes of database queries and answering such queries in an efficient way.Keywords
This publication has 32 references indexed in Scilit:
- Hypertree Decompositions and Tractable QueriesJournal of Computer and System Sciences, 2002
- The complexity of acyclic conjunctive queriesJournal of the ACM, 2001
- A comparison of structural CSP decomposition methodsArtificial Intelligence, 2000
- Conjunctive-Query Containment and Constraint SatisfactionJournal of Computer and System Sciences, 2000
- On the Restraining Power of GuardsThe Journal of Symbolic Logic, 1999
- Graph minors. II. Algorithmic aspects of tree-widthJournal of Algorithms, 1986
- A sufficient condition for backtrack-bounded searchJournal of the ACM, 1985
- Closures of database hypergraphsJournal of the ACM, 1985
- Tree queriesACM Transactions on Database Systems, 1982
- A simplied universal relation assumption and its propertiesACM Transactions on Database Systems, 1982