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.