Weighted hypertree decompositions and optimal query plans

ABSTRACT

Hypertree width [22, 25] is a measure of the degree of cyclicity of hypergraphs. A number of relevant problems from different areas, e.g., the evaluation of conjunctive queries in database theory or the constraint satisfaction in AI, are tractable when their underlying hypergraphs have bounded hypertree width. However, in practical contexts like the evaluation of database queries, we have more information besides the structure of queries. For instance, we know the number of tuples in relations, the selectivity of attributes and so on. In fact, all commercial query-optimizers are based on quantitative methods and do not care about structural properties.In this paper, we define the notion of weighted hypertree decomposition, in order to combine structural decomposition methods with quantitative approaches. Weighted hypertree decompositions are equipped with cost functions, that can be used for modelling many situations where we have further information on the given problem, besides its hypergraph representation. We analyze the complexity of computing the hypertree decompositions having the smallest weights, called minimal hypertree decompositions. We show that, in many cases, adding weights we loose tractability. However, we prove that, under some - not very severe - restrictions on the allowed cost functions and on the target hypertrees, optimal weighted hypertree decompositions can be computed in polynomial time. For some easier hypertree weighting functions, this problem is also highly parallelizable. Then, we provide a cost function that models query evaluation costs and show how to exploit weighted hypertree decompositions for determining (logical) query plans for answering conjunctive queries. Finally, we present the results of an experimental comparison of this query optimization technique with the query optimization of a commercial DBMS. These preliminary results are very promising, as for some large queries (with many joins) our hybrid technique clearly outperforms the commercial optimizer.

REFERENCES

