DBScholar

Back to papers

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)

Paper ID
hab7025df5bb52cb0
Venue
PODS
Year
2017
Pagerank
0.00012068611
Overall Rank
1,091 | 92.67%
DOI
10.1145/3034786.3056105

Incoming Non-self Citations Over Time

Authors

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 53 citing papers.

Rank Citing Paper Year Venue Pagerank
315 Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems 2018 PODS 0.00021236408
1,465 Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities 2019 SIGMOD 0.00010572023
2,302 On Functional Aggregate Queries with Additive Inequalities 2019 PODS 8.6687541e-05
2,593 Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries 2020 VLDB 8.2429717e-05
2,824 G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching 2020 SIGMOD 7.9662478e-05
2,844 FactorJoin: A New Cardinality Estimation Framework for Join Queries 2023 SIGMOD 7.9446987e-05
3,161 A Learned Sketch for Subgraph Counting 2021 SIGMOD 7.5771609e-05
3,188 Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries 2020 PODS 7.5510881e-05
3,526 Bag Query Containment and Information Theory 2020 PODS 7.2287658e-05
3,994 Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins 2023 PODS 6.8652819e-05
4,161 The Relational Data Borg is Learning 2020 VLDB 6.7669004e-05
4,466 Instance and Output Optimal Parallel Algorithms for Acyclic Joins 2019 PODS 6.584648e-05
4,510 Conjunctive Queries with Comparisons 2022 SIGMOD 6.5673056e-05
4,607 Worst-Case Optimal Graph Joins in Almost No Space 2021 SIGMOD 6.501689e-05
4,745 Optimal Join Algorithms Meet Top-k 2020 SIGMOD 6.4369578e-05
4,854 LpBound: Pessimistic Cardinality Estimation using ℓp-Norms of Degree Sequences 2025 SIGMOD 6.3775929e-05
4,945 Debunking the Myth of Join Ordering: Toward Robust SQL Analytics 2025 SIGMOD 6.3418058e-05
5,013 Free Join: Unifying Worst-Case Optimal and Traditional Joins 2023 SIGMOD 6.3119508e-05
5,224 SafeBound: A Practical System for Generating Cardinality Bounds 2023 SIGMOD 6.2197808e-05
5,487 Beyond Equi-joins: Ranking, Enumeration and Factorization 2021 VLDB 6.1085184e-05
5,895 Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees 2025 SIGMOD 5.9534254e-05
5,910 Join Size Bounds using l_p-Norms on Degree Sequences 2024 PODS 5.9478947e-05
6,432 Evaluating Datalog over Semirings: A Grounding-based Approach 2024 PODS 5.7857524e-05
6,469 Output-sensitive Conjunctive Query Evaluation 2024 PODS 5.7719911e-05
6,533 Query Evaluation by Circuits 2022 PODS 5.7519838e-05
6,547 Ranked Enumeration of Join Queries with Projections 2022 VLDB 5.7488764e-05
6,569 Fast Matrix Multiplication for Query Processing 2024 PODS 5.7442578e-05
6,576 Output-Optimal Algorithms for Join-Aggregate Queries 2025 PODS 5.7428578e-05
6,692 Tractability Beyond beta-Acyclicity for Conjunctive Queries with Negation 2021 PODS 5.7048435e-05
6,881 Insert-Only versus Insert-Delete in Dynamic Query Evaluation 2024 PODS 5.6559492e-05
6,958 The Complexity of Boolean Conjunctive Queries with Intersection Joins 2022 PODS 5.6316072e-05
7,341 Space-Time Tradeoffs for Conjunctive Queries with Access Patterns 2023 PODS 5.5465684e-05
7,442 A Nearly Instance-optimal Differentially Private Mechanism for Conjunctive Queries 2022 PODS 5.5241292e-05
7,616 Computing Complex Temporal Join Queries Efficiently 2022 SIGMOD 5.4822011e-05
8,338 Continual Observation of Joins under Differential Privacy 2024 SIGMOD 5.3502656e-05
8,770 Minimally Factorizing the Provenance of Self-join Free Conjunctive Queries 2024 PODS 5.2811408e-05
9,420 Output-Sensitive Evaluation of Regular Path Queries 2025 PODS 5.1802184e-05
10,186 Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints 2025 PODS 5.0628015e-05
10,187 Path-centric Cardinality Estimation for Subgraph Matching 2025 VLDB 5.0628015e-05
10,216 Conjunctive Queries with Negation and Aggregation: A Linear Time Characterization 2024 PODS 5.0572653e-05
10,308 Worst-Case-Optimal Similarity Joins on Graph Databases 2024 SIGMOD 5.0377711e-05
10,388 Jaguar: A Primal Algorithm for Conjunctive Query Evaluation in Submodular-Width Time 2026 PODS 4.9769913e-05
10,394 PANDAExpress: A Simpler and Faster PANDA Algorithm 2026 PODS 4.9769913e-05
10,410 The Space-Time Complexity of Sum-Product Queries 2026 PODS 4.9769913e-05
10,519 Succinct Structure Representations for Efficient Query Optimization 2026 SIGMOD 4.9769913e-05
10,638 CorrBound: Cardinality Estimation Accounting for Inter- and Intra-relation Correlations 2026 SIGMOD 4.9769913e-05
10,734 Secure Multi-Party Sampling over Joins 2026 VLDB 4.9769913e-05
10,863 Worst-Case Optimal BGPs on Temporal Graphs 2026 VLDB 4.9769913e-05
10,893 FlowLog: Efficient and Extensible Datalog via Incrementality 2026 VLDB 4.9769913e-05
11,091 Circuit Bounds for Conjunctive Queries with Self-joins 2025 PODS 4.9769913e-05
Previous Page 1 / 2 Next

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