Please visit, subscribe and share 10 Minutes Lectures in Computer Science

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 in 2NF because all attributes are prime attributes. [2NF - No non-prime attribute should be functionally dependent on proper subset of any candidate key]

R2 is in 3NF? As all attributes have formed the key, all are prime attributes. Hence, there is no transitive functional dependencies of non-prime attributes. So, R2 also in 3NF.
 
R2 is in BCNF? 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).
 
R2 is not in BCNF because the LHS of FDs are not super keys . [BCNF - Every non-trivial functional dependency must be a dependency on a superkey.]
 

Featured Content

Multiple choice questions in Natural Language Processing Home

MCQ in Natural Language Processing, Quiz questions with answers in NLP, Top interview questions in NLP with answers Multiple Choice Que...

All time most popular contents