Friday 8th April, 12:15, room 310

posted 29 Mar 2016, 09:58 by Jakub Michaliszyn
Tomasz Gogacz

Entropy bounds for conjunctive queries with functional dependencies

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 is tight.