Recognizing Prime Attributes Based on F-based Derivation Tree

Abstract

Although the prime attribute problem is nondeterministic polynomial-time complete (NP-complete), the difficulty of determining whether an attribute is prime is related to how the attribute appears in the set of functional dependencies (FDs). The prime attribute problem is extensively studied based on the occurrence of an attribute in the set of FDs. First, in a relation scheme R(U, F), the attribute set U is partitioned into four distinct subsets according to where attributes in U appear in F: U₁ (attributes appearing exclusively on the left-hand sides of FDs in F), U₂ (attributes appearing exclusively on the right-hand sides of FDs in F), U₃ (attributes appearing on both sides of FDs in F), and U₄ (attributes not appearing in any FD in F). Second, the occurrence patterns of attributes in the set of FDs are mapped to an F-based derivation tree (F-based DT) forest, and the features of attributes in U₁, U₂, U₃ or U₄ are shown in the F-based DT forest. Then, an algorithm for recognizing prime attributes based on F-based DT is proposed. Finally, the following conclusions are obtained: when an attribute belongs to U₃, the prime attribute problem is NP-complete; when an attribute belongs to U₁, U₂, or U₄, the problem is in polynomial-time complexity class (P-class), meaning it can be efficiently solved in polynomial time. Compared with traditional methods, the proposed algorithm can simplify the process for recognizing prime attributes significantly, and improve database normalization.

Keywords

F-based derivation tree / prime attribute / NP-complete / normalization

References

[1] Lucchesi C L, Osborn S L. Candidate keys for relations[J]. Journal of Computer and System Sciences, 1978, 17(2): 270-279.

[2] Cordero P, Enciso M, Mora A. Automated reasoning to infer all minimal keys[C]// IJCAI. Palo Alto: IJCAI, 2013: 817-823.

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

[4] Demetrovics J, Thi V D. Relations and minimal keys[J]. Acta Cybernetica, 1988, 8(3): 279-285.

[5] 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.

[6] 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.

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

[8] Hao Z X, Liu G H. An algorithm to find out all candidate keys of relation scheme[J]. Chinese Journal of Computers, 1991, 14(4): 300-307. (in Chinese)

[9] 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.

[10] 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.

[11] Saiedian H, Spencer T. An efficient algorithm to compute the candidate keys of a relational database scheme[J]. The Computer Journal, 1996, 39(2): 124-132.

[12] Wastl R. Linear derivations for keys of a database relation scheme[J]. Journal of Universal Computer Science, 1998, 4(11): 883-897.

[13] 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.

[14] Liu G H, Hao Z X, Chen Z J. A quick replacing algorithm for finding all candidate keys of a relation scheme[J]. Chinese Journal of Computers, 1998, 21(10): 890-895. (in Chinese)

[15] Hao Z X, Guo J F. A hypergraph—based method for finding out all candidate keywords in relational schemes[J]. Chinese Journal of Computers, 1992, 15(4): 264-270. (in Chinese)

[16] 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)

[17] Bahmani A H, Naghibzadeh M, Bahmani B. Automatic database normalization and primary key generation[C]// Canadian Conference on Electrical and Computer Engineering (CCECE). Piscataway, NJ: IEEE, 2008: 11-16.

[18] Bordoloi S, Kalita B. Designing graph database models from existing relational databases[J]. International Journal of Computer Applications, 2013, 74(1): 25-31.

[19] 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.

[20] 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.

[21] Hodel R E. An introduction to mathematical logic[M]. New York: Dover Publications, 2013.

[22] Nakos V, Ngo H Q, Tsourakakis C E. Targeted least cardinality candidate key for relational databases[PP/OL]. arXiv(2024—08—24)[2025—03—21]. https://arxiv.org/abs/2408.13540.