Nie jesteś zalogowany |
Entropy Bounds for Conjunctive Queries
- Prelegent(ci)
- Szymon Toruńczyk
- Afiliacja
- Uniwersytet Warszawski
- Termin
- 15 czerwca 2016 14:15
- Pokój
- p. 5870
- 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.
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.
