Redundant functional dependencies

A functional dependency in the set is redundant if it can be derived from the other functional dependencies in the set.  A redundant FD can be detected using the following steps:
Step 1:  Start with a set of S of functional dependencies (FDs). 
Step 2: Remove an FD f and create a set of FDs  S' = S -  f . 
Step 3: Test whether f can be derived from the FDs in S'; by using the set of Armstrong's  axioms and derived rules.
Step 4:  If f can be so derived, it is redundant , and hence S' = S. Otherwise replace f into   S'; so that now S' = S + f.
Step 5: Repeat steps 2 to 4 for all FDs in S.
Armstrong's axioms and derived rules, as discussed in the previous section, can be used to find redundant FDs.  

For example, suppose the following set of FDs is given in the algorithm:  
Z -> A   B -> X   AX -> Y   ZB -> Y 

Because ZB  -> Y Can be derived from other FDs in the set, it can be shown to be redundant.
The following argument can be given:

• Z -> A by augmentation rule will yield ZB -> AB.
• B -> X and AX -> Y by pseudo-transitivity rule will yield AB -> Y.
• ZB -> AB and AB -> Y by transitivity rule will yield ZB -> Y.

An algorithm (called membership algorithm) can be developed to find redundant FDs, that is, to determine whether an FD f(A -> B) can be derived from a set of FDs  S.  Using the algorithm the redundant functional dependency can be checked.
 

Algorithm: Membership algorithm to find redundant functional dependency

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

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 -> yin F' Do
              a) If X ⊆ T Then                         //if X is contained in T
                 T = T ∪ Y                           //add Y to T
               End if
       
        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.  

---

• Prev
• Next

---