Size and treewidth bounds for conjunctive queries

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Size and treewidth bounds for conjunctive queries

Full text

Pdf (539 KB)

Source

Symposium on Principles of Database Systems archive
Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems table of contents

Providence, Rhode Island, USA

SESSION: Awards table of contents

Pages 45-54

Year of Publication: 2009

ISBN:978-1-60558-553-6

Authors

Georg Gottlob	Computing Laboratory and Oxford Man Institute of Quantitative Finance, University of Oxford, Oxford, United Kingdom
Stephanie Tien Lee	Computing Laboratory, University of Oxford, Oxford, United Kingdom
Gregory J. Valiant	UC Berkeley, Berkeley, CA, USA

Sponsors

ACM: Association for Computing Machinery
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGMOD: ACM Special Interest Group on Management of Data
SIGART: ACM Special Interest Group on Artificial Intelligence

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 20, Downloads (12 Months): 69, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1559795.1559804 What is a DOI?

ABSTRACT

This paper provides new worst-case bounds for the size and treewith of the result Q(D) of a conjunctive query Q to a database D. We derive bounds for the result size |Q(D)| in terms of structural properties of Q, both in the absence and in the presence of keys and functional dependencies. These bounds are based on a novel "coloring" of the query variables that associates a coloring number C(Q) to each query Q. Using this coloring number, we derive tight bounds for the size of Q(D) in case (i) no functional dependencies or keys are specified, and (ii) simple (one-attribute) keys are given. These results generalize recent size-bounds for join queries obtained by Atserias, Grohe, and Marx (FOCS 2008). An extension of our coloring technique also gives a lower bound for |Q(D)| in the general setting of a query with arbitrary functional dependencies. Our new coloring scheme also allows us to precisely characterize (both in the absence of keys and with simple keys) the treewidth-preserving queries--the queries for which the output treewidth is bounded by a function of the input treewidth. Finally we characterize the queries that preserve the sparsity of the input in the general setting with arbitrary functional dependencies.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, 1995.
	2	A. V. Aho , C. Beeri , J. D. Ullman, The theory of joins in relational databases, ACM Transactions on Database Systems (TODS), v.4 n.3, p.297-314, Sept. 1979 [doi>10.1145/320083.320091]
	3	A.V. Aho, Y. Sagiv, and J.D. Ullman. Equivalence of relational expressions. SIAM J. of Computing, 8(2):218--246, May 1979.
	4	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]
	5	Albert Atserias , Martin Grohe , Dániel Marx, Size Bounds and Query Plans for Relational Joins, Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, p.739-748, October 25-28, 2008 [doi>10.1109/FOCS.2008.43]
	6	Catriel Beeri , Moshe Y. Vardi, A Proof Procedure for Data Dependencies, Journal of the ACM (JACM), v.31 n.4, p.718-741, Oct. 1984 [doi>10.1145/1634.1636]
	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	Surajit Chaudhuri, An overview of query optimization in relational systems, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.34-43, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275492]
	9	Bruno Courcelle, The monadic second-order logic of graphs. I. recognizable sets of finite graphs, Information and Computation, v.85 n.1, p.12-75, March 1990 [doi>10.1016/0890-5401(90)90043-H]
	10	Alin Deutsch , Lucian Popa , Val Tannen, Query reformulation with constraints, ACM SIGMOD Record, v.35 n.1, March 2006 [doi>10.1145/1121995.1122010]
	11	Ronald Fagin , Phokion G. Kolaitis , Renée J. Miller , Lucian Popa, Data Exchange: Semantics and Query Answering, Proceedings of the 9th International Conference on Database Theory, p.207-224, January 08-10, 2003
	12	Georg Gottlob , Stephanie Tien Lee, A logical approach to multicut problems, Information Processing Letters, v.103 n.4, p.136-141, August, 2007 [doi>10.1016/j.ipl.2007.03.005]
	13	G. Gottlob, S.T. Lee, and G.J. Valiant. Size and treewidth bounds for conjunctive queries (extended version). Available from the authors upon request.
	14	G. Gottlob, R. Pichler, and F. Wei. Efficient datalog abduction through bounded treewidth. In AAAI, pages 1626--1631, 2007.
	15	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]
	16	Peter J. Haas , Jeffrey F. Naughton , S. Seshadri , Arun N. Swami, Selectivity and cost estimation for joins based on random sampling, Journal of Computer and System Sciences, v.52 n.3, p.550-569, June 1996 [doi>10.1006/jcss.1996.0041]
	17	Matthias Jarke , Jurgen Koch, Query Optimization in Database Systems, ACM Computing Surveys (CSUR), v.16 n.2, p.111-152, June 1984 [doi>10.1145/356924.356928]
	18	Phokion G. Kolaitis, Schema mappings, data exchange, and metadata management, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065176]
	19	Maurizio Lenzerini, Data integration: a theoretical perspective, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543644]
	20	Alon Y. Levy , Alberto O. Mendelzon , Yehoshua Sagiv, Answering queries using views (extended abstract), Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.95-104, May 22-25, 1995, San Jose, California, United States [doi>10.1145/212433.220198]
	21	David Maier , Alberto O. Mendelzon , Yehoshua Sagiv, Testing implications of data dependencies, ACM Transactions on Database Systems (TODS), v.4 n.4, p.455-469, Dec. 1979 [doi>10.1145/320107.320115]
	22	Frank Olken , Doron Rotem, Random Sampling from Database Files: A Survey, Proceedings of the 5th International Conference SSDBM on Statistical and Scientific Database Management, p.92-111, April 03-05, 1990
	23	N. Robertson and P.D. Seymour. Graph minors II: Algorithmic Aspects of Tree-Width. Journal of Algorithms, 7:309--322, 1986.
	24	Arun Swami , K. Bernhard Schiefer, On the estimation of join result sizes, Proceedings of the 4th international conference on extending database technology: Advances in database technology, p.287-300, May 1994, Cambridge, United Kingdom
	25	Mikkel Thorup, All structured programs have small tree width and good register allocation, Information and Computation, v.142 n.2, p.159-181, May 2, 1998 [doi>10.1006/inco.1997.2697]