2017 · 92 citations · 32 references
ComputingComputer ScienceAlgorithmsInformation TheoryTheory Of ComputationPredicate LogicQuery ProcessingAlgorithmic Information TheoryDatalogProof Size Lower BoundsUpper Bounds
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 runtimes for aggregate and conjunctive queries with functional dependencies and degree bounds.
32
The generalized distributive law
S.M. Aji, Robert J. McEliece · IEEE Transactions on Information Theory · 2000 · 754 citations
Finding and counting given length cycles
Noga Alon, Raphael Yuster, Uri Zwick · Algorithmica · 1997 · 613 citations
Bucket elimination: A unifying framework for reasoning
Rina Dechter · Artificial Intelligence · 1999 · 593 citations
Thomas Eiter, Georg Gottlob, Heikki Mannila · ACM Transactions on Database Systems · 1997 · 490 citations · Full text