  We study the problem of finding the worst-case bound for the size of the
result $Q(\mathbb{ D})$ of a fixed conjunctive query $Q$ applied to a database
$\mathbb{ D}$ 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.

Databases