Database Paper Browser

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
1717
Venue
PODS
Year
2017
Pagerank
0.00011956109
Overall Rank
1,442 | 89.97%
DOI
10.1145/3034786.3056105

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 48 of 48 citing papers.

Rank Citing Paper Year Venue Pagerank
2,142 Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities 2019 SIGMOD 9.4507296e-05
3,006 On Functional Aggregate Queries with Additive Inequalities 2019 PODS 7.7299363e-05
3,646 G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching 2020 SIGMOD 6.8853079e-05
3,715 Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries 2020 VLDB 6.8220943e-05
3,775 Bag Query Containment and Information Theory 2020 PODS 6.775636e-05
3,778 A Learned Sketch for Subgraph Counting 2021 SIGMOD 6.7747398e-05
3,781 Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries 2020 PODS 6.7723513e-05
3,990 FactorJoin: A New Cardinality Estimation Framework for Join Queries 2023 SIGMOD 6.5581983e-05
4,708 Instance and Output Optimal Parallel Algorithms for Acyclic Joins 2019 PODS 5.980172e-05
4,787 The Relational Data Borg is Learning 2020 VLDB 5.9224501e-05
5,104 Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins 2023 PODS 5.6946113e-05
5,493 Worst-Case Optimal Graph Joins in Almost No Space 2021 SIGMOD 5.4771449e-05
5,718 Conjunctive Queries with Comparisons 2022 SIGMOD 5.3552123e-05
5,855 Optimal Join Algorithms Meet Top-k 2020 SIGMOD 5.3006096e-05
5,885 Continual Observation of Joins under Differential Privacy 2024 SIGMOD 5.2880878e-05
5,962 Beyond Equi-joins: Ranking, Enumeration and Factorization 2021 VLDB 5.2536266e-05
5,972 SafeBound: A Practical System for Generating Cardinality Bounds 2023 SIGMOD 5.2474768e-05
5,992 Evaluating Datalog over Semirings: A Grounding-based Approach 2024 PODS 5.2415551e-05
6,305 Free Join: Unifying Worst-Case Optimal and Traditional Joins 2023 SIGMOD 5.1209718e-05
6,626 Tractability Beyond beta-Acyclicity for Conjunctive Queries with Negation 2021 PODS 4.9889109e-05
6,969 LpBound: Pessimistic Cardinality Estimation using ℓp-Norms of Degree Sequences 2025 SIGMOD 4.8799937e-05
7,017 Query Evaluation by Circuits 2022 PODS 4.8603097e-05
7,065 Fast Matrix Multiplication for Query Processing 2024 PODS 4.8447515e-05
7,126 Debunking the Myth of Join Ordering: Toward Robust SQL Analytics 2025 SIGMOD 4.8232367e-05
7,166 Ranked Enumeration of Join Queries with Projections 2022 VLDB 4.8124491e-05
7,332 The Complexity of Boolean Conjunctive Queries with Intersection Joins 2022 PODS 4.7606012e-05
7,344 Join Size Bounds using l_p-Norms on Degree Sequences 2024 PODS 4.7565607e-05
7,467 Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees 2025 SIGMOD 4.7218691e-05
7,579 A Nearly Instance-optimal Differentially Private Mechanism for Conjunctive Queries 2022 PODS 4.706055e-05
7,761 Space-Time Tradeoffs for Conjunctive Queries with Access Patterns 2023 PODS 4.658708e-05
8,159 Computing Complex Temporal Join Queries Efficiently 2022 SIGMOD 4.5729025e-05
8,437 Insert-Only versus Insert-Delete in Dynamic Query Evaluation 2024 PODS 4.5138778e-05
8,508 Minimally Factorizing the Provenance of Self-join Free Conjunctive Queries 2024 PODS 4.4952414e-05
8,589 Output-Optimal Algorithms for Join-Aggregate Queries 2025 PODS 4.4897014e-05
8,966 Output-sensitive Conjunctive Query Evaluation 2024 PODS 4.4193184e-05
9,744 Output-Sensitive Evaluation of Regular Path Queries 2025 PODS 4.2897489e-05
9,843 Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints 2025 PODS 4.2721228e-05
9,845 Path-centric Cardinality Estimation for Subgraph Matching 2025 VLDB 4.2721228e-05
9,940 Worst-Case-Optimal Similarity Joins on Graph Databases 2024 SIGMOD 4.2456408e-05
10,009 The Space-Time Complexity of Sum-Product Queries 2026 PODS 4.1945683e-05
10,149 CorrBound: Cardinality Estimation Accounting for Inter- and Intra-relation Correlations 2026 SIGMOD 4.1945683e-05
10,254 Secure Multi-Party Sampling over Joins 2026 VLDB 4.1945683e-05
10,284 FlowLog: Efficient and Extensible Datalog via Incrementality 2026 VLDB 4.1945683e-05
10,343 Circuit Bounds for Conjunctive Queries with Self-joins 2025 PODS 4.1945683e-05
10,347 Fast Matrix Multiplication meets the Submodular Width 2025 PODS 4.1945683e-05
10,898 Conjunctive Queries with Negation and Aggregation: A Linear Time Characterization 2024 PODS 4.1945683e-05
10,970 Relational Algorithms for Top-k Query Evaluation 2024 SIGMOD 4.1945683e-05
11,698 Tighter Upper Bounds for Join Cardinality Estimates 2018 SIGMOD 4.1945683e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
502 Worst-case Optimal Join Algorithms 2012 PODS 0.00021526612
583 FAQ: Questions Asked Frequently 2016 PODS 0.00019717214
1,259 Aggregation and Ordering in Factorised Databases 2013 VLDB 0.00012995821
1,328 Hypertree Decompositions: Questions and Answers 2016 PODS 0.00012565612
1,711 SCADS: Scale-Independent Storage for Social Computing Applications 2009 CIDR 0.0001080509
2,056 PIQL: Success-Tolerant Query Processing in the Cloud 2012 VLDB 9.6645763e-05
2,296 Joins via Geometric Resolutions: Worst-case and Beyond 2015 PODS 9.0776226e-05
2,936 Querying with Access Patterns and Integrity Constraints 2015 VLDB 7.8554347e-05
4,455 Generalized Scale Independence Through Incremental Precomputation 2013 SIGMOD 6.171182e-05
4,546 Bounded Conjunctive Queries 2014 VLDB 6.0987778e-05
6,824 Computing Join Queries with Functional Dependencies 2016 PODS 4.9144789e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
7,761 Space-Time Tradeoffs for Conjunctive Queries with Access Patterns 2023 PODS 4.658708e-05
6,949 Tree-Width and Functional Dependencies in Databases 2008 PODS 4.8898337e-05
4,546 Bounded Conjunctive Queries 2014 VLDB 6.0987778e-05
10,905 Tight Bounds of Circuits for Sum-Product Queries 2024 PODS 4.1945683e-05
3,006 On Functional Aggregate Queries with Additive Inequalities 2019 PODS 7.7299363e-05
10,001 A Unifying Algorithm for Hierarchical Queries 2026 PODS 4.1945683e-05
5,744 Size and Treewidth Bounds for Conjunctive Queries 2009 PODS 5.3441438e-05
10,347 Fast Matrix Multiplication meets the Submodular Width 2025 PODS 4.1945683e-05
3,775 Bag Query Containment and Information Theory 2020 PODS 6.775636e-05
9,843 Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints 2025 PODS 4.2721228e-05