Document Open Access Logo

Entropy Bounds for Conjunctive Queries with Functional Dependencies

Authors Tomasz Gogacz, Szymon Torunczyk

PDF

File

Thumbnail PDF
PDF
LIPIcs.ICDT.2017.15.pdf
  • Filesize: 0.51 MB
  • 17 pages

Document Identifiers

Subject Classification

Keywords
  • database theory
  • conjunctive queries
  • size bounds
  • entropy
  • finite groups
  • entropy cone

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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.

Cite As Get 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

Author Details

Tomasz Gogacz
Szymon Torunczyk

References

  1. 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.
  2. 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.
  3. 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.
  4. Terence H. Chan. Group characterizable entropy functions. CoRR, abs/cs/0702064, 2007. URL: http://arxiv.org/abs/cs/0702064.
  5. 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. Google Scholar
  6. 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.
  7. Ehud Friedgut. Hypergraphs, entropy, and inequalities. The American Mathematical Monthly, 111(9):749-760, 2004. URL: http://www.jstor.org/stable/4145187.
  8. 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.
  9. 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.
  10. Paul Halmos. Finite-Dimensional Vector Spaces. Springer, 1974. Google Scholar
  11. 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.
  12. Serge Lang. Algebra. Addison-Wesley, Menlo Park Cal, 1993. URL: http://opac.inria.fr/record=b1081613.
  13. 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.
  14. Desmond S. Lun. A relationship between information inequalities and group theory, 2002. Google Scholar
  15. 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.
  16. 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.
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact