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

 

Go back to Normalization – solved exercises page.

Related Posts:

Various uses of attribute closure

How to find Closure?

Normalization solved exercise 5

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) with FD's AB → C, AC → B, BC → A, B → D.

Determine all the keys of relation R. Is the relation R in BCNF?

Solution:

We can derive the values of C and D uniquely from the FDs AB → C, and B → D. And the closure of AB, i.e., (AB)⁺ = ABCD. Hence, AB is one of the keys.

We can derive the values of B and D uniquely from the FDs AC → B, and B → D (Transitive FDs). (AC)⁺ = ABCD. Hence, AC is one of the keys.

We can derive the values of A and D uniquely from the FDs BC → A, and B → D. and the closure (BC)⁺ = ABCD. Hence, BC is one of the keys.

The keys are AB, AC, and BC.

Is R in BCNF?

Requirements: R should be in 2NF, 3NF, and every determinant must be a candidate key.

Partial key dependency is present – In the functional dependency B → D, the determinant B is not a key. But it is a part of the candidate keys AB and BC. If part of any candidate keys can uniquely identify another (or set of) non-key attribute, we call that as partial key dependency.

Hence, R is not in 2NF. We need to decompose R into the following relations so that we can make 2NF relations out of R;

R1(A, B, C) and R2(B, D).

R1 and R2 do not have partial key dependencies, and transitive dependencies. Hence, both are in 2NF and 3NF.

The determinants are the keys in both the relations. Hence, R1 and R2 are in BCNF.

Go back to Normalization - solved exercises page

Normalization solved exercise 4

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) with FD's AB → C, AC → B, BC → A.

Determine all the keys of relation R. Is the relation R in BCNF?

Solution:

From AB → C, we obtain that AB is one of the keys.

From AC → B, we obtain that AC is one of the keys.

From BC → A, we obtain that BC is one of the keys.

Every single FD given above, includes all the attributes of R. Hence, all the left hand side attributes form the key. And the keys are AB, AC, and BC.

Is R in BCNF?

Requirements: R should be in 2NF, 3NF, and every determinant must be a candidate key.

From the set of functional dependencies given, we observe the following;

• No partial key dependencies. So, R is in 2NF.
• No transitive dependencies. So, R is in 3NF.
• Every determinant (AB, BC, AC) is a candidate key. Hence, R is in BCNF as well.

Go back to Normalization - solved exercises page.

Normalization solved exercise 3

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

Question:

Consider a relation R(A, B, C, D, E) with FD's AB → C, CD → E, C → A, C → D, D → B.

The possible candidate keys for R are AB, AD, C

(a) List all the functional dependencies that violate 3NF. If any, then decompose R accordingly.

(b) List all the FD's that violate BCNF. If any, then decompose R accordingly.

Solution (a):

To be in 3NF, the following points should not be violated by any of the FDs;

(i) R should be in 2NF;

According to the properties that are to be held for 2NF (No partial functional dependencies), all the non-prime attributes (E is the only non-prime attribute in our case) depend on prime attributes (A, B, C, and D in our case) or keys as a whole. No partial dependencies found. Hence, we would say that R is in 2NF.

(ii) Transitive functional dependencies of non-prime attributes on candidate keys are prohibited;

In the list of functional dependencies, we found no non-key dependencies. That is, no non-prime attribute is functionally dependent on another non-prime attribute.

From points (i) and (ii), it is clear that there are no FDs that violate 3NF. Hence, we would say that R is in 3NF.

Solution (b):

R can be in BCNF if and only if R is in 3NF and every determinant is a candidate key. 

From the solution (a), you would understand that R is in 3NF. But every determinant is not a candidate key. In the given set of FDs, D → B is the only functional dependency that violates this rule. That is, D is not a candidate key on its own. Hence, the relation R is not in BCNF.

To convert R into a BCNF relation, we need to decompose R using the FD D → B. Then we shall get the following relations R1 and R2;

R1 (D, B) and R2 (A, C, D, E)

Go back to Normalization - Solved Exercises page