DBScholar

Back to papers

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
h7d0244470713cf92
Venue
PODS
Year
2016
Pagerank
5.6917027e-05
Overall Rank
6,739 | 54.70%
DOI
10.1145/2902251.2902289

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{khamis_pods16,
        address = {New York, NY, USA},
        series = {{PODS} '16},
        title = {{Computing Join Queries with Functional Dependencies}},
        url = {https://dl.acm.org/doi/10.1145/2902251.2902289},
        doi = {10.1145/2902251.2902289},
        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 = {2016}
}

Incoming Citations (Sorted by Pagerank)

Showing 15 of 15 citing papers.

Rank Citing Paper Year Venue Pagerank
315 Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems 2018 PODS 0.00021246
1,091 What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? 2017 PODS 0.00012074152
2,591 Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries 2020 VLDB 8.2468757e-05
2,974 Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs 2022 VLDB 7.7938744e-05
3,526 Bag Query Containment and Information Theory 2020 PODS 7.2321894e-05
4,752 Optimal Join Algorithms Meet Top-k 2020 SIGMOD 6.434561e-05
4,852 LpBound: Pessimistic Cardinality Estimation using ℓp-Norms of Degree Sequences 2025 SIGMOD 6.3806134e-05
5,219 SafeBound: A Practical System for Generating Cardinality Bounds 2023 SIGMOD 6.222726e-05
5,918 Join Size Bounds using l_p-Norms on Degree Sequences 2024 PODS 5.9481539e-05
10,182 Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints 2025 PODS 5.0651993e-05
10,301 Worst-Case-Optimal Similarity Joins on Graph Databases 2024 SIGMOD 5.040157e-05
10,377 Maintaining Queries under Updates Using Heavy-Light Partitioning of the Input Relations 2026 PODS 4.9793485e-05
10,382 PANDAExpress: A Simpler and Faster PANDA Algorithm 2026 PODS 4.9793485e-05
10,627 CorrBound: Cardinality Estimation Accounting for Inter- and Intra-relation Correlations 2026 SIGMOD 4.9793485e-05
11,735 Lightweight Materialization for Fast Dashboards Over Joins 2023 SIGMOD 4.9793485e-05
Previous Page 1 / 1 Next

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
402 Worst-case Optimal Join Algorithms 2012 PODS 0.00019104625
466 Design and Implementation of the LogicBlox System 2015 SIGMOD 0.00017773029
1,292 From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System 2015 SIGMOD 0.00011152286
3,000 Querying with Access Patterns and Integrity Constraints 2015 VLDB 7.7669839e-05
Previous Page 1 / 1 Next

Semantically Similar Papers