An Improved Algorithm for Finding a Key of a Relation
Summary: Algorithm computes a key of relation R(A) in O(|K|·|F|) time (|K| = output key size, |F| = FD input length), improving over prior O(|A|·|F|) bounds. Significant when key is much smaller than the attribute set, giving order‑of‑magnitude speedups. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
Incoming Citations (Sorted by Pagerank)
Showing 1 of 1 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 5,791 | Practical algorithms for finding prime attributes and testing normal forms | 1989 | PODS | 5.3247079e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 0 of 0 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 1,310 | The Size of Projections of Relations Satisfying a Functional Dependency | 1982 | VLDB | 0.000126534 |
| 3,826 | Automatic Discovery of Attributes in Relational Databases | 2011 | SIGMOD | 6.7204879e-05 |
| 445 | Computing Joins Of Relations | 1975 | SIGMOD | 0.00023029279 |
| 8,437 | Finding Candidate Keys For Relational Data Bases | 1975 | SIGMOD | 4.5065883e-05 |
| 25 | Dependency Inference (Extended Abstract) | 1987 | VLDB | 0.00083070519 |
| 700 | Reasoning about Record Matching Rules | 2009 | VLDB | 0.00017927576 |
| 12,935 | Polynomial Time Designs toward Both BCNF and Efficient Data Manipulation | 1990 | SIGMOD | 4.1905499e-05 |
| 10,595 | Efficient Discovery of Relaxed Functional Dependencies | 2025 | VLDB | 4.1905499e-05 |
| 9,724 | On Concise Set of Relative Candidate Keys | 2014 | VLDB | 4.2903967e-05 |
| 6,743 | An Algorithm For Servicing Multi-Relational Queries | 1977 | SIGMOD | 4.9383908e-05 |