Computing Join Queries with Functional Dependencies

Summary: Algorithm that computes joins with functional dependencies within the GLVV polymatroid output-size bound up to polylog factors, achieving worst-case optimality when GLVV is tight. Extends GLVV via the lattice of FD-closed sets, proves tightness on distributive lattices, handles degree/cardinality bounds, and turns polymatroid proofs into algorithms. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1684
Venue: PODS
Year: 2016
Pagerank: 4.9101655e-05
Overall Rank: 6,822 | 52.59%
DOI: 10.1145/2902251.2902289

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,452	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00011922523
3,516	Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs	2022	VLDB	7.018912e-05
3,702	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	6.8251643e-05
3,782	Bag Query Containment and Information Theory	2020	PODS	6.7691169e-05
5,845	Optimal Join Algorithms Meet Top-k	2020	SIGMOD	5.3057391e-05
5,978	SafeBound: A Practical System for Generating Cardinality Bounds	2023	SIGMOD	5.2424396e-05
6,967	LpBound: Pessimistic Cardinality Estimation using ℓp-Norms of Degree Sequences	2025	SIGMOD	4.875312e-05
7,337	Join Size Bounds using l_p-Norms on Degree Sequences	2024	PODS	4.7532633e-05
9,843	Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints	2025	PODS	4.2680295e-05
9,940	Worst-Case-Optimal Similarity Joins on Graph Databases	2024	SIGMOD	4.241573e-05
10,149	CorrBound: Cardinality Estimation Accounting for Inter- and Intra-relation Correlations	2026	SIGMOD	4.1905499e-05
11,222	Lightweight Materialization for Fast Dashboards Over Joins	2023	SIGMOD	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 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
610	Design and Implementation of the LogicBlox System	2015	SIGMOD	0.00019204048
1,938	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD	0.00010025547
2,942	Querying with Access Patterns and Integrity Constraints	2015	VLDB	7.8464054e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
11,560	The Limits of Efficiency for Open- and Closed-World Query Evaluation Under Guarded TGDs	2020	PODS	4.1905499e-05
7,337	Join Size Bounds using l_p-Norms on Degree Sequences	2024	PODS	4.7532633e-05
8,587	Output-Optimal Algorithms for Join-Aggregate Queries	2025	PODS	4.4853975e-05
2,298	Joins via Geometric Resolutions: Worst-case and Beyond	2015	PODS	9.0746479e-05
8,029	Tight Fine-Grained Bounds for Direct Access on Join Queries	2022	PODS	4.598451e-05
503	Worst-case Optimal Join Algorithms	2012	PODS	0.00021517145
6,946	Tree-Width and Functional Dependencies in Databases	2008	PODS	4.8874695e-05
9,843	Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints	2025	PODS	4.2680295e-05
8,972	Output-sensitive Conjunctive Query Evaluation	2024	PODS	4.4150824e-05
5,752	Size and Treewidth Bounds for Conjunctive Queries	2009	PODS	5.3393414e-05