Abstract
Many difficult problems that are tractable when restricted to acyclic instances are good candidates to be solved efficiently whenever their structure is not precisely acyclic, but not far from that. This is the case for fundamental database problems such as answering conjunctive queries or counting the number of answers (without actually computing them). The chapter describes structural decomposition methods that guarantee tractability for all such problem instances whose associated hypergraphs have a small degree of cyclicity, called width. In particular, it focuses on the notion of hypertree width, by describing its properties and its applications to the database field, and covering queries with aggregate operators and some recent parallel and distributed implementations.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Some notions strongly related to the treewidth appeared even before the 80’s in the literature. For a detailed story, we refer to [16].
References
C.R. Aberger, S. Tu, K. Olukotun, C. Ré, EmptyHeaded: A relational engine for graph processing, in Proceedings of SIGMOD 2016 (2016)
C.R. Aberger, S. Tu, K. Olukotun, C. Ré, Old techniques for new join algorithms: A case study in RDF processing, in CoRR, arXiv:abs/1602.03557 (2016)
I. Adler, G. Gottlob, M. Grohe, Hypertree width and related hypergraph invariants. Eur. J. Comb. 28(8), 2167–2181 (2007)
F.N. Afrati, M. Joglekar, C. Ré, S. Salihoglu, J.D. Ullman, GYM: A multiround join algorithm in mapreduce, in CoRR, arXiv:abs/1410.4156 (2014)
M. Aref, B. ten Cate, T.J. Green, B. Kimelfeld, D. Olteanu, E. Pasalic, T.L. Veldhuizen, G. Washburn, Design and implementation of the logicblox system, in Proceedings of SIGMOD 2015 (2015), pp. 1371–1382
R. Barilaro, F. Ricca, G. Terracina, Optimizing the distributed evaluation of stratified programs via structural analysis, in Proceeding of 11th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR 2011), Vancouver, Canada, 2011, Lecture Notes in Computer Science (Springer, Heidelberg, 2011), pp. 217–222
P.A. Bernstein, N. Goodman, Power of natural semijoins. SIAM J. Comput. 10(4), 751–771 (1981)
H.L. Bodlaender, A linear time algorithm for finding tree-decompositions of small treewidth, in Proceeding of STOC 1993 (1993), pp. 226–234
A.A. Bulatov, The complexity of the counting constraint satisfaction problem. J. ACM 60(5), 34:1–34:41 (2013)
A.A. Bulatov, M. Dyer, L.A. Goldberg, M. Jerrum, C. Mcquillan, The expressibility of functions on the boolean domain, with applications to counting CSPs. J. ACM 60(5), 32:1–32:36 (2013)
F. Calimeri, S. Perri, F. Ricca, Experimenting with parallelism for the instantiation of ASP programs. J. Algorithms Cogn. Inf. Log. 63(1–3), 34–54 (2008)
H. Chen, S. Mengel, A trichotomy in the complexity of counting answers to conjunctive queries, in Proceeding of ICDT 2015 (2015), pp. 110–126
D.A. Cohen, P. Jeavons, M. Gyssens, A unified theory of structural tractability for constraint satisfaction problems. J. Comput. Syst. Sci. 74(5), 721–743 (2008)
V. Dalmau, P. Jonsson, The complexity of counting homomorphisms seen from the other side. Theory Comput. Syst. 329(1–3), 315–323 (2004)
J. Dean, S. Ghemawat, Mapreduce: A flexible data processing tool. Commun. ACM 53(1), 72–77 (2010)
R. Dechter, Constraint Processing (Morgan Kaufmann Publishers Inc., 2003)
R. Dechter, N. Flerova, R. Marinescu, Search algorithms for M Best solutions for graphical models, in Proceeding of AAAI 2012 (2012), pp. 1895–1901
R. Fagin, Degrees of acyclicity for hypergraphs and relational database schemes. J. ACM 30(3), 514–550 (1983)
W. Fischl, G. Gottlob, R. Pichler, General and fractional hypertree decompositions: Hard and easy cases, in CoRR, arXiv:abs/1611.01090 (2016)
L. Ghionna, L. Granata, G. Greco, F. Scarcello, Hypertree decompositions for query optimization, in Proceeding of ICDE 2007 (2007), pp. 36–45
L. Ghionna, G. Greco, F. Scarcello, H-DB: A hybrid quantitative-structural sql optimizer, in Proceeding of CIKM 2011 (2011), pp. 2573–2576
G. Gottlob, G. Greco, Decomposing combinatorial auctions and set packing problems. J. ACM 60(4), 24:1–24:39 (2013)
G. Gottlob, N. Greco, N. Leone, F. Scarcello, Hypertree decompositions: Questions and answers, in Proceeding of PODS 2016 (2016), pp. 57–74
G. Greco, F. Scarcello, Tractable optimization problems through hypergraph-based structural restrictions, in Proceeding of ICALP 2009 (2009), pp. 16–30
G. Gottlob, G. Greco, F. Scarcello, Treewidth and hypertree width, in Tractability: Practical Approaches to Hard Problems, ed. by L. Bordeaux, Y. Hamadi, P. Kohli (2012)
G. Gottlob, M. Grohe, N. Musliu, M. Samer, F. Scarcello, Hypertree decompositions: Structure, algorithms, and applications, in Proceeding of WG 2005 (2005), pp. 1–15
G. Gottlob, S.T. Lee, G. Valiant, P. Valiant, Size and treewidth bounds for conjunctive queries. J. ACM 59(3), 1–35 (2012)
G. Gottlob, N. Leone, F. Scarcello, Advanced parallel algorithms for acyclic conjunctive queries. Technical Report DBAI-TR-98/18, Technical University of Vienna (1998)
G. Gottlob, N. Leone, F. Scarcello, On tractable queries and constraints, in Proceeding of DEXA 1999 (1999), pp. 1–15
G. Gottlob, N. Leone, F. Scarcello, The complexity of acyclic conjunctive queries. J. ACM 48(3), 431–498 (2001)
G. Gottlob, N. Leone, F. Scarcello, Computing LOGCFL certificates. Theor. Comput. Sci. 270(1–2), 761–777 (2002)
G. Gottlob, N. Leone, F. Scarcello, Hypertree decompositions and tractable queries. J. Comput. Syst. Sci. (Conference Version has Appeared in PODS 1999) 64(3), 579–627 (2002)
G. Gottlob, N. Leone, F. Scarcello, Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width. J. Comput. Syst. Sci. 66(4), 775–808 (2003)
G. Gottlob, Z. Miklós, T. Schwentick, Generalized hypertree decompositions: NP-hardness and tractable variants. J. ACM 56(6), 30:1–30:32 (2009)
G. Greco, F. Scarcello, The power of tree projections: Local consistency, greedy algorithms, and larger islands of tractability, in Proceeding of PODS 2010 (2010), pp. 327–338
G. Greco, F. Scarcello, Structural tractability of constraint optimization, in Proceeding of CP 2011 (2011), pp. 340–355
G. Greco, F. Scarcello, Counting solutions to conjunctive queries: Structural and hybrid tractability, in Proceeding of PODS 2014 (2014), pp. 132–143
G. Greco, F. Scarcello, Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems. Inf. Comput. 252, 201–220 (2017)
G. Greco, F. Scarcello, The power of local consistency in conjunctive queries and constraint satisfaction problems. SIAM J. Comput. (2017)
M. Grohe, D. Marx, Constraint solving via fractional edge covers. ACM Trans. Algorithms 11(1), 4:1–4:20 (2014)
I.F. Ilyas, G. Beskales, M.A. Soliman, A survey of top-k query processing techniques in relational database systems. ACM Comput. Surv. 40(4), 11:1–11:58 (2008)
M. Joglekar, R. Puttagunta, C. Ré, Aggregations over generalized hypertree decompositions, in Proceeding of PODS 2016 (2016)
M.R. Joglekar, C.M. Ré, It’s all a matter of degree: Using degree information to optimize multiway joins, in Proceeding of ICDT 2016 (2016), pp. 11:1–11:17
O. Kalinsky, Y. Etsion, B. Kimelfeld, Flexible caching in trie joins, in CoRR, arXiv:abs/1602.08721 (2016)
R.M. Karp, V. Ramachandran, Parallel algorithms for shared-memory machines, in Handbook of Theoretical Computer Science, vol. A (MIT Press, 1990), pp. 869–941
K. Kask, R. Dechter, J. Larrosa, A. Dechter, Unifying tree decompositions for reasoning in graphical models. Artif. Intell. 166(1–2), 165–193 (2005)
M.A. Khamis, H. Ngo, D. Suciu, Worst-case optimal algorithms for conjunctive queries with functional dependencies, in Proceeding of PODS 2016 (2016)
M.A. Khamis, H.Q. Ngo, C. Ré, A. Rudra, Joins via geometric resolutions: Worst-case and beyond, in Proceeding of PODS 2015 (2015), pp. 213–228
M.A. Khamis, H.Q. Ngo, A. Rudra. FAQ: Questions asked frequently, in Proceedings of PODS 2016 (2016)
B. Kimelfeld, Y. Sagiv, Incrementally computing ordered answers of acyclic conjunctive queries, in Proceedings of NGITS 2006 (2006), pp. 141–152
P.G. Kolaitis, Constraint satisfaction, databases, and logic, in Proceedings of IJCAI 2003 (2003), pp. 1587–1595
E.L. Lawler, A procedure for computing the k best solutions to discrete optimization problems and its application to the shortest path problem. Manag. Sci. 18(7), 401–405 (1972)
D. Marx, Approximating fractional hypertree width. ACM Trans. Algorithms 6(2), 29:1–29:17 (2010)
D. Marx, Tractable hypergraph properties for constraint satisfaction and conjunctive queries. J. ACM 60(6), 42:1–42:51 (2013)
J. Minker (ed.), Foundations of Deductive Databases and Logic Programming (Morgan Kaufmann Publishers Inc., Washington DC, 1988)
H.Q. Ngo, C. Ré, A. Rudra, Skew strikes back: New developments in the theory of join algorithms. SIGMOD Rec. 42(4), 5–16 (2013)
R. Pichler, S. Skritek, Tractable counting of the answers to conjunctive queries. J. Comput. Syst. Sci. 79(6), 984–1001 (2013)
O. Reingold, Undirected connectivity in log-space. J. ACM 55(4), 17:1–17:24 (2008)
N. Robertson, P. Seymour, Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms 7(3), 309–322 (1986)
F. Scarcello, G. Greco, N. Leone, Weighted hypertree decompositions and optimal query plans. J. Comput. Syst. Sci. 73(3), 475–506 (2007)
R.E. Tarjan, M. 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)
G. Terracina, N. Leone, V. Lio, C. Panetta, Experimenting with recursive queries in database and logic programming systems. Theory Pract. Log. Program. (TPLP) 8(2), 129–165 (2008)
L.G. Valiant, A bridging model for parallel computation. Commun. ACM 33(8), 103–111 (1990)
T.L. Veldhuizen, Triejoin: A simple, worst-case optimal join algorithm, in Proceedings of ICDT 2014 (2014), pp. 96–106
M. Yannakakis, Algorithms for acyclic database schemes, in Proceedings of VLDB 1981 (1981), pp. 82–94
Acknowledgements
The work was supported by project “Ba2Know (Business Analytics to Know) Service Innovation - LAB”, No. PON03PE_00001_1 funded by the Italian Ministry of University and Research (MIUR), and by project “Smarter Solutions in the Big Data World (S2BDW)”, funded by the Italian Ministry for Economic Development (MISE) within the programme PON “Imprese e competitivitá” 2014–2020.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG
About this chapter
Cite this chapter
Greco, G., Leone, N., Scarcello, F., Terracina, G. (2018). Structural Decomposition Methods: Key Notions and Database Applications. In: Flesca, S., Greco, S., Masciari, E., Saccà, D. (eds) A Comprehensive Guide Through the Italian Database Research Over the Last 25 Years. Studies in Big Data, vol 31. Springer, Cham. https://doi.org/10.1007/978-3-319-61893-7_15
Download citation
DOI: https://doi.org/10.1007/978-3-319-61893-7_15
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-61892-0
Online ISBN: 978-3-319-61893-7
eBook Packages: EngineeringEngineering (R0)