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
1683
Venue
PODS
Year
2016
Pagerank
5.8070233e-05
Overall Rank
6,672 | 54.23%
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
321 Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems 2018 PODS 0.00021283186
1,109 What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? 2017 PODS 0.00012142685
2,745 Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries 2020 VLDB 8.1747954e-05
3,070 Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs 2022 VLDB 7.7900444e-05
3,457 Bag Query Containment and Information Theory 2020 PODS 7.3981641e-05
5,576 SafeBound: A Practical System for Generating Cardinality Bounds 2023 SIGMOD 6.1663946e-05
5,601 Optimal Join Algorithms Meet Top-k 2020 SIGMOD 6.1540123e-05
5,639 LpBound: Pessimistic Cardinality Estimation using ℓp-Norms of Degree Sequences 2025 SIGMOD 6.1385102e-05
6,257 Join Size Bounds using l_p-Norms on Degree Sequences 2024 PODS 5.9397944e-05
9,994 Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints 2025 PODS 5.1814573e-05
10,087 Worst-Case-Optimal Similarity Joins on Graph Databases 2024 SIGMOD 5.1558402e-05
10,160 Maintaining Queries under Updates Using Heavy-Light Partitioning of the Input Relations 2026 PODS 5.093636e-05
10,165 PANDAExpress: A Simpler and Faster PANDA Algorithm 2026 PODS 5.093636e-05
10,438 CorrBound: Cardinality Estimation Accounting for Inter- and Intra-relation Correlations 2026 SIGMOD 5.093636e-05
11,421 Lightweight Materialization for Fast Dashboards Over Joins 2023 SIGMOD 5.093636e-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
411 Worst-case Optimal Join Algorithms 2012 PODS 0.00018902089
490 Design and Implementation of the LogicBlox System 2015 SIGMOD 0.000175757
1,320 From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System 2015 SIGMOD 0.00011166426
2,947 Querying with Access Patterns and Integrity Constraints 2015 VLDB 7.9325276e-05
Previous Page 1 / 1 Next

Semantically Similar Papers