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)

Paper ID: 734
Venue: PODS
Year: 1985
Pagerank: 5.8149777e-05
Overall Rank: 6,645 | 54.42%
DOI: 10.1145/325405.325431

Incoming Non-self Citations Over Time

Authors

1. Sukhamay Kundu (Louisiana State University)

BibTeX Citation

@inproceedings{kundu_pods85,
        address = {New York, NY, USA},
        series = {{PODS} '85},
        title = {{An Improved Algorithm for Finding a Key of a Relation}},
        url = {https://dl.acm.org/doi/10.1145/325405.325431},
        doi = {10.1145/325405.325431},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Kundu, Sukhamay},
        year = {1985}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,798	Practical algorithms for finding prime attributes and testing normal forms	1989	PODS	5.7707336e-05

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

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,894	The Size of Projections of Relations Satisfying a Functional Dependency	1982	VLDB
2	3,456	Automatic Discovery of Attributes in Relational Databases	2011	SIGMOD
3	1,479	Computing Joins Of Relations	1975	SIGMOD
4	8,654	Finding Candidate Keys For Relational Data Bases	1975	SIGMOD
5	203	Dependency Inference	1987	VLDB
6	619	Reasoning about Record Matching Rules	2009	VLDB
7	13,120	Polynomial Time Designs toward Both BCNF and Efficient Data Manipulation	1990	SIGMOD
8	10,848	Efficient Discovery of Relaxed Functional Dependencies	2025	VLDB
9	9,883	On Concise Set of Relative Candidate Keys	2014	VLDB
10	7,120	An Algorithm For Servicing Multi-Relational Queries	1977	SIGMOD