Normalization solved exercise to find key

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) with FD's B → C, D → A. Determine all the keys of relation R. 

Solution:

To find the key of a relation, we need to find the closure of attributes. If any attribute’s or set of attributes’ closure gives all the attributes of the relation, then we would say that attribute/set of attributes as the key for that relation.

To simplify this task or to avoid finding closure of all attributes, let us do find the closure for left hand side (LHS) attributes of the functional dependencies.

For the given question, attributes B and D are the LHS attributes.

• The closure of B, (B)⁺ = BC from ≠ ABCD. Hence B is not a key. [Refer, How tofind closure/how to find key, purpose of finding attribute closure]

• The closure of D, (D)⁺ = DA ≠ ABCD. Hence D is not a key. [Refer, How to find closure/how to find key, purpose of finding attribute closure]

• The closure of B and D together, i.e., (BD)⁺ = ABCD. All the attributes can be determined. Hence, BD is a key (a composite key).

 The key for R is (BD).


Go back to Normalization - solved exercises page.

********

Normalization process solved problems

Important normalization exercises solved an explained

How to find the key of a relation during normalization process

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.