Isolde Adler
ABSTRACT
Conjunctive query (CQ) evaluation on relational databases is NP-complete in general. Several restrictions, like bounded tree-width and bounded hypertree-width, allow polynomial time evaluations.We extend the framework in the presence of functional dependencies. Our exteAnded CQ evaluation problem has a concise equivalent formulation in terms of the homomorphism problem (HOM) for non-relational structures. We introduce the notions of "closure tree-width" and "hyperclosure tree-width" for arbitrary structures, and we prove that HOM (and hence CQ) restricted to bounded (hyper)closure tree-width becomes tractable. There are classes of structures with bounded closure tree-width but unbounded tree-width. Similar statements hold for hyperclosure tree-width and hypertree-width, and for hyperclosure tree-width and closure tree-width.
It follows from a result by Gottlob, Miklós, and Schwentick that for fixed k ≥ 2, deciding whether a given structure has hyperclosure tree-width at most k, is NP-complete. We prove an analogous statement for closure tree-width. Nevertheless, for given k we can approximate k-bounded closure tree-width in polynomial time.
- I. Adler. Width functions for hypergraph decompositions. Dissertation, 2006. Available at http://www.freidok.unifreiburg.de/volltexte/2468/pdf/thesis adler.pdf.Google Scholar
- I. Adler, G. Gottlob, and M. Grohe. Hypertree-width and related hypergraph invariants. European Journal of Combinatorics, 28(8):2167--2181, 2007. Preliminary version in EUROCOMB'05. Google ScholarDigital Library
- A. K. Chandra and Ph. M. Merlin. Optimal implementation of conjunctive queries in relational data bases. In STOC, pages 77--90. ACM, 1977. Google ScholarDigital Library
- Ch. Chekuri and A. Rajaraman. Conjunctive query containment revisited. Theor. Comput. Sci., 239(2):211--229, 2000. Google ScholarDigital Library
- David A. Cohen, Peter Jeavons, and Marc Gyssens. A unified theory of structural tractability for constraint satisfaction and spread cut decomposition. In Leslie Pack Kaelbling and Alessandro Saffiotti, editors, IJCAI, pages 72--77. Professional Book Center, 2005. Google ScholarDigital Library
- V. Dalmau, Ph. G. Kolaitis, and M. Y. Vardi. Constraint satisfaction, bounded treewidth, and finite-variable logics. In Pascal Van Hentenryck, editor, CP, volume 2470 of Lecture Notes in Computer Science, pages 310--326. Springer, 2002. Google ScholarDigital Library
- R. Diestel. Graph Theory. Springer, 1997.Google Scholar
- H.-D. Ebbinghaus and J. Flum. Finite Model Theory. Springer, 1990.Google Scholar
- T. Feder and M. Y. Vardi. The computational structure of monotone monadic snp and constraint satisfaction: A study through datalog and group theory. SIAM J. Comput., 28(1):57--104, 1998. Google ScholarDigital Library
- E. C. Freuder. Complexity of k-tree structured constraint satisfaction problems. In AAAI, pages 4--9, 1990.Google ScholarDigital Library
- G. Gottlob, N. Leone, and F. Scarcello. Hypertree decompositions and tractable queries. J. Comput. Syst. Sci., 64(3):579--627, 2002.Google ScholarDigital Library
- Georg Gottlob, Zoltán Miklós, and Thomas Schwentick. Generalized hypertree decompositions: np-hardness and tractable variants. In Leonid Libkin, editor, PODS, pages 13--22. ACM, 2007. Google ScholarDigital Library
- M. Grohe and D. Marx. Constraint solving via fractional edge covers. In SODA, pages 289--298. ACM Press, 2006. Google ScholarDigital Library
- G. Grätzer. Universal Algebra. Van Nostrand, 1968.Google Scholar
- M. Yannakakis. Algorithms for acyclic database schemes. In VLDB, pages 82--94. IEEE Computer Society, 1981. Google ScholarDigital Library
Index Terms
- Tree-width and functional dependencies in databases
Recommendations
Tree-Related Widths of Graphs and Hypergraphs
A hypergraph pair is a pair $(G,H)$ where $G$ and $H$ are hypergraphs on the same set of vertices. We extend the definitions of hypertree-width [G. Gottlob, N. Leone, and F. Scarcello, J. Comput. System Sci., 64 (2002), pp. 579-627] and generalized ...
Graphs of small rank-width are pivot-minors of graphs of small tree-width
We prove that every graph of rank-width k is a pivot-minor of a graph of tree-width at most 2k. We also prove that graphs of rank-width at most 1, equivalently distance-hereditary graphs, are exactly vertex-minors of trees, and graphs of linear rank-...
The relative clique-width of a graph
The tree-width of graphs is a well-studied notion the importance of which is partly due to the fact that many hard algorithmic problems can be solved efficiently when restricted to graphs of bounded tree-width. The same is true for the clique-width ...
Comments