Thursday, February 4, 2016

Steps to decompose a non-2NF relation to a 2NF relation



How to decompose a non-2NF relation into a 2NF relation? / Decomposing a relation that consists partial functional dependencies / Steps in decomposing a table into a 2nf table


2NF properties:


-Relation should be in 1NF.

-No partial functional dependency must present. (All the non-key attributes must depend on the whole key / key attribute)

Decomposition steps:
If any partial functional dependency (partial FD is considered only when the key is a composite key) present in a table/relation that you normalize, then you should decompose (break) that relation into two or more relations depend on the set of functional dependencies. To decompose the relation, you can follow these simple steps;

Step 1: Create a separate relation for each partial dependency


Step 2: Remove the right hand side attribute of the partial dependency from the relation that is being decomposed.

Example 1:
Flight_ID
Flight_Day
Pilot
Boarding_Gate
IC123
Monday
Kesav
2
IC123
Tuesday
Mark
2
IC217
Wednesday
Kesav
3
IA156
Monday
Steve
1

For this Flight_Schedule table, the following is the set of functional dependencies;
F = { Flight_ID Flight_Day Pilot Boarding_Gate, Flight_ID Boarding_Gate}
This table is in 1NF, but not in 2NF because of the FD Flight_ID Boarding_Gate. In our example, the key is (Flight_ID, Flight_Day). These two attributes together can identify the Pilot value uniquely. But for identifying the other attribute Boarding_Gate, the attribute Flight_Day is enough [Flight_Day is part of the composite key of this relation].

Now, let us apply the steps shown above.

Step 1: Create a separate relation for each partial dependency. In our example, Flight_ID Boarding_Gate is the partial dependency. Hence we need to create a separate relation for this FD. Let us name this relation as Boarding.
Boarding ( Flight_ID, Boarding_Gate)

Step 2: Remove the right hand side attribute of the partial dependency from the relation that is being decomposed. In the relation Flight_Schedule (Flight_ID, Flight_Day, Pilot, Boarding_Gate), the attribute Boarding_Gate should be removed as per this condition. The reason is, Boarding_Gate is the right hand side (RHS) attribute of the partial dependency, Flight_ID Boarding_Gate. Hence,
Flight_Schedule (Flight_ID, Flight_Day, Pilot).

Thus, Flight_Schedule (Flight_ID, Flight_Day, Pilot, Boarding_Gate) is decomposed into Flight_Schedule (Flight_ID, Flight_Day, Pilot) and Boarding ( Flight_ID, Boarding_Gate).

Example 2:

Assume a relation R (A, B, C, D, E) with the following set of functional dependencies;
F = {AB C, B D, E D}
The key for this relation is ABE. Then, all three given FDs are partial dependencies, viz., AB C, B D, and E D.
Step 1: separate tables for partial dependencies; hence, R1 (ABC), R2 (BD) and R3 (ED).

Step 2: remove RHS of these two partial FDs from R; hence, R4(A, B, E).

Thus, we have four tables R1 (ABC), R2 (BD), R3 (ED) and R4 (ABE).



5 comments:

  1. In last example, all three FDs are partial, right? You did not considered AB->C as a partial dependencies. Now according to steps, we we create a separate table for each partial dependency, we get,

    R1:(A,B,C)
    R2:(B,D)
    R3:(E,F)

    This is lossy decomposition since we cannot koin R1 and R3. So we need to revise the steps in order to create proper decomposition. Am just guessing what they could be.

    Should there be 3rd step: "Check if the decomposition is lossless. If not, suitably add determinate (left side fds) of one fd to another"?

    We need more verbose/concrete steps.

    ReplyDelete
  2. The key is referring to primary key or candidate key?

    ReplyDelete
    Replies
    1. A table may have many candidate keys. One among them is chosen as primary key. Hence, a table with only one candidate key, the terms are interchangeable. You please understand according to the context.
      I am not able to locate which 'key' in the post?

      Delete

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

data recovery