Entropy bounds for conjunctive queries with functional dependencies

DOI10.4230/LIPICS.ICDT.2017.15MaRDI QIDQ3174907zbMATH OpenOpenAlexFDO

Authors Tomasz Gogacz, Szymon Toruńczyk

Publication date 18 July 2018

Full work available at URL https://arxiv.org/abs/1512.01808

zbMATH Keywords

conjunctive queriesdatabase theoryentropyentropy conefinite groupssize bounds

Mathematics Subject Classification ID

Database theory (68P15) Measures of information, entropy (94A17)

Abstract: We study the problem of finding the worst-case bound for the size of the result $Q(mathbbD)$ of a fixed conjunctive query $Q$ applied to a database $mathbbD$ satisfying given functional dependencies. We provide a precise 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 is tight, answering a question from their paper. Our result generalizes the bound due to Atserias, Grohe and Marx, who consider the case without functional dependencies. 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.

Recommendations

• Size and treewidth bounds for conjunctive queries
• On the complexity of finding bounds for projection cardinalities in relational databases
• Bounds and algorithms for joins via fractional edge covers
• Worst-case optimal join algorithms
• Enumeration complexity of conjunctive queries with functional dependencies

Cited in

(3)

• Size and treewidth bounds for conjunctive queries
• Join sampling under acyclic degree constraints and (cyclic) subgraph sampling
• Enumeration complexity of conjunctive queries with functional dependencies

This page was built for publication: Entropy bounds for conjunctive queries with functional dependencies

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3174907)