In relational database design, normalization theory is fundamental to reducing data redundancy and avoiding update anomalies. However, identifying all keys and prime attributes—a critical step in normalization—has long been known to be computationally challenging. Previous research established that when the normal form of a relation scheme is unknown, the prime attribute problem is NP-complete, and the maximum number of keys grows exponentially with the number of attributes.
Now, a research team led by Professor Liu Guohua from Donghua University has focused specifically on relation schemes in second normal form (2NF). While any scheme in Boyce-Codd normal form (BCNF) or third normal form (3NF) inherently satisfies 2NF requirements, 2NF itself serves as a foundational stage in normalization. The team’s work provides systematic investigation of prime attributes and key-related problems specifically for 2NF.
The researchers first present a necessary condition and a sufficient condition for determining whether a relation scheme is in 2NF, based on analyzing the distribution of functional dependency (FD) sets. They then demonstrate a critical finding: even when a relation scheme is known to be in 2NF, new keys can be generated by replacing attributes in an existing key with the left-hand sides of specific FDs, and the total number of all keys can grow exponentially with both the number of attributes and the number of functional dependencies. In a worst-case scenario, the number of keys can reach 1+(
m−1)
(s−log2m)×(m−1), where
m is the number of FDs and
s is the number of attributes.
Based on this theoretical insight, the team proposes a constructive procedure to enumerate all keys of a relation scheme in 2NF. Although the algorithm’s time complexity is exponential, it serves as a baseline for enumeration and demonstrates that listing all keys remains a cumbersome task even under the 2NF constraint.
Most importantly, the study proves that the prime attribute problem—determining whether a given attribute appears in at least one candidate key—remains
NP-complete even when the relation scheme is known to be in 2NF. This result extends the classic NP-completeness proof by Lucchesi and Osborn (1978) to the 2NF case, closing a significant gap in database normalization theory.
This research not only deepens the theoretical understanding of the computational complexity inherent in 2NF normalization but also provides practical guidance for database designers. The work entitled “
Investigating Problems Related to Prime Attributes and All Keys in 2NF”
was published in
Journal of Donghua University (English Edition) (published in Issue 02, 2026).
DOI: 10.19884/j.1672-5220.202504008