Tag: how to check whether two sets of fds are equivalent

Equivalence of Two Sets of Functional Dependencies

Database Management System

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.