Equivalence of Two Sets of Functional Dependencies-
Before you go through this article, make sure that you have gone through the previous article on Functional Dependency.
In DBMS,
- Two different sets of functional dependencies for a given relation may or may not be equivalent.
- If F and G are the two sets of functional dependencies, then following 3 cases are possible-
Case-01: F covers G (F ⊇ G)
Case-02: G covers F (G ⊇ F)
Case-03: Both F and G cover each other (F = G)
Case-01: Determining Whether F Covers G-
Following steps are followed to determine whether F covers G or not-
Step-01:
- Take the functional dependencies of set G into consideration.
- For each functional dependency X → Y, find the closure of X using the functional dependencies of set G.
Step-02:
- Take the functional dependencies of set G into consideration.
- For each functional dependency X → Y, find the closure of X using the functional dependencies of set F.
Step-03:
- Compare the results of Step-01 and Step-02.
- If the functional dependencies of set F has determined all those attributes that were determined by the functional dependencies of set G, then it means F covers G.
- Thus, we conclude F covers G (F ⊇ G) otherwise not.
Case-02: Determining Whether G Covers F-
Following steps are followed to determine whether G covers F or not-
Step-01:
- Take the functional dependencies of set F into consideration.
- For each functional dependency X → Y, find the closure of X using the functional dependencies of set F.
Step-02:
- Take the functional dependencies of set F into consideration.
- For each functional dependency X → Y, find the closure of X using the functional dependencies of set G.
Step-03:
- Compare the results of Step-01 and Step-02.
- If the functional dependencies of set G has determined all those attributes that were determined by the functional dependencies of set F, then it means G covers F.
- Thus, we conclude G covers F (G ⊇ F) otherwise not.
Case-03: Determining Whether Both F and G Cover Each Other-
- If F covers G and G covers F, then both F and G cover each other.
- Thus, if both the above cases hold true, we conclude both F and G cover each other (F = G).
PRACTICE PROBLEM BASED ON EQUIVALENCE OF FUNCTIONAL DEPENDENCIES-
Problem-
A relation R (A , C , D , E , H) is having two functional dependencies sets F and G as shown-
Set F-
A → C
AC → D
E → AD
E → H
Set G-
A → CD
E → AH
Which of the following holds true?
(A) G ⊇ F
(B) F ⊇ G
(C) F = G
(D) All of the above
Solution-
Determining whether F covers G-
Step-01:
- (A)+ = { A , C , D } // closure of left side of A → CD using set G
- (E)+ = { A , C , D , E , H } // closure of left side of E → AH using set G
Step-02:
- (A)+ = { A , C , D } // closure of left side of A → CD using set F
- (E)+ = { A , C , D , E , H } // closure of left side of E → AH using set F
Step-03:
Comparing the results of Step-01 and Step-02, we find-
- Functional dependencies of set F can determine all the attributes which have been determined by the functional dependencies of set G.
- Thus, we conclude F covers G i.e. F ⊇ G.
Determining whether G covers F-
Step-01:
- (A)+ = { A , C , D } // closure of left side of A → C using set F
- (AC)+ = { A , C , D } // closure of left side of AC → D using set F
- (E)+ = { A , C , D , E , H } // closure of left side of E → AD and E → H using set F
Step-02:
- (A)+ = { A , C , D } // closure of left side of A → C using set G
- (AC)+ = { A , C , D } // closure of left side of AC → D using set G
- (E)+ = { A , C , D , E , H } // closure of left side of E → AD and E → H using set G
Step-03:
Comparing the results of Step-01 and Step-02, we find-
- Functional dependencies of set G can determine all the attributes which have been determined by the functional dependencies of set F.
- Thus, we conclude G covers F i.e. G ⊇ F.
Determining whether both F and G cover each other-
- From Step-01, we conclude F covers G.
- From Step-02, we conclude G covers F.
- Thus, we conclude both F and G cover each other i.e. F = G.
Thus, Option (D) is correct.
Next Article- Canonical Cover in DBMS
Get more notes and other study material of Database Management System (DBMS).
Watch video lectures by visiting our YouTube channel LearnVidFun.
