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 att...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:U_(1)(attributes only appearing on the left-hand side of FDs),U_(2)(attributes only appearing on the right-hand side of FDs),U_(3)(attributes appearing on both sides of FDs),and U_(4)(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 U_(3) 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.展开更多
文摘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:U_(1)(attributes only appearing on the left-hand side of FDs),U_(2)(attributes only appearing on the right-hand side of FDs),U_(3)(attributes appearing on both sides of FDs),and U_(4)(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 U_(3) 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.
