Equivalence of Two Sets of Functional Dependencies

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.

Summary
Equivalence of Two Sets of Functional Dependencies
Article Name
Equivalence of Two Sets of Functional Dependencies
Description
Functional Dependencies Equivalence- Two sets of functional dependencies may or may not be equivalent. Three cases are possible- F covers G, G covers F, Both F and G cover each other.
Author
Publisher Name
Gate Vidyalay
Publisher Logo
Liked this article? Share it with your friends and classmates now-