• 1: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 2: Serge Abiteboul , Oliver M. Duschka, Complexity of answering queries using materialized views, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.254-263, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275516]
• 3: 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]
• 4: P. A. Bernstein and N. Goodman. The power of natural semijoins. SIAM Journal on Computing, 10(4), pp. 751--771, 1981.
• 5: Hans L. Bodlaender , Fedor V. Fomin, Tree Decompositions with Small Cost, Proceedings of the 8th Scandinavian Workshop on Algorithm Theory, p.378-387, July 03-05, 2002
• 6: Jin-Yi Cai , Venkatesan T. Chakaravarthy , Raghav Kaushik , Jeffrey F. Naughton, On the complexity of join predicates, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.207-214, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375592]
• 7: Ashok K. Chandra , Dexter C. Kozen , Larry J. Stockmeyer, Alternation, Journal of the ACM (JACM), v.28 n.1, p.114-133, Jan. 1981 [doi>10.1145/322234.322243]
• 8: 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]
• 9: 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]
• 10: R. Dechter. Constraint networks. In Stuart C. Shapiro, editor, Encyclopedia of Artificial Intelligence, pp. 276--285. Wiley, 1992. Volume 1, second edition.
• 11: Rina Dechter, Constraint Processing, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
• 12: Ronald Fagin , Alberto O. Mendelzon , Jeffrey D. Ullman, A simplied universal relation assumption and its properties, ACM Transactions on Database Systems (TODS), v.7 n.3, p.343-360, Sept. 1982 [doi>10.1145/319732.319735]
• 13: 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]
• 14: Eugene C. Freuder, A sufficient condition for backtrack-bounded search, Journal of the ACM (JACM), v.32 n.4, p.755-761, Oct. 1985 [doi>10.1145/4221.4225]
• 15: Markus Frick , Martin Grohe, Deciding first-order properties of locally tree-decomposable structures, Journal of the ACM (JACM), v.48 n.6, p.1184-1206, November 2001 [doi>10.1145/504794.504798]
• 16: Hector Garcia-Molina , Jennifer Widom , Jeffrey D. Ullman, Database System Implementation, Prentice-Hall, Inc., Upper Saddle River, NJ, 1999
• 17: Peter Harvey , Aditya Ghose, Reducing Redundancy in the Hypertree Decomposition Scheme, Proceedings of the 15th IEEE International Conference on Tools with Artificial Intelligence, p.474, November 03-05, 2003
• 18: Y. E. Ioannidis. Query Optimization. The Computer Science and Engineering Handbook, pp. 1038--1057, 1997.
• 19: Y. E. Ioannidis. The History of Histograms (abridged). In In Proc. of VLDB'03, Berlin, Germany, pp. 19--30, 2003.
• 20: 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]
• 21: Nathan Goodman , Oded Shmueli, Tree queries: a simple class of relational queries, ACM Transactions on Database Systems (TODS), v.7 n.4, p.653-677, Dec. 1982 [doi>10.1145/319758.319775]
• 22: G. Gottlob, N. Leone, and F. Scarcello. Hypertree decompositions and tractable queries. Journal of Computer and System Sciences, 64(3), pp. 579--627, 2002.
• 23: 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]
• 24: 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]
• 25: Georg Gottlob , Nicola Leone , Francesco Scarcello, Hypertree Decompositions: A Survey, Proceedings of the 26th International Symposium on Mathematical Foundations of Computer Science, p.37-57, August 27-31, 2001
• 26: Georg Gottlob , Nicola Leone , Francesco Scarcello, Computing LOGCFL certificates, Theoretical Computer Science, v.270 n.1-2, p.761-777, January [doi>10.1016/S0304-3975(01)00108-6]
• 27: S. H. Greibach. The Hardest Context-Free Language. SIAM Journal on Computing, 2(4):304--310, 1973.
• 28: Martin Grohe, The Complexity of Homomorphism and Constraint Satisfaction Problems Seen from the Other Side, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.552, October 11-14, 2003
• 29: Martin Groher , Thomas Schwentick , Luc Segoufin, When is the evaluation of conjunctive queries tractable?, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.657-666, July 2001, Hersonissos, Greece [doi>10.1145/380752.380867]
• 30: Marc Gyssens , Peter G. Jeavons , David A. Cohen, Decomposing constraint satisfaction problems using database techniques, Artificial Intelligence, v.66 n.1, p.57-89, March 1994 [doi>10.1016/0004-3702(94)90003-5]
• 31: David S. Johnson, A catalog of complexity classes, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
• 32: Phokion G. Kolaitis , Moshe Y. Vardi, Conjunctive-query containment and constraint satisfaction, Journal of Computer and System Sciences, v.61 n.2, p.302-332, Oct. 2000 [doi>10.1006/jcss.2000.1713]
• 33: David Maier, Theory of Relational Databases, Computer Science Pr, 1983
• 34: Christos H. Papadimitriou , Mihalis Yannakakis, On the complexity of database queries (extended abstract), Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.12-19, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263664]
• 35: J. Pearson and P. G. Jeavons. A Survey of Tractable Constraint Satisfaction Problems, CSD-TR-97-15, Royal Holloway, Univ. of London, 1997.
• 36: N. Robertson and P. D. Seymour. Graph minors ii. algorithmic aspects of tree width. Journal of Algorithms, 7, pp. 309--322, 1986.
• 37: W. L. Ruzzo. Tree-size bounded alternation. Journal of Computer and System Sciences, 21, pp. 218--235, 1980.
• 38: Domenico Saccà, Closures of database hypergraphs, Journal of the ACM (JACM), v.32 n.4, p.774-803, Oct. 1985 [doi>10.1145/4221.4997]
• 39: S. Skyum , L. G. Valiant, A complexity theory based on Boolean algebra, Journal of the ACM (JACM), v.32 n.2, p.484-502, April 1985 [doi>10.1145/3149.3158]
• 40: I. H. Sudborough. Time and Tape Bounded Auxiliary Pushdown Automata. In Mathematical Foundations of Computer Science (MFCS'77), LNCS 53, Springer-Verlag, pp.493--503, 1977.
• 41: Francesco Scarcello and Alfredo Mazzitelli. The hypertree decompositions homepage, since 2002. http://wwwinfo.deis.unical.it/~frank/Hypertrees/
• 42: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• 43: Moshe Y. Vardi, The complexity of relational query languages (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.137-146, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802186]
• 44: Moshe Y. Vardi, Constraint satisfaction and database theory: a tutorial, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.76-85, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335209]
• 45: M. Yannakakis. Algorithms for acyclic database schemes. In Proc. of VLDB'81, Cannes, France, pp. 82--94, 1981.
• 46: C. T. Yu and M. Z. Özsoyoǧlu. On determining tree-query membership of a distributed query. Infor, 22(3), pp. 261--282, 1984.
• 47: Clement T. Yu , Z. Meral Ozsoyoglu , K. Lam, Optimization of distributed tree queries, Journal of Computer and System Sciences, v.29 n.3, p.409-445, Dec. 1984 [doi>10.1016/0022-0000(84)90007-2]