What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?
Summary: Relates Shannon-type (Shannon flow) information inequalities to output-size bounds for disjunctive Datalog (generalizing CQs) under FDs, degree and input-cardinality bounds via “proof sequences”. Uses these sequences to drive PANDA, yielding algorithms that match fractional hypertree and exactly submodular-width runtimes. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Mahmoud Abo Khamis (LogicBlox Inc.)
- 2. Hung Q. Ngo (LogicBlox Inc.)
- 3. Dan Suciu (LogicBlox Inc.; University of Washington)
BibTeX Citation
@inproceedings{khamis_pods17,
address = {New York, NY, USA},
series = {{PODS} '17},
title = {{What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?}},
url = {https://dl.acm.org/doi/10.1145/3034786.3056105},
doi = {10.1145/3034786.3056105},
booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
publisher = {Association for Computing Machinery},
author = {Khamis, Mahmoud Abo and Ngo, Hung Q. and Suciu, Dan},
year = {2017}
}
Incoming Citations (Sorted by Pagerank)
Showing 50 of 52 citing papers.
Outgoing Citations (Sorted by Pagerank)
Showing 12 of 12 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 4,393 | Bounded Conjunctive Queries | 2014 | VLDB |
| 2 | 7,904 | Tight Bounds of Circuits for Sum-Product Queries | 2024 | PODS |
| 3 | 2,266 | On Functional Aggregate Queries with Additive Inequalities | 2019 | PODS |
| 4 | 10,174 | A Unifying Algorithm for Hierarchical Queries | 2026 | PODS |
| 5 | 5,982 | Size and Treewidth Bounds for Conjunctive Queries | 2009 | PODS |
| 6 | 10,643 | Fast Matrix Multiplication meets the Submodular Width | 2025 | PODS |
| 7 | 3,457 | Bag Query Containment and Information Theory | 2020 | PODS |
| 8 | 10,159 | Jaguar: A Primal Algorithm for Conjunctive Query Evaluation in Submodular-Width Time | 2026 | PODS |
| 9 | 9,994 | Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints | 2025 | PODS |
| 10 | 10,165 | PANDAExpress: A Simpler and Faster PANDA Algorithm | 2026 | PODS |