Equivalence of functional dependencies in DBMS

Equivalence of functional dependencies

  • Equivalence of functional dependencies is nothing but we need to determine whether all functional dependencies existed for the relation are equal or not
  • You will be given a relation with different functional dependency sets of that relationship you need to check whether one functional dependency is a subset of other or both are equal

Finding a relationship between two to FD (functional dependency) sets 

Consider S1 and S2 are two FD sets for a relation R.

  1. If all FDs of S1 can be determined from FDs that are present in S2, we can conclude that S2  S1.
  2. If all FDs of S2 can be determined from FDs that are present in S1, we can conclude FD1 FD2.
  3. If 1 and 2 are satisfied then, S1=S2.
Equivalence of functional dependencies

Check for the equivalence of functional dependencies for A relation R (A, B, C, D) having two FD sets S1 = {A->B, B->C, AB->D} and S2= {A->B, B->C, A->C, A->D} 

Solution: 
  • Step 1.  Checking whether all FDs of set S1 is present in set S2 
    • FD A->B in set S1 is present in set S2.
    • FD B->C in set S1 is also present in set S2.
    • FD AB->D in present in set S1 but not in S2 but we have to check whether we can derive it or not. In set S2, (AB) + = {A, B, C, D}. It means that A,B,C,D can be determined functionally from AB which implies AB->D holds true for set S2
    • As all FDs in set S1 also hold in set S2, S2  S1 is true.
  • Step 2.  Checking whether all FDs of S2 are present in S1
    • FD A->B in set S2 is present in set S1.
    • FD B->C in set S2 is also present in set S1.
    • FD A->C is present in S2 but not in S1 but we have to check whether we can derive it or not. In set S1, (A) + = {A, B, C, D}. It means that A,B,C,D can be determined functionally from A which implies A->C holds true for set S1.
    • FD A->D is present in S2 but not in S1 but we have to check whether we can derive it or not. In set S1, (A) + = {A, B, C, D}. It means that A,B,C,D can be determined functionally from A which implies A->D holds true for set S1.
    • As all FDs in set S2 also hold in set S1, S1  S2 is true.
  • Step 3. We can conclude that S1=S2 as both S2 S1 and S1 S2 are true. Hence these two FD sets are semantically equivalent.