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.00011922523
Overall Rank
1,452 | 89.92%
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,143 Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities 2019 SIGMOD 9.4437798e-05
3,009 On Functional Aggregate Queries with Additive Inequalities 2019 PODS 7.7230513e-05
3,644 G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching 2020 SIGMOD 6.8842065e-05
3,702 Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries 2020 VLDB 6.8251643e-05
3,781 A Learned Sketch for Subgraph Counting 2021 SIGMOD 6.7691344e-05
3,782 Bag Query Containment and Information Theory 2020 PODS 6.7691169e-05
3,785 Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries 2020 PODS 6.7658346e-05
3,992 FactorJoin: A New Cardinality Estimation Framework for Join Queries 2023 SIGMOD 6.5519369e-05
4,709 Instance and Output Optimal Parallel Algorithms for Acyclic Joins 2019 PODS 5.9744219e-05
4,787 The Relational Data Borg is Learning 2020 VLDB 5.9168117e-05
5,085 Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins 2023 PODS 5.7040225e-05
5,503 Worst-Case Optimal Graph Joins in Almost No Space 2021 SIGMOD 5.4718854e-05
5,728 Conjunctive Queries with Comparisons 2022 SIGMOD 5.350072e-05
5,845 Optimal Join Algorithms Meet Top-k 2020 SIGMOD 5.3057391e-05
5,963 Beyond Equi-joins: Ranking, Enumeration and Factorization 2021 VLDB 5.2485815e-05
5,978 SafeBound: A Practical System for Generating Cardinality Bounds 2023 SIGMOD 5.2424396e-05
5,996 Evaluating Datalog over Semirings: A Grounding-based Approach 2024 PODS 5.2365238e-05
6,294 Free Join: Unifying Worst-Case Optimal and Traditional Joins 2023 SIGMOD 5.1202075e-05
6,625 Tractability Beyond beta-Acyclicity for Conjunctive Queries with Negation 2021 PODS 4.9841228e-05
6,967 LpBound: Pessimistic Cardinality Estimation using ℓp-Norms of Degree Sequences 2025 SIGMOD 4.875312e-05
7,017 Query Evaluation by Circuits 2022 PODS 4.8556471e-05
7,060 Fast Matrix Multiplication for Query Processing 2024 PODS 4.8401037e-05
7,122 Debunking the Myth of Join Ordering: Toward Robust SQL Analytics 2025 SIGMOD 4.8199209e-05
7,165 Ranked Enumeration of Join Queries with Projections 2022 VLDB 4.807833e-05
7,328 The Complexity of Boolean Conjunctive Queries with Intersection Joins 2022 PODS 4.7560344e-05
7,337 Join Size Bounds using l_p-Norms on Degree Sequences 2024 PODS 4.7532633e-05
7,441 Continual Observation of Joins under Differential Privacy 2024 SIGMOD 4.7251588e-05
7,465 Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees 2025 SIGMOD 4.7186055e-05
7,584 A Nearly Instance-optimal Differentially Private Mechanism for Conjunctive Queries 2022 PODS 4.7015411e-05
7,762 Space-Time Tradeoffs for Conjunctive Queries with Access Patterns 2023 PODS 4.6542406e-05
8,163 Computing Complex Temporal Join Queries Efficiently 2022 SIGMOD 4.5685178e-05
8,428 Insert-Only versus Insert-Delete in Dynamic Query Evaluation 2024 PODS 4.5095504e-05
8,506 Minimally Factorizing the Provenance of Self-join Free Conjunctive Queries 2024 PODS 4.4909322e-05
8,587 Output-Optimal Algorithms for Join-Aggregate Queries 2025 PODS 4.4853975e-05
8,972 Output-sensitive Conjunctive Query Evaluation 2024 PODS 4.4150824e-05
9,743 Output-Sensitive Evaluation of Regular Path Queries 2025 PODS 4.2856385e-05
9,843 Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints 2025 PODS 4.2680295e-05
9,845 Path-centric Cardinality Estimation for Subgraph Matching 2025 VLDB 4.2680295e-05
9,940 Worst-Case-Optimal Similarity Joins on Graph Databases 2024 SIGMOD 4.241573e-05
10,009 The Space-Time Complexity of Sum-Product Queries 2026 PODS 4.1905499e-05
10,149 CorrBound: Cardinality Estimation Accounting for Inter- and Intra-relation Correlations 2026 SIGMOD 4.1905499e-05
10,254 Secure Multi-Party Sampling over Joins 2026 VLDB 4.1905499e-05
10,296 FlowLog: Efficient and Extensible Datalog via Incrementality 2026 VLDB 4.1905499e-05
10,355 Circuit Bounds for Conjunctive Queries with Self-joins 2025 PODS 4.1905499e-05
10,359 Fast Matrix Multiplication meets the Submodular Width 2025 PODS 4.1905499e-05
10,902 Conjunctive Queries with Negation and Aggregation: A Linear Time Characterization 2024 PODS 4.1905499e-05
10,973 Relational Algorithms for Top-k Query Evaluation 2024 SIGMOD 4.1905499e-05
11,703 Tighter Upper Bounds for Join Cardinality Estimates 2018 SIGMOD 4.1905499e-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
503 Worst-case Optimal Join Algorithms 2012 PODS 0.00021517145
564 FAQ: Questions Asked Frequently 2016 PODS 0.00020002796
1,255 Aggregation and Ordering in Factorised Databases 2013 VLDB 0.00013011216
1,322 Hypertree Decompositions: Questions and Answers 2016 PODS 0.00012595941
1,706 SCADS: Scale-Independent Storage for Social Computing Applications 2009 CIDR 0.00010806188
2,062 PIQL: Success-Tolerant Query Processing in the Cloud 2012 VLDB 9.654149e-05
2,298 Joins via Geometric Resolutions: Worst-case and Beyond 2015 PODS 9.0746479e-05
2,942 Querying with Access Patterns and Integrity Constraints 2015 VLDB 7.8464054e-05
4,457 Generalized Scale Independence Through Incremental Precomputation 2013 SIGMOD 6.1636855e-05
4,545 Bounded Conjunctive Queries 2014 VLDB 6.0917464e-05
6,822 Computing Join Queries with Functional Dependencies 2016 PODS 4.9101655e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
7,337 Join Size Bounds using l_p-Norms on Degree Sequences 2024 PODS 4.7532633e-05
6,946 Tree-Width and Functional Dependencies in Databases 2008 PODS 4.8874695e-05
4,545 Bounded Conjunctive Queries 2014 VLDB 6.0917464e-05
10,909 Tight Bounds of Circuits for Sum-Product Queries 2024 PODS 4.1905499e-05
3,009 On Functional Aggregate Queries with Additive Inequalities 2019 PODS 7.7230513e-05
10,000 A Unifying Algorithm for Hierarchical Queries 2026 PODS 4.1905499e-05
5,752 Size and Treewidth Bounds for Conjunctive Queries 2009 PODS 5.3393414e-05
10,359 Fast Matrix Multiplication meets the Submodular Width 2025 PODS 4.1905499e-05
3,782 Bag Query Containment and Information Theory 2020 PODS 6.7691169e-05
9,843 Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints 2025 PODS 4.2680295e-05