8

I am working through an example problem in which we are trying to identify which of the following relations is in Third Normal Form (3NF). Here are the relations we are given:

R1(ABCD)
ACD -> B   AC -> D   D -> C   AC -> B

R2(ABCD)
AB -> C   ABD -> C   ABC -> D   AC -> D

R3(ABCD)
C -> B   A -> B   CD -> A   BCD -> A

R4(ABCD)
C -> B   B -> A   AC -> D   AC -> B

I know the answer is R1 is in 3NF, but I'm having a hard time understanding the steps to go about determining what violates 3NF. Can someone break it down in plain English for each of the relations? It would be extremely helpful if you can show me in steps how each relation might violate one of the 3NF rules:

  1. X -> A, then A is a subset of X
  2. X is a superkey
  3. A is a part of some key for R

For R1, the first step I take is breaking it down into closures:

ACD+ = ABCD
AC+ = ABCD
D+ = C

ACD and AC are superkeys, which satisfy rule 2.
1. D -> C, but C is not a subset of D. Rule 1 violated.
2. D is not a superkey. Rule 2 is violated.
3. C is a part of some key for R. C is a part of AC and ACD. So, rule 3 is upheld?

Not sure if I'm even doing these steps right, so please break it down as simple as possible for someone struggling with these concepts. Thanks.

raphnguyen
  • 3,565
  • 18
  • 56
  • 74
  • 1
    ACD is a superkey, but it's not an irreducible superkey. It's not a candidate key. The normal forms require you to first determine *all* the candidate keys, because the normal forms are defined (explicitly or implicitly) by functional dependencies and candidate keys. For example, 2NF requires that be no partial-key dependencies. That means you have to be able to distinguish prime attributes (attributes that are part of any candidate key) and nonprime attributes. There are two candidate keys in R1. AC is one of them. ACD is not the other one. – Mike Sherrill 'Cat Recall' Jul 05 '13 at 18:08
  • 2
    In plain English, it's about being dependent on the key, the whole key, and nothing but the key, so help me Codd. – Joe May 16 '15 at 18:03
  • None of this is in plain English. Fail, all of you! – Ken Netherland Mar 27 '23 at 22:06

4 Answers4

20

The best definition I've found for a relation that is in third normal form (3NF) is the following: 

A relation schema R is in 3NF if, whenever a function dependency X -> A holds in R, either
    (a) X is a superkey of R, or
    (b) A is a prime attribute of R.

Now there are three definitions that need clarification, key,superkey, and prime attribute.

For the definitions we will use examples from the R1 relation to describe them:

R1(ABCD)
ACD -> B   AC -> D   D -> C   AC -> B

key: A key is the attribute that determines every attribute of the relation. In other words, it is the set of attributes that will give you all the other attributes of the relation that are not in the set. In relation R1 of the above example, the keys are AC and AD. Why is AC a key? Because by knowing attributes A and C you can determine the remaining attributes, B and D. Why is AD a key? The same reason. A and D will ultimately determine B and C.

superkey: A superkey is basically a superset of a key. A superkey will contain the key always and potentially more attributes. In the previous example, AC is a key. Thus AC, ACD, ACB, etc. are superkeys. Note that a key itself is a superkey.

prime attribute: A prime attribute is basically an attribute that is part of a key. Thus A and C are prime attributes as they are part of the key AC. Take note however, the difference between a key and superkey. For the super key ACB, B is not a prime attribute since B is not part of the key. Just think of a prime attribute as a subset of a key.

Now let's look at the four relations:

R1(ABCD)
ACD -> B   AC -> D   D -> C   AC -> B

R2(ABCD)
AB -> C   ABD -> C   ABC -> D   AC -> D

R3(ABCD)
C -> B   A -> B   CD -> A   BCD -> A

R4(ABCD)
C -> B   B -> A   AC -> D   AC -> B

For each relation we will write down the keys and the prime attributes. Then we will see if the definition is satisfied.

R1:
keys: AC, AD
prime attributes: A, C, D

ACD -> B: Left side is a superkey. Satisfies (a).

AC -> D: Left side is a key and thus a superkey. Satisfies (a).

D -> C: Left side is not a superkey. Does not satisfy (a). However, right side is a prime attribute. Satisfies (b).

AC -> B: Left side is a key. Satisfies (a).

Either (a) or (b) is satisfied in all cases. Thus R1 is in 3NF.

R2:
keys: AB
prime attributes: A, B

AB -> C: Left side is a key and thus a superkey. Satisfies (a).  

ABD -> C: Left side is a superkey. Satisfies (a).

ABC -> D: Left side is a superkey. Satisfies (a).

AC -> D: Left side is not a superkey. Does not satisfy (a). Right side is not a prime attribute. Does not satisfy (b).

Since (a) or (b) is not satisfied in all cases, R2 is not in 3NF.

R3:
keys: CD, 
prime attributes: C, D

