Menu

March 29, 2016, 7:09 p.m.

On Friday 8th April at 12:15 in room 310 Tomasz Gogacz will give a TIBAD seminar talk.

Title: Entropy bounds for conjunctive queries with functional dependencies.

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