Features of Prime Attributes in a Relation Scheme

Abstract

Normal forms have a significant role in the theory of relational database normalization.The definitions of normal forms are established through the functional dependency (FD) relationship between a prime or nonprime attribute and a key.However, determining whether an attribute is a prime attribute is a nondeterministic polynomial-time complete (NP-complete) problem, making it intractable to determine if a relation scheme is in a specific normal form.While the prime attribute problem is generally NP-complete, there are cases where identifying prime attributes is not challenging.In a relation scheme R(U,F), we partition U into four distinct subsets based on where attributes in U appear in F:U1 (attributes only appearing on the left-hand side of FDs), U2 (attributes only appearing on the right-hand side of FDs), U3 (attributes appearing on both sides of FDs), and U4 (attributes not present in F).Next, we demonstrate the necessary and sufficient conditions for a key to be the unique key of a relation scheme.Subsequently, we illustrate the features of prime attributes in U3 and generalize the features of common prime attributes.The findings lay the groundwork for distinguishing between complex and simple cases in prime attribute identification, thereby deepening the understanding of this problem.

Keywords

normalization / key / prime attribute / nonprime attribute

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 L, OSBORN S L. Candidate keys for relations[J]. Journal of Computer and System Sciences, 1978, 17(2): 270-279.

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

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

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

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

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

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

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

[12] NAKOS V, NGO H Q, TSOURAKAKIS C E. Targeted least cardinality candidate key for relational databases[EB/OL]. (2024-08-24)[2025-04-05]. https://arxiv.org/abs/2408.13540vl.

[13] 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, Portland, Oregon, USA. New York: ACM, 1985: 189-192.

[14] 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, Philadelphia, Pennsylvania, USA. New York: ACM, 1989: 128-133.

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

[16] CODD E F. A relational model of data for large shared data banks[J]. Communications of the ACM, 1970, 13(6): 377-387.

[17] BEERI C, BERNSTEIN P A, GOODMAN N. .A sophisticate’s introduction to database normalization theory[M]//Readings in artificial intelligence and databases. San Francisco: Morgan Kaufmann, 1989: 468-479.

[18] HODEL R E. An introduction to mathematical logic[M]. New York: Dover Publication, 2013.

[19] ARMSTRONG W W.Dependency structures of data base relationships[C]//Information Processing 74. Amsterdam: North-Holland, 1974: 580-583.

[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] MAIER D. Minimum covers in relational database model[J]. Journal of the ACM, 1980, 27(4): 664-674.

[22] JOU J H, FISCHER P C. The complexity of recognizing 3NF relation schemes[J]. Information Processing Letters, 1982, 14 (4): 187-190.

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

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