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: 735
Venue: PODS
Year: 1985
Pagerank: 5.5240911e-05
Overall Rank: 5,408 | 62.38%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Sukhamay Kundu

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,781	Practical algorithms for finding prime attributes and testing normal forms	1989	PODS	5.3298267e-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	Pagerank
1,320	The Size of Projections of Relations Satisfying a Functional Dependency	1982	VLDB	0.0001261772
3,823	Automatic Discovery of Attributes in Relational Databases	2011	SIGMOD	6.7261168e-05
8,445	Finding Candidate Keys For Relational Data Bases	1975	SIGMOD	4.5109131e-05
441	Computing Joins Of Relations	1975	SIGMOD	0.00023058395
702	Reasoning about Record Matching Rules	2009	VLDB	0.00017918203
25	Dependency Inference (Extended Abstract)	1987	VLDB	0.00083101742
12,925	Polynomial Time Designs toward Both BCNF and Efficient Data Manipulation	1990	SIGMOD	4.1945683e-05
10,587	Efficient Discovery of Relaxed Functional Dependencies	2025	VLDB	4.1945683e-05
9,725	On Concise Set of Relative Candidate Keys	2014	VLDB	4.2945121e-05
6,686	An Algorithm For Servicing Multi-Relational Queries	1977	SIGMOD	4.9624102e-05