LIPIcs.ICDT.2017.15.pdf
- Filesize: 0.51 MB
- 17 pages
Document
Entropy Bounds for Conjunctive Queries with Functional Dependencies
Authors
-
Part of:
Volume:
20th International Conference on Database Theory (ICDT 2017)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Database Theory (ICDT) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2017-03-17
Cite AsGet BibTex
Tomasz Gogacz and Szymon Torunczyk. Entropy Bounds for Conjunctive Queries with Functional Dependencies. In 20th International Conference on Database Theory (ICDT 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 68, pp. 15:1-15:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.ICDT.2017.15
https://doi.org/10.4230/LIPIcs.ICDT.2017.15
Abstract
We study the problem of finding the worst-case size of the result Q(D) of a fixed conjunctive query Q applied to a database D satisfying given functional dependencies. We provide a characterization of this bound in terms of entropy vectors, and in terms of finite groups. In particular, we show that an upper bound provided by [Gottlob, Lee, Valiant and Valiant, J.ACM, 2012] is tight, and that a correspondence of [Chan and Yeung, ACM TOIT, 2002] is preserved in the presence of functional dependencies. However, tightness of a weaker upper bound provided by Gottlob et al., which would have immediate applications to evaluation of join queries ([Khamis, Ngo, and Suciu, PODS, 2016]) remains open. Our result shows that the problem of computing the worst-case size bound, in the general case, is closely related to difficult problems from information theory.
Keywords
- database theory
- conjunctive queries
- size bounds
- entropy
- finite groups
- entropy cone
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Albert Atserias, Martin Grohe, and Dániel Marx. Size bounds and query plans for relational joins. SIAM J. Comput., 42(4):1737-1767, 2013. URL: http://dx.doi.org/10.1137/110859440.
- Paul Beame, Paraschos Koutris, and Dan Suciu. Communication steps for parallel query processing. In Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2013, New York, NY, USA - June 22 - 27, 2013, pages 273-284, 2013. URL: http://dx.doi.org/10.1145/2463664.2465224.
- Ernest F. Brickell and Daniel M. Davenport. On the classification of ideal secret sharing schemes. Journal of Cryptology, 4(2):123-134, 1991. URL: http://dx.doi.org/10.1007/BF00196772.
- Terence H. Chan. Group characterizable entropy functions. CoRR, abs/cs/0702064, 2007. URL: http://arxiv.org/abs/cs/0702064.
-
Terence H. Chan and Raymond W. Yeung. On a relation between information inequalities and group theory. IEEE Transactions on Information Theory, 48(7):1992-1995, 2002.
- Oriol Farràs, Jessica Ruth Metcalf-Burton, Carles Padró, and Leonor Vázquez. On the optimization of bipartite secret sharing schemes. Des. Codes Cryptography, 63(2):255-271, May 2012. URL: http://dx.doi.org/10.1007/s10623-011-9552-7.
- Ehud Friedgut. Hypergraphs, entropy, and inequalities. The American Mathematical Monthly, 111(9):749-760, 2004. URL: http://www.jstor.org/stable/4145187.
- Tomasz Gogacz and Szymon Toruńczyk. Entropy bounds for conjunctive queries with functional dependencies. CoRR, abs/1512.01808, 2015. URL: http://arxiv.org/abs/1512.01808.
- Georg Gottlob, Stephanie Tien Lee, Gregory Valiant, and Paul Valiant. Size and treewidth bounds for conjunctive queries. J. ACM, 59(3):16, 2012. URL: http://dx.doi.org/10.1145/2220357.2220363.
-
Paul Halmos. Finite-Dimensional Vector Spaces. Springer, 1974.
- Mahmoud Abo Khamis, Hung Q. Ngo, and Dan Suciu. Computing join queries with functional dependencies. In Tova Milo and Wang-Chiew Tan, editors, Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2016, San Francisco, CA, USA, June 26 - July 01, 2016, pages 327-342. ACM, 2016. URL: http://dx.doi.org/10.1145/2902251.2902289.
- Serge Lang. Algebra. Addison-Wesley, Menlo Park Cal, 1993. URL: http://opac.inria.fr/record=b1081613.
- Laszló Lovász. Submodular functions and convexity. Mathematical programming: the state of the art, 1983. URL: http://www.cs.elte.hu/~lovasz/scans/submodular.pdf.
-
Desmond S. Lun. A relationship between information inequalities and group theory, 2002.
- Hung Q. Ngo, Ely Porat, Christopher Ré, and Atri Rudra. Worst-case optimal join algorithms: [extended abstract]. In Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2012, Scottsdale, AZ, USA, May 20-24, 2012, pages 37-48, 2012. URL: http://dx.doi.org/10.1145/2213556.2213565.
- Zhen Zhang and Raymond W. Yeung. On characterization of entropy function via information inequalities. IEEE Transactions on Information Theory, 44(4):1440-1452, 1998. URL: http://dx.doi.org/10.1109/18.681320.