What Do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog Have to Do with One Another?
This paper connects semantic query optimization, physical query optimization & cost estimation, to information theory with provable bounds.
Authors: Mahmoud Abo Khamis, Hung Q. Ngo, Dan Suciu. 2017.
In Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS ‘17) (Invited to the Journal of the ACM)
Recent works on bounding the output size of a conjunctive query with functional dependencies and degree bounds have shown a deep connection between fundamental questions in information theory and database theory. We prove analogous output bounds for disjunctive datalog rules, and answer several open questions regarding the tightness and looseness of these bounds along the way. The bounds are intimately related to Shannon-type information inequalities. We devise the notion of a “proof sequence” of a specific class of Shannon-type information inequalities called “Shannon flow inequalities”. We then show how a proof sequence can be used as symbolic instructions to guide an algorithm called PANDA, which answers disjunctive datalog rules within the size bound predicted. We show that PANDA can be used as a black-box to devise algorithms matching precisely the fractional hypertree width and the submodular width run-times for aggregate and conjunctive queries with functional dependencies and degree bounds.
Read the PDF: What Do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog Have to Do with One Another? (opens in a new tab)
Related Posts
Comprehensive Survey of Recursive Query Processing and Optimization Techniques using Datalog
In recent years, we have witnessed a revival of the use of recursive queries in a variety of emerging application domains such as data integration and exchange, information extraction, networking, and program analysis. A popular language used for expressing these queries is Datalog.
Functional Aggregate Query (FAQ): Questions Asked Frequently
We define and study the Functional Aggregate Query (FAQ) problem, which encompasses many frequently asked questions in constraint satisfaction, databases, matrix operations, probabilistic graphical models and logic. This is our main conceptual contribution.