You are not logged in |
joint work with Tomasz Gogacz
- Speaker(s)
- Szymon Toruńczyk
- Affiliation
- Uniwersytet Warszawski
- Date
- June 15, 2016, 2:15 p.m.
- Room
- room 5870
- Seminar
- Seminar Automata Theory
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.
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.
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.
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.