C -> B: Left side is not a superkey. Does not satisfy (a). Right side is not a prime attribute. Does not satisfy (b).

Since we have already found a case that does not satisfy either (a) or (b), we can immediately conclude that R3 is not in 3NF.

R4:
keys: C
prime attributes: C

C -> B: Left side is a key and thus a superkey. Satisfies (a).  

B -> A: Left side is not a superkey. Does not satisfy (a). Right side is not a prime attribute. Does not satisfy (b).

Again, we can stop here as the second case satisfies neither (a) nor (b). The relation R4 is not in 3NF.

Mars
  • 4,677
  • 8
  • 43
  • 65
  • That is not a correct definition of 3NF. Also, the definition addresses *all* FDs that hold, but you are only checking some. Also the question can't be answered unless we are given a cover for the FDs that hold. – philipxy Nov 16 '19 at 04:37
0

A simplified expression of 3NF is "A relation is in 3NF if every attribute transitively dependent on a key is a key attribute."1 A key attribute is an attribute that's part of any candidate key.

R3 is one of the simpler ones to analyze with respect to 3NF.

R3(ABCD)

  • C -> B
  • A -> B
  • CD -> A
  • BCD -> A

The only candidate key is CD.

  • Is there a transitive dependency? Yes, there is: CD->A, and A->B. B is transitively dependent on the key.
  • Is B a key attribute? No, it's not; CD is the only key.

So R3 is not in 3NF.

R4 is similar. C is the only candidate key.

  • Is there a transitive dependency? Yes, there is: C->B, and B->A.
  • Is A a key attribute? No, it's not; C is the only key.

So R4 is not in 3NF.

In R1, the candidate keys are AC and AD.

  • Is there a transitive dependency? Yes, there is: AC->D, and D->C.
  • Is C a key attribute? Yes, it is.

So R1 is in 3NF.

  1. "A New Normal Form for the Design of Relational Schemata", Carlo Zaniolo, in ACM Transactions on Database Systems, Vol. 7, No. 3, September 1982, p 492. More recent work uses prime attribute to refer to attributes that are part of any candidate key and non-prime attribute to refer to attributes that are not part of any candidate key.
Mike Sherrill 'Cat Recall'
  • 91,602
  • 17
  • 122
  • 185
0

Let me explain in simple words:

For the given relation, R1(ABCD),the functional dependencies are:

ACD -> B

AC -> D

D -> C

AC -> B

Condition to be in 3NF

X->Y here X is a Super key when Y is non-prime attribute else it can be any attribute

Prime attributes are the attributes which belongs to the super key

Non-prime attributes are the attributes which do not belongs to the super key

Let us come back to relation R1,

AC+=ABCD

AD+=ABCD

ACD+=ABCD and

D+=DC

Thus,we get AD,AC,ACD as our Super keys

And A,C,D are prime attributes and B is a non-prime attributes

ACD->B

This Functional dependency is in 3NF as ACD is a super key and B is prime attribute

AC->D

This Functional dependency is also in 3NF as AC is a super key and D is prime attribute

D->C

This Functional dependency is also in 3NF as D is a prime attribute and C is also prime attribute

AC->B

This Functional dependency is also in 3NF as AC is a super key and B is non-prime attribute

  Thus,the relation is not in 3NF only when non-prime attributes
  does not depend on super key

Hope,this helps!

Lordferrous
  • 678
  • 8
  • 8
-1

In simple english, here are the 3 Normal Forms:

1NF: The existence of "the key" ensures that the table is in 1NF(Key must be there).

2NF:It is required that "each" non-key attributes be dependent on "the whole key" to ensure 2NF.

3NF: further requiring that "each" non-key attributes be dependent on "nothing but the key" ensures 3NF.

Now, for this:

R1(ABCD) ACD -> B   AC -> D   D -> C   AC -> B

Look at these ACD -> B and AC -> B: clearly violates the 2NF condition. Forget 3NF, this relation is not even in 2NF. "the whole key"-->concept does not hold.

I think, you have proved the same using SET.

Mayukh Roy
  • 1,815
  • 3
  • 19
  • 31
  • There's only one non-prime attribute in R1 (B), and it's dependent on the whole key (AC). Maybe I don't understand what you're getting at. – Mike Sherrill 'Cat Recall' Mar 04 '13 at 12:45
  • B is a non key attribute and to be in 2NF, it must be dependent on the whole key. If (ACD) is a whole key, and ACD->B holds, AC->B relation violates: "each non-key attributes be dependent on "the whole key(ACD)", not the part of key(AC), to ensure 2NF".. Is there anything wrong as per my understanding, it will be great if you share. – Mayukh Roy Mar 04 '13 at 13:00
  • ACD isn't a key in R1; AC is. (AC is *one* of the keys.) – Mike Sherrill 'Cat Recall' Mar 04 '13 at 13:03