Tuesday, 2 February 2016

Normalization solved exercise 6



Set of solved exercises in Normalization / Normalization Solved Examples / How to find candidate keys, and primary keys in database? / Sets of examples to find the keys of a tables / Process of Key finding in a database – Examples / Normalization to BCNF.


Question:

Consider a relation R(A, B, C, D, E) with FDs AB C, AC B, BC A, D E.
Determine all the keys of relation R. Is the relation R in BCNF?

Solution:

The closure of AB, or AC, or BC is ABC. The attributes D and E are left alone. To include them we need to include the determinant D of D E with other FDs determinants to form candidate keys as follows;

The closure of ABD, i.e., (ABD)+ = ABCDE. [Derived from AB C and D E]. This shows that ABD is one of the keys.

The closure of ACD, i.e., (ACD)+ = ABCDE. [Derived from AC B and D E]. This shows that ACD is one of the keys.

The closure of BCD, i.e., (BCD)+ = ABCDE. [Derived from BC A and D E]. This shows that BCD is one of the keys.

The candidate keys are ABD, ACD, and BCD.

Normalization
  •  The relation R is in 1NF.

  •  R is not in 2NF. Why?
    • 2NF says “no partial functional dependencies”. In other words, all the non-key (non-prime) attributes must fully functionally dependent on the key or whole key.
    • This is violated here. For example, if we say ABD as the key (because ABD determines all the attributes of R uniquely), D determines the value of E which is a non-key attribute. This means, D alone would be enough to uniquely determine E. This is called as partial functional dependencies (or partial key dependency).
    • This happens with other candidate keys also.
    • The solution is to decompose R into two or more relations.
How to decompose into 2NF?

Follow these steps;
  1. Create a separate relation for each partial dependency.
  2. Remove the right hand side (RHS) attributes of partial dependency from the relation that is to be decomposed.
Apply these steps on R(A, B, C, D, E).
1. Create separate relation for partial dependency D E. We will get R1 (D, E).
2. Remove RHS of D E from R. We will get R2 (A, B, C, D).

As a result, we get R1 (D, E) and R2 (A, B, C, D).

R1 is in 2NF? Yes. R1 is in 2NF, 3NF, and BCNF. [Only one key and one non-key attributes]

R2 is in 2NF? The relation R2 (A, B, C, D) holds set of functional dependencies AB C, AC B, BC A and an attribute D (We would write this as D D, a trivial FD).

Key for R2 would be ABD, or ACD, or BCD. (It is because the closure of these attributes is ABCD).

And, R2 is not in 2NF because of partial key dependency. For example, AB C is partial because the key is ABD. Hence, we need to decompose R2. For that, let us take the FD that violate 2NF into a separate relation. In this case, we can take the FD AB C and we get R21(A,B,C). We don't need to do this for other FDs because all attributes are into R21 already. Only the left out attribute is D. Now, D can be combined with any of the determiner of FDs to get R22(A,B,D).

Key for R21 are AB, BC, and AC. R21 has no partial dependency, hence in  2NF, no transitive dependency of non-key attributes hence in 3NF and the LHS of all FDs are keys hence in BCNF.

Key for R22 is (ABD). As all attributes have formed the key, R22 is in 2NF, 3NF and BCNF.

Final BCNF relations are; R1 (D, E), R21 (A, B, C) and R22(A, B, D).

1 comment:

  1. the relation R2 is not in BCNF, it needs to be further divided into R21(ABC) and R22(ABD)

    ReplyDelete

SQL exercises for beginners one

SQL Exercises for Beginners / Simple SQL Exercises with Answers / Solved SQL exercises / SQL solved exercises with simple conditions / So...