2026-07-22T13:29:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7047 2024-03-06T10:39:26Z ddc:004 open_access

Entropy Bounds for Conjunctive Queries with Functional Dependencies Gogacz, Tomasz Torunczyk, Szymon database theory conjunctive queries size bounds entropy finite groups entropy cone 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tomasz Gogacz and Szymon Torunczyk 2017 Is Part Of LIPIcs, Volume 68, 20th International Conference on Database Theory (ICDT 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2017.15 urn:nbn:de:0030-drops-70479 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2017.15 eng https://creativecommons.org/licenses/by/3.0/legalcode