8 kwietnia 2016 12:15
TIBAD: Tomasz Gogacz, Entropy bounds for conjunctive queries with functional dependencies
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.