The Polymatroid Bound: Extensions and Applications in Database Query Evaluation.

Abstract: Information theory has been used to compute upper bounds on the output sizes of database queries as well as to devise matching algorithms that can answer these queries within these bounds. The polymatroid bound generalizes many of these bounds and has a matching query evaluation algorithm, called PANDA [Abo Khamis et al, PODS'17]. In this talk, we present extensions of the polymatroid bound that utilize the query structure to derive new constraints on entropies. We state open problems regarding the relationship between these extensions and the original bound. On the algorithmic side, we present the PANDA algorithm in detail and discuss its shortcomings and related open problems.

Computer scienceMathematics

Audience: researchers in the discipline

Seminar on Algorithmic Aspects of Information Theory

Series comments: This online seminar is a follow up of the Dagstuhl Seminar 22301, www.dagstuhl.de/en/program/calendar/semhp/?semnr=22301.