Redundant Functional Dependency(FD)

Redundant Functional Dependency(FD)

  • A FD in the set is redundant, if it can be derived from the other FDs in the set.
  • Redundant FD can be detected by using Membership algorithm.

Algorithams:

Input: Let F be a set of FDs for relation R.

Let f: A -> B is a FD to be examined for redundancy.

Steps:

1. F’ = F – f  # find out new set of FDs by removing f from F

2. T = A  # set T = determinant of A ->B

3. For each FD: X -> Y in F’ Do

If X ∈ T Then  # if X is contained in T

T = T U Y  # add Y to T

End if

End For

4. If B ∈ T Then   # if B is contained in T

f : A -> B is redundant.  # given FD f : A ->B is redundant. `

End if

Output: Decision whether a given FD f : A -> B is redundant or not.

Example:

suppose a relation R is given with attributes A, B, C, D, E.
Also, a set of functional dependencies F is given with following FDs.
F =  {A -> B, C -> D, BD -> E, AC -> E}

1. Find out whether a FD f : AC -> E is redundant or not .

Step 1 : F ‘ = {A -> B, C -> D, BD -> E}

Step 2 : T = AC

Step 3 : T = AC + B = ACB   T = ACB + D = ACBD   T = ACBD + E = ACBDE

Step 4 : f : AC -> E is redundant.

2. Find out whether a FD f : BD -> E is redundant or not .

Step 1 : F ‘ = {A -> B,C -> D, AC -> E}

Step 2 : T= BD

Step 3 : Nothing can be added to T, As there is no other FD : X -> Y   such that X-> T

Step 4 : f : BD -> E is not Redundant.

Leave a Reply

Your email address will not be published. Required fields are marked *