889 views
0 votes
0 votes
What is the number of redundent FD’s possible for given set of FD , A->B, B->C,C->D  for relation R(ABCD)?? please explain in detail.

1 Answer

1 votes
1 votes

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 can be used to find redundant FDs.

 

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.

 

 

 

Related questions

0 votes
0 votes
0 answers
1
air1ankit asked Oct 27, 2017
460 views
R(ABCDE) { A,BC,CD} are candidate key of relation R after 1 NF design which one is possible multi valued attributes before 1 NF design ???