Investigating Problems Related to Prime Attributes and All Keys in 2NF

Abstract

In relational database normalization theory, identifying all keys and prime attributes is essential yet highly challenging. It has been shown that the prime attribute problem is nondeterministic polynomial-time complete (NP-complete). Additionally, the maximum number of keys in a relation scheme is exponential in the number of attributes. These conclusions hold when the normal form is unknown, and when the normal form is known they may change. For instance, when a relation scheme is in Boyce-Codd normal form (BCNF), the prime attribute problem falls within the polynomial-time complexity class (P-class), and listing all keys becomes less cumbersome. In the realm of normalization, second normal form (2NF) serves as a foundational stage, and any scheme that is in BCNF or third normal form (3NF) inherently satisfies the requirements of 2NF. Therefore, this paper focuses on the problems related to the prime attribute and all keys for 2NF. First, we present a necessary condition and a sufficient condition for a relation scheme to be in 2NF. Then, we demonstrate that the maximum number of keys is exponential in the number of attributes and functional dependencies of a relation scheme in 2NF. Furthermore, we propose an algorithm for finding all keys of a relation scheme in 2NF. Finally, we demonstrate that the prime attribute problem remains NP-complete in 2NF. This study deepens the theoretical understanding of the computational complexity inherent in 2NF normalization and provides practical references for database scheme design.

Keywords

prime attribute / key / NP-complete / normalization / second normal form (2NF)

References

[1] CODD E F . Further normalization of the data base relational model[J]. Data Base Systems, 1972, 6 (1972): 33—64.

[2] CODD E F . Recent investigations in relational data base systems[M]. New York: IBM Thomas J. Watson Research Division, 1974.

[3] DEMETROVICS J. On the number of candidate keys[J]. Information Processing Letters, 1978, 7 (6): 266—269.

[4] LUCCHESI C , OSBORN S L . Candidate keys for relations[J]. Journal of Computer and System Sciences, 1978, 17 (2): 270—279.

[5] BEERI C , BERNSTEIN P A . Computational problems related to the design of normal form relational schemas[J]. ACM Transactions on Database Systems, 1979, 4 (1): 30—59.

[6] KUNDU S. An improved algorithm for finding a key of a relation[C]// Proceedings of the Fourth ACM SIGACT—SIGMOD Symposium on Principles of Database Systems. New York: ACM, 1985: 189—192.

[7] MANNILA H , RAIHA K J . Practical algorithms for finding prime attributes and testing normal forms[C]// Proceedings of the Eighth ACM SIGACT—SIGMOD—SIGART Symposium on Principles of Database Systems. New York: ACM, 1989: 128—133.

[8] MAIER D. Minimum covers in the relational database model (extended abstract)[C]// Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing. New York: ACM, 1979: 330—337.

[9] OSBORN S L . Testing for existence of a covering Boyce—Codd normal form[J]. Information Processing Letters, 1979, 8 (1): 11—14.

[10] XU Y L , LIU G H , YU X X , et al. Features of prime attributes in a relation scheme[J]. Journal of Donghua University (English Edition), 2025, 42 (6): 689—698.

[11] CORDERO P , ENCISO M , MORA A . Automated reasoning to infer all minimal keys[C]// IJCAI. Palo Alto: IJCAI, 2013: 817—823.

[12] DEMBA M. KeyFinder: an efficient minimal keys finding algorithm for relational databases[J]. Inteligencia Artificial, 2021, 24 (68): 37—52.

[13] DEMETROVICS J , THI V D . Relations and minimal keys[J]. Acta Cybernetica, 1988, 8 (3): 279—285.

[14] FERNANDEZ M , VARGA J . Finding candidate keys and 3NF via strategic port graph rewriting[C]// Proceedings of the 22nd International Symposium on Principles and Practice of Declarative Programming. New York: ACM, 2020: 1—14.

[15] FADOUS R , FORSYTH J . Finding candidate keys for relational data bases[C]// Proceedings of the 1975 ACM SIGMOD International Conference on Management of Data. New York: ACM, 1975: 203—210.

[16] FENG Y C . Algorithm for solving candidate key by graph theory[J]. Chinese Journal of Computers, 1988, 11 (9): 556—558. (in Chinese)

[17] HAO Z X , LIU G H . An algorithm to find out all candidate keys of relation schema[J]. Chinese Journal of Computers, 1991, 14 (4): 300—307. (in Chinese)

[18] SAIEDIAN H , SPENCER T . An efficient algorithm to compute the candidate keys of a relational database schema[J]. The Computer Journal, 1996, 39 (2): 124—132.

[19] WASTL R. Linear derivations for keys of a database relation schema[J]. Journal of Universal Computer Science, 1998, 4 (11): 883—897.

[20] YU C T , JOHNSON D T . On the complexity of finding the set of candidate keys for a given set of functional dependencies[J]. Information Processing Letters, 1976, 5 (4): 100—101.

[21] LIU G H , HAO Z X , CHEN Z J . A quick replacement algorithm for finding all candidate keys of a relation scheme[J]. Chinese Journal of Computers, 1998, 21 (10): 890—895. (in Chinese)

[22] HAO Z X , GUO J F . A hypergraph based method for finding out all candidate keys of relation schema[J]. Chinese Journal of Computers, 1992, 15 (4): 264—270. (in Chinese)

[23] HAO Z X , LIU G H , LIU C L . A method for finding all candidate keys of relational schema based on attributes relative table[J]. Journal of Computer Research and Development, 1994, 31 (6): 6—13. (in Chinese)

[24] FENG Y C , PANG C Y . Algorithm for finding candidate key word[J]. Journal of Huazhong University of Science and Technology (Natural Science Edition), 1986, 14 (5): 655—658. (in Chinese)

[25] BAHMANI A H , NAGHIBZADEH M , BAHMANI B . Automatic database normalization and primary key generation[C]// 2008 Canadian Conference on Electrical and Computer Engineering. New York: IEEE, 2008: 000011—000016.

[26] BORDOLOI S , KALITA B . Designing graph database models from existing relational databases[J]. International Journal of Computer Applications, 2013, 74 (1): 25—31.

[27] NAKOS V , NGO H Q , TSOURAKAKIS C E . Targeted least cardinality candidate key for relational databases[EB/OL]. (2024—08—24)[2025—01—20]. https://arxiv.org/pdf/2408.13540.