29 marca 2016 19:09

W piątek 8 kwietnia o 12:15 w sali 310 Tomasz Gogacz opowie o Entropy bounds for conjunctive queries with functional dependencies.

Abstrakt. 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.