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.9144789e-05
Overall Rank: 6,824 | 52.53%
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,442	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00011956109
3,511	Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs	2022	VLDB	7.0254052e-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
5,855	Optimal Join Algorithms Meet Top-k	2020	SIGMOD	5.3006096e-05
5,972	SafeBound: A Practical System for Generating Cardinality Bounds	2023	SIGMOD	5.2474768e-05
6,969	LpBound: Pessimistic Cardinality Estimation using ℓp-Norms of Degree Sequences	2025	SIGMOD	4.8799937e-05
7,344	Join Size Bounds using l_p-Norms on Degree Sequences	2024	PODS	4.7565607e-05
9,843	Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints	2025	PODS	4.2721228e-05
9,940	Worst-Case-Optimal Similarity Joins on Graph Databases	2024	SIGMOD	4.2456408e-05
10,149	CorrBound: Cardinality Estimation Accounting for Inter- and Intra-relation Correlations	2026	SIGMOD	4.1945683e-05
11,220	Lightweight Materialization for Fast Dashboards Over Joins	2023	SIGMOD	4.1945683e-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
502	Worst-case Optimal Join Algorithms	2012	PODS	0.00021526612
613	Design and Implementation of the LogicBlox System	2015	SIGMOD	0.00019181325
1,939	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD	0.00010025655
2,936	Querying with Access Patterns and Integrity Constraints	2015	VLDB	7.8554347e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
11,556	The Limits of Efficiency for Open- and Closed-World Query Evaluation Under Guarded TGDs	2020	PODS	4.1945683e-05
7,344	Join Size Bounds using l_p-Norms on Degree Sequences	2024	PODS	4.7565607e-05
8,589	Output-Optimal Algorithms for Join-Aggregate Queries	2025	PODS	4.4897014e-05
2,296	Joins via Geometric Resolutions: Worst-case and Beyond	2015	PODS	9.0776226e-05
8,028	Tight Fine-Grained Bounds for Direct Access on Join Queries	2022	PODS	4.6028646e-05
502	Worst-case Optimal Join Algorithms	2012	PODS	0.00021526612
6,949	Tree-Width and Functional Dependencies in Databases	2008	PODS	4.8898337e-05
9,843	Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints	2025	PODS	4.2721228e-05
8,966	Output-sensitive Conjunctive Query Evaluation	2024	PODS	4.4193184e-05
5,744	Size and Treewidth Bounds for Conjunctive Queries	2009	PODS	5.3441438e-05