Georg Gottlob
Abstract
Hypertree decompositions of hypergraphs are a generalization of tree decompositions of graphs. The corresponding hypertree-width is a measure for the acyclicity and therefore an indicator for the tractability of the associated computation problem. Several NP-hard decision and computation problems are known to be tractable on instances whose structure is represented by hypergraphs of bounded hypertree-width. Roughly speaking, the smaller the hypertree-width, the faster the computation problem can be solved. In this paper, we present the new backtracking-based algorithm det-k-decomp for computing hypertree decompositions of small width. Our benchmark evaluations have shown that det-k-decomp significantly outperforms opt-k-decomp, the only exact hypertree decomposition algorithm so far. Even compared to the best heuristic algorithm, we obtained competitive results as long as the hypergraphs are sufficiently simple.
- Bodlaender, H. L. 2005. Discovering treewidth. In Proceedings of the 31st Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM'05). Lecture Notes in Computer Science, vol. 3381. Springer-Verlag, New York. 1--16. Google Scholar
Digital Library
- Dechter, R. 2003. Constraint Processing, Chapt. 4, Morgan Kaufmann, Burlington, MA. 85--115. Google ScholarDigital Library
- Ganzow, T., Gottlob, G., Musliu, N., and Samer, M. 2005. A CSP hypergraph library. Tech. Rept. DBAI-TR-2005-50, Institute of Information Systems (DBAI), TU Vienna.Google Scholar
- Gottlob, G., Leone, N., and Scarcello, F. 1999. On tractable queries and constraints. In Proceedings of 10th International Conference on Database and Expert System Applications (DEXA). Lecture Notes in Computer Science, vol. 1677. Springer-Verlag, New York. 1--15. Google ScholarDigital Library
- Gottlob, G., Leone, N., and Scarcello, F. 2002. Hypertree decompositions and tractable queries. J. Comput. Syst. Sci. 64, 3, 579--627.Google ScholarDigital Library
- Gottlob, G., Leone, N., and Scarcello, F. 2003. Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width. J. Comput. Syst. Sci. 66, 4, 775--808. Google ScholarDigital Library
- Gottlob, G., Miklós, Z., and Schwentick, T. 2007. Generalized hypertree decompositions: NP-hardness and tractable variants. In Proceedings of the 26th ACM Symposium on Principles of Database Systems (PODS'07). ACM Press, New York. 13--22. Google ScholarDigital Library
- Harvey, P. and Ghose, A. 2003. Reducing redundancy in the hypertree decomposition scheme. In Proceedings of 15th International Conference on Tools with Artificial Intelligence (ICTAI'03). IEEE Computer Society, Los Alamitos, CA. 474--481. Google ScholarDigital Library
- Korimort, T. 2003. Constraint satisfaction problems—heuristic decomposition. Ph.D. thesis, Institute of Information Systems (DBAI), TU Vienna.Google Scholar
- Koster, A. M. C. A., Bodlaender, H. L., and van Hoesel, S. P. M. 2001. Treewidth: Computational experiments. Tech. Rept. ZIB-Report 01-38, Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB).Google Scholar
- Leone, N., Mazzitelli, A., and Scarcello, F. 2002. Cost-based query decompositions. In Proceedings of the 10th Italian Symposium on Advanced Database Systems (SEBD).Google Scholar
- McMahan, B. 2004. Bucket elimination and hypertree decompositions. Implementation Rept. Institute of Information Systems (DBAI), TU Vienna.Google Scholar
- Scarcello, F., Greco, G., and Leone, N. 2007. Weighted hypertree decompositions and optimal query plans. J. Comput. Syst. Sci. 73, 3, 475--506. Google ScholarDigital Library
Index Terms
- A backtracking-based algorithm for hypertree decomposition
Recommendations
General and Fractional Hypertree Decompositions: Hard and Easy Cases
PODS '18: Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database SystemsHypertree decompositions, as well as the more powerful generalized hypertree decompositions (GHDs), and the yet more general fractional hypertree decompositions (FHD) are hypergraph decomposition methods successfully used for answering conjunctive ...
Generalized hypertree decompositions: np-hardness and tractable variants
PODS '07: Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systemsThe 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,...
Generalized hypertree decompositions: NP-hardness and tractable variants
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,...
Comments