Digital Symposium Collection 2000

Hypertree Decompositions and Tractable Queries Georg Gottlob, Nicola Leone, and Francesco Scarcello   View Paper (PDF)   Return to Query Optimization Abstract Several important decision problems on conjunctive queries (CQs) are NP-complete in general but become tractable, and actually highly parallelizable, if restricted to acyclic or nearly acyclic queries. Examples are the evaluation of Boolean CQs and query containment. These problems were shown tractable for conjunctive queries of bounded treewidth [9], and of bounded degree of cyclicity [24, 231. The so far most general concept of nearly acyclic queries was the notion of queries of bounded query-width introduced by Chekuri and Rajaraman [9]. While CQs of bounded query-width are tractable, it remained unclear whether such queries are erficiently recognizable. Chekuri and Rajaraman [9] stated as an open problem whether for each constant k it can be determined in polynomial time if a query has query width <= k. We give a negative answer by proving this problem NP- complete (specifically, for k = 4). In order to circumvent this difficulty, we introduce the new concept of hypertree decomposition of a query and the corresponding notion of hypertree width. We prove: (a) for each k, the class of queries with query width bounded by Ic is properly contained in the class of queries whose hypertree width is bounded by k; (b) unlike query width, constant hypertree-width is efficiently recognizable; (c) Boolean queries of constant hypertrce-width can be efficiently evaluated. References Note: References link to DBLP on the Web. [1] Serge Abiteboul , Richard Hull , Victor Vianu : Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0 Contents [2] Stefan Arnborg : Efficient Algorithms for Combinatorial Problems with Bounded Decomposability - A Survey. BIT 25(1) : 2-23(1985) [3] Catriel Beeri , Ronald Fagin , David Maier , Mihalis Yannakakis : On the Desirability of Acyclic Database Schemes. JACM 30(3) : 479-513(1983) [4] Philip A. Bernstein , Nathan Goodman : Power of Natural Semijoins. SIAM J. Comput. 10(4) : 751-771(1981) [5] Wolfgang Bibel : Constraint Satisfaction from a Deductive Viewpoint. Artificial Intelligence 35(3) : 401-413(1988) [6] Hans L. Bodlaender : A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth. SIAM J. Comput. 25(6) : 1305-1317(1996) [7] Ashok K. Chandra , Dexter Kozen , Larry J. Stockmeyer : Alternation. JACM 28(1) : 114-133(1981) [8] Ashok K. Chandra , Philip M. Merlin : Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977 : 77-90 [9] Chandra Chekuri , Anand Rajaraman : Conjunctive Query Containment Revisited. ICDT 1997 : 56-70 [10] Alessandro D'Atri , Marina Moscarini : Recognition Algorithms and Design Methodologies for Acyclic Database Schemes. Advances in Computing Research 3 : 43-67(1986) [11] ... [12] Rina Dechter , Judea Pearl : Tree Clustering for Constraint Networks. Artificial Intelligence 38(3) : 353-366(1989) [13] Ronald Fagin : Degrees of Acyclicity for Hypergraphs and Relational Database Schemes. JACM 30(3) : 514-550(1983) [14] Ronald Fagin , Alberto O. Mendelzon , Jeffrey D. Ullman : A Simplified Universal Relation Assumption and Its Properties. TODS 7(3) : 343-360(1982) [15] Eugene C. Freuder : A Sufficient Condition for Backtrack-Bounded Search. JACM 32(4) : 755-761(1985) [16] M. R. Garey , David S. Johnson : Computer and Intractability: A Guide to NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7 [17] Nathan Goodman , Oded Shmueli : Tree Queries: A Simple Class of Relational Queries. TODS 7(4) : 653-677(1982) [18] Georg Gottlob , Nicola Leone , Francesco Scarcello : The Complexity of Acyclic Conjunctive Queries. FOCS 1998 : 706-715 [19] ... [20] ... [21] ... [22] Sheila A. Greibach : The Hardest Context-Free Language. SIAM J. Comput. 2(4) : 304-310(1973) [23] Marc Gyssens , Peter Jeavons , David A. Cohen : Decomposing Constraint Satisfaction Problems Using Database Techniques. Artificial Intelligence 66(1) : 57-89(1994) [24] Marc Gyssens , Jan Paredaens : A Decomposition Methodology for Cyclic Databases. Advances in Data Base Theory 1982 : 85-122 [25] Peter Jeavons , David Cohen , Marc Gyssens : Closure Properties of Constraints. JACM 44(4) : 527-548(1997) [26] ... [27] Phokion G. Kolaitis , Moshe Y. Vardi : Conjunctive-Query Containment and Constraint Satisfaction. PODS 1998 : 205-213 [28] David Maier : The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0 Contents [29] Christos H. Papadimitriou , Mihalis Yannakakis : On the Complexity of Database Queries. PODS 1997 : 12-19 [30] Xiaolei Qian : Query Folding. ICDE 1996 : 48-55 [31] Neil Robertson , P. D. Seymour : Graph Minors. II. Algorithmic Aspects of Tree-Width. J. Algorithms 7(3) : 309-322(1986) [32] Walter L. Ruzzo : Tree-Size Bounded Alternation. JCSS 21(2) : 218-235(1980) [33] Sven Skyum , Leslie G. Valiant : A Complexity Theory Based on Boolean Algebra. JACM 32(2) : 484-502(1985) [34] Ivan Hal Sudborough : Time and Tape Bounded Auxiliary Pushdown Automata. MFCS 1977 : 493-503 [35] Robert Endre Tarjan , Mihalis Yannakakis : Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs. SIAM J. Comput. 13(3) : 566-579(1984) [36] Jeffrey D. Ullman : Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X Contents [37] Jeffrey D. Ullman : Information Integration Using Logical Views. ICDT 1997 : 19-40 [38] Moshe Y. Vardi : The Complexity of Relational Query Languages (Extended Abstract). STOC 1982 : 137-146 [39] Mihalis Yannakakis : Algorithms for Acyclic Database Schemes. VLDB 1981 : 82-94 [40] ... BIBTEX @inproceedings{DBLP:conf/pods/GottlobLS99,   author    = {Georg Gottlob and                 Nicola Leone and                 Francesco Scarcello},    title     = {Hypertree Decompositions and Tractable Queries},    booktitle = {Proceedings of the Eighteenth ACM SIGACT-SIGMOD-SIGART Symposium                 on Principles of Database Systems, May 31 - June 2, 1999, Philadelphia,                 Pennsylvania},    publisher = {ACM Press},    year      = {1999},    isbn      = {1-58113-062-7},    pages     = {21-32},    crossref  = {DBLP:conf/pods/99},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, Copyright(C) 2000 ACM