Questions on Minimal Cover or Irreducible Sets or Canonical Cover –

Questions on Minimal Cover or Irreducible Sets or Canonical Cover –

Question 1 :Find the minimal cover or irreducible set from the
following functional dependencies :
AB → CD
BC → D

Solution :
Step 1 : Union Simplification :
   AB → C ..(1)
   AB → D ..(2)
   BC → D ..(3)

Step 2 : Removal of Redundant set of FDs -
 (i) Find the closure of LHS of (1), i.e. Compute (AB)+ from (2) and
     (3) by hiding (1). If we get RHS of (1) in the closure,i.e. 'C',
     then (1) is redundant, otherwise non redundant.

                          (AB)+ = {ABD}

     as (AB)+ will not determine C, So AB → C is non redundant.
(ii) Similarly for (2), Compute (AB)+ from (1) and (3) by hiding (2).
                          (AB)+ = {ABCD}

     as (AB)+ will determine D, therefore, AB → D is redundant.
     Now, Remaining FDs = {AB→C, BC→D}
(iii) For (3), Compute (BC)+ from (1) by hiding (3).

                          (BC)+ = {BC}

     as (BC)+ will not determine D, so, BC → D is also non redundant.

Step 3 : LHS Simplification or Removal of Extraneous Attributes -
         FDs remained after step 2
           AB→C .. (3)
           BC→D .. (4)
    AB → C
    (i) Remove A from AB → C, and find B+ from (4). If the
        attribute A exists in the closure, then A is said to be
        redundant.
                       B+ = {B} ⇒ A is Non Redundant
   (ii) Remove B from AB → C and find A+ from (4).
                       A+ = {A} ⇒ B is Non Redundant.
    BC → D
    (i) Remove B from BC → D, and find C+ from (3).
                       C+ = {C} ⇒ B is Non Redundant
   (ii) Remove C from BC → D and find B+ from (3).
                       B+ = {B} ⇒ C is Non Redundant

Apply step 2 again if we find any redundant attribute, otherwise skip
So Finally, Irreducible set will be
AB→C
BC→D

The another Example will give you more clarification about solving minimal cover questions.

Question 2 :
Find the minimal cover or irreducible set from the following
functional dependencies :
ABCD → E ..(1)
E    → D ..(2)
AC   → D ..(3)
A    → B ..(4)

Solution :
step 1 : No need for union simplification as FDs are already simplified.

Step 2 : Removal of redundant set of FDs -
 (i)  For (1), Compute (ABCD)+ from (2) (3) and (4) by hiding (1).
                          (ABCD)+ = {ABCD}
                        ⇒ ABCD → E is non redundant.
(ii)  For (2), Compute (E)+ from (1) (3) and (4) by hiding (2).
                          (E)+ = {E}
                        ⇒ E → D is non redundant.
(iii) For (3), Compute (AC)+ from (1) (2) and (4) by hiding (3).
                          (AC)+ = {ACB}
                        ⇒ AC → D is non redundant.
(iv)  For (4), Compute (A)+ from (1) (2) and (3) by hiding (4).
                          (A)+ = {A}
                        ⇒ A → B is non redundant.

Step 3 : LHS Simplification or Removal of Extraneous Attributes -
         FDs remained after step 2 is same as in step 1.
  ABCD → E
   (i) Remove A from ABCD → E, and find BCD+ from (2) (3) and (4). If
        attribute A exists in the closure, then A is said to be
        redundant.
                      (BCD)+ = {BCD} ⇒ A is Non Redundant
   (ii) Remove B from ABCD → E and find ACD+ from (2) (3) and (4).
                      (ACD)+ = {ACDB} ⇒ B is Redundant.
                    ⇒ FD will now reduced to ACD → E
  (iii) Remove C from ACD → E, and find AD+ from (2) (3) and (4).
                       (AD)+ = {ADB} ⇒ C is Non Redundant.
   (iv) Remove D from ACD → E, and find AC+ from (2) (3) and (4).
                      (AC)+ = {ACDB} ⇒ D is Redundant.
                    ⇒ FD will now reduced to AC → E
  AC → D
    (i) Remove A from AC → D and find C+ from (1) (2) and (4).
                       (C)+ = {C} ⇒ A is non redundant.
   (ii) Remove C from AC → D and find A+ from (1) (2) and (4).
                       (A)+ = {AB} ⇒ C is non redundant.
FDs remained after step 3 are :
AC → E ..(5)
E  → D ..(6)
AC → D ..(7)
A  → B ..(8)

Step 4 : Applying step 2 again to find redundant FDs -
  (i)  For (5), Compute (AC)+ from (6) (7) and (8) by hiding (5).
                          (AC)+ = {ACDB}
                        ⇒ AC → E is non redundant.
 (ii)  For (6), Compute (E)+ from (5) (7) and (8) by hiding (6).
                          (E)+ = {E}
                        ⇒ E → D is non redundant.
(iii)  For (7), Compute (AC)+ from (5) (6) and (8) by hiding (7).
                          (AC)+ = {ACEDB}
                        ⇒ AC → D is redundant. So, excluded.
 (iv)  For (8), Compute (A)+ from (5) and (6) by hiding (8).
                          (A)+ = {AB}
                        ⇒ A → B is non redundant.

So Finally, Irreducible set will be
AC → E
E  → D
A  → B

]]>