Entropy Bounds for Conjunctive Queries

Prelegent(ci)

Szymon Toruńczyk

Afiliacja

Uniwersytet Warszawski

Termin

15 czerwca 2016 14:15

Pokój

p. 5870

Tytuł w języku angielskim

joint work with Tomasz Gogacz

Seminarium

Seminarium „Teoria automatów”

---

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.

---