Generalized hypertree decompositions: np-hardness and tractable variants

ABSTRACT

The generalized hypertree width GHW(H) of a hypergraph H is a measure of its cyclicity. Classes of conjunctive queries or constraint satisfaction problems whose associated hypergraphs have bounded GHW are known to be solvable in polynomial time. However,it has been an open problem for several years if for a fixed constant k and input hypergraph H it can be determined in polynomial time whether GHW(H)< k. Here, this problem is settled by proving that even for k=3 the problem is already NP-hard. On the way to this result, another long standing open problem, originally raised by Goodman and Shmueli in 1984 all in the context of join optimization is solved. It is proven that determining whether a hypergraph H admits a tree projection with respect to a hypergraph G is NP-complete. Our intractability results on generalized hypertree width motivate further research on more restrictive tractable hypergraph decomposition methods that approximate general hypertree decomposition (GHD). We show that each such method is dnominated by a tractable decomposition method definable through a function that associates a set of partial edges to a hypergraph. By using one particular such function, we define the new Component Hypertree Decomposition method, which is tractable and strictly more general than other approximations to GHD published so far.

REFERENCES

• 1: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 2: I. Adler. Marshals, monotone marshals, and hypertree-width. Journal of Graph Theory, 47(4):275--296, 2004.
• 3: I. Adler, G. Gottlob, and M. Grohe. Hypertree-width and related hypergraph invariants. In Proceedings of the 3rd European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB'05), volume AE of DMTCS Proceedings Series, pages 5--10, 2005.
• 4: Stefan Arnborg, Efficient algorithms for combinatorial problems on graphs with bounded, decomposability—a survey, BIT, v.25 n.1, p.2-23, 1985
• 5: Stefan Arnborg , Jens Lagergren , Detlef Seese, Easy problems for tree-decomposable graphs, Journal of Algorithms, v.12 n.2, p.308-340, June 1991 [doi>10.1016/0196-6774(91)90006-K]
• 6: Catriel Beeri , Ronald Fagin , David Maier , Mihalis Yannakakis, On the Desirability of Acyclic Database Schemes, Journal of the ACM (JACM), v.30 n.3, p.479-513, July 1983 [doi>10.1145/2402.322389]
• 7: Ashok K. Chandra , Philip M. Merlin, Optimal implementation of conjunctive queries in relational data bases, Proceedings of the ninth annual ACM symposium on Theory of computing, p.77-90, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803397]
• 8: Chandra Chekuri , Anand Rajaraman, Conjunctive query containment revisited, Theoretical Computer Science, v.239 n.2, p.211-229, May 28, 2000 [doi>10.1016/S0304-3975(99)00220-0]
• 9: D. A. Cohen, P. Jeavons, and M. Gyssens. A unified theory of structural tractability for constraint satisfaction and spread cut decomposition. In IJCAI'05, pages 72--77, 2005.
• 10: Brouno Courcelle, Graph rewriting: an algebraic and logic approach, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
• 11: Jörg Flum , Markus Frick , Martin Grohe, Query evaluation via tree-decompositions, Journal of the ACM (JACM), v.49 n.6, p.716-752, November 2002 [doi>10.1145/602220.602222]
• 12: Martin Charles Golumbic , Haim Kaplan , Ron Shamir, Graph sandwich problems, Journal of Algorithms, v.19 n.3, p.449-473, Nov. 1995 [doi>10.1006/jagm.1995.1047]
• 13: M. C. Golumbic and A. Wassermann. Complexity and algorithms for graph and hypergraph sandwich problems. Graphs and Combinatorics, 14:223--239, 1998.
• 14: N. Goodman and O. Shmueli. The tree projection theorem and relational query processing. JCSS, 28(1):60--79, 1984.
• 15: G. Gottlob, V. Gurvich, and Z. Miklós. On the complexity of the acyclic hypergraph sandwich problem. Technical Report DBAI-TR-2005-51, Vienna University of Technology, 2005.
• 16: A comparison of structural CSP decomposition methods, Artificial Intelligence, v.124 n.2, p.243-282, Dec. 2000 [doi>10.1016/S0004-3702(00)00078-3]
• 17: Georg Gottlob , Nicola Leone , Francesco Scarcello, The complexity of acyclic conjunctive queries, Journal of the ACM (JACM), v.48 n.3, p.431-498, May 2001 [doi>10.1145/382780.382783]
• 18: G. Gottlob, N. Leone, and F. Scarcello. Hypertree decompositions and tractable queries. Journal of Computer and System Sciences (JCSS), 64(3):579--627, May 2002.
• 19: Georg Gottlob , Nicola Leone , Francesco Scarcello, Robbers, marshals, and guards: game theoretic and logical characterizations of hypertree width, Journal of Computer and System Sciences, v.66 n.4, p.775-808, 1 June 2003 [doi>10.1016/S0022-0000(03)00030-8]
• 20: G. Gottlob, Z. Miklós, and T. Schwentick. Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants. Technical report DBAI-TR-2007-55, Vienna University of Technology, 2007. http://www.dbai.tuwien.ac.at/staff/miklos/ghw.pdf.
• 21: G. Gottlob, R. Pichler, and F. Wei. Bounded Treewidth as a Key to Tractability of Knowledge Representation and Reasoning. In Proc. AAAI 2006. AAAI Press, 2006.
• 22: Martin Grohe , Dániel Marx, Constraint solving via fractional edge covers, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.289-298, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109590]
• 23: Aviv Lustig , Oded Shmueli, Acyclic hypergraph projections, Journal of Algorithms, v.30 n.2, p.400-422, Feb. 1999 [doi>10.1006/jagm.1998.0965]
• 24: N. Robertson and P. D. Seymour. Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms, 7:309--322, 1986.
• 25: Yehoshua Sagiv , Oded Shmueli, Solving queries by tree projections, ACM Transactions on Database Systems (TODS), v.18 n.3, p.487-511, Sept. 1993 [doi>10.1145/155271.155277]
• 26: Francesco Scarcello , Gianluigi Greco , Nicola Leone, Weighted hypertree decompositions and optimal query plans, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055587]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Theory

Keywords:
NP-complete, acyclic, conjunctive query, hypergraph, hypertree decomposition, tractable, tree projection problem