The number of different minimal cover possible are?

Question

Consider R(A,B,C,D,E,F,G) be a relational schema with the following functional dependencies: AC->G, D->EG, BC->D, CG->BD, ACD->B, CE->AG. The number of different minimal cover possible are___________?

Actually in this question we were supposed to find all the possible minimal covers. I used this video So using that theory i tried doing this question but end up getting only 2 minimal covers and then answer given in my text book is 4 . The minimal covers I got are:

1) D->E,D->G,BC->D,CG->D,AC->B(#),CE->A

2) AC->G,D->E,D->G,BC->D,CG->D,CD->B(#), CE->A

Actually the video gives only standard procedure to FIND a minimal cover. but the problem is a bit tricky as it asks about how MANY minimal covers we can find. I am applying the algorithm right...the only issue is that I am unable to find how many more minimal covers can be possible for the given set of FD's

Answer 1

A common algorithm to produce a minimal cover consists of three steps:

1. Split the right part, producing FDs with only one attribute on the right part.

2. For each left part with more than one attribute, try to remove each attribute in turn and see if the remaining can still determine the right part. In this case, eliminate the attribute from the left part.

3. For each remaining dependency, try to see if it can be eliminated.

In your case the first step produces:

F = { A C → G
      A C D → B
      B C → D
      C G → B
      C G → D
      C E → A
      C E → G
      D → E
      D → G }

In the second step, we must check the first seven dependencies. For each dependency A1A2...An -> B we try to eliminate in turn each Ai and see if B is included in the closure of the remaining attributes (the closure taken with respect to F). In this case we have two possibilities: from ACD -> B we can eliminate either A or D. So we have now two different set of dependencies:

F1 = { A C → G
       C D → B
       B C → D
       C G → B
       C G → D
       C E → A
       C E → G
       D → E
       D → G }

and

F2 = { A C → G
       A C → B
       B C → D
       C G → B
       C G → D
       C E → A
       C E → G
       D → E
       D → G }

Now we can apply the last step: for each dependency X -> A we can see if A is included in the closure of X, X+ with respect to all the other dependencies. In this case, we can eliminate that dependency.

The result will depend, in general, from the order in which we apply those checks.

Here there are four different canonical covers:

G1 = { A C → G
       B C → D
       C G → B
       C E → A
       D → E
       D → G }

G2 = { A C → G
       B C → D
       C G → D
       C E → A
       C D → B
       D → E
       D → G }

G3 = { A C → B
       B C → D
       C G → B
       C E → A
       D → E
       D → G }

G4 = { A C → B
       B C → D
       C G → D
       C E → A
       D → E
       D → G }

Note: it is not clear to me if there are other canonical covers.