MADE EASY TEST-SERIES

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___________?

Comments

https://gateoverflow.in/273396/madeeasydbms Check this out!

Only 2 minimal covers possible.

---

Yes there are 2 diffrent minimal covers possible. I counted number of dependencies of a minimal cover.

---

plz explain this soln?

Answer 1

STEP 1: After splitting the FD's we get : AC->G, D->E, D->G, BC->D, CG->B, CG->D, ACD->B, CE->A, CE->G

Step 2: now removing extraneous attributes:

    a) D is extraneous in ACD as AC->D by AC->G and CG->D therefore ACD will be AC

    b) A is extraneous in ACD as CD->A by D->E and CE->A therefore ACD will be CD

Step 3: removing redundant FD's:

A) removing ACD->B , CE->G, CG->D or CG->B FD's

1) Considering a) of Step 2 FD's are : AC->G, D->E, D->G, BC->D, CG->B, CG->D, AC->B, CE->A, CE->G

      -->  AC->B is redundant as AC->G and CG->B by transitivity AC->B so it should be removed.

       now remaining FD's are  AC->G, D->E, D->G, BC->D, CG->B, CG->D,  CE->A, CE->G

      -->1)CG->D is redundant as CG->B  and BC->D by transitivity CG->D, so it should be removed.

       now remaining FD's are  AC->G, D->E, D->G, BC->D, CG->B,  CE->A, CE->G

                                                                or

          2)  CG->B is redundant as CG->D, D->E, CE->A and AC->B by transitivity CG->B, so it should be removed.

             now remaining FD's are  AC->G, D->E, D->G, BC->D, CG->D,  CE->A, CE->G

      -->CE->G is redundant as CE->A and AC->G by transitivity CE->G, so it should be removed.

           now remaining FD's are AC->G, D->E, D->G, BC->D, CG->B,  CE->A--------------------------------------(1) minimal cover

           now remaining FD's are AC->G, D->E, D->G, BC->D, CG->D,  CE->A--------------------------------------(2) minimal cover

2)Considering b) of Step 2 FD's are : AC->G, D->E, D->G, BC->D, CG->B, CG->D, CD->B, CE->A, CE->G

    -->CD->B is redundant as D->G and CG->B by transitivity CD->B so it should be removed.

          now remaining FD's are  AC->G, D->E, D->G, BC->D, CG->B, CG->D,  CE->A, CE->G

    -->1)CG->D is redundant as CG->B  and BC->D by transitivity CG->D, so it should be removed.

         now remaining FD's are  AC->G, D->E, D->G, BC->D, CG->B,  CE->A, CE->G

                                                                             or

      2)  CG->B is redundant as CG->D, D->E, CE->A and AC->B by transitivity CG->B, so it should be removed.

           now remaining FD's are  AC->G, D->E, D->G, BC->D, CG->D,  CE->A, CE->G

    -->CE->G is redundant as CE->A and AC->G by transitivity CE->G, so it should be removed.

       now remaining FD's are AC->G, D->E, D->G, BC->D, CG->B,  CE->A--------------------------------------(1) minimal cover

                                                        or

        now remaining FD's are AC->G, D->E, D->G, BC->D, CG->D,  CE->A--------------------------------------(2) minimal cover

B) removing CG->B or CG->D , CE->G, AC->G

  1)Considering a) of Step 2 FD's are : AC->G, D->E, D->G, BC->D, CG->B, CG->D, AC->B, CE->A, CE->G

      -->1) CG->B is redundant as CG->D, D->E, CE->A and AC->B by transitivity CG->B, so it should be removed.

             now remaining FD's are AC->G, D->E, D->G, BC->D, CG->D, AC->B, CE->A, CE->G

                                                  or

            2) CG->D is redundant as CG->B  and BC->D by transitivity CG->D, so it should be removed.

              now remaining FD's are AC->G, D->E, D->G, BC->D, CG->B, AC->B, CE->A, CE->G

      -->CE->G is redundant as CE->A and AC->G by transitivity CE->G, so it should be removed.

            now remaining FD's are AC->G, D->E, D->G, BC->D, CG->B, AC->B, CE->A

                                                                      or

           now remaining FD's are AC->G, D->E, D->G, BC->D, CG->D, AC->B, CE->A

      -->AC->G is redundant as AC->B, BC->D and D->G by transitivity AC->G, so it should be removed.

          now remaining FD's are D->E, D->G, BC->D, CG->B, AC->B, CE->A-------------(3) minimal cover

                                                                      or

         now remaining FD's are D->E, D->G, BC->D, CG->D, AC->B, CE->A--------------(4) minimal cover

 

2) Considering b) of Step 2 FD's are : AC->G, D->E, D->G, BC->D, CG->B, CG->D, CD->B, CE->A, CE->G

     -->1) CG->B is redundant as CG->D and CD->B by transitivity CG->B, so it should be removed.

              now remaining FD's are AC->G, D->E, D->G, BC->D, CG->D, CD->B, CE->A, CE->G

                                                                or

          2) CG->D is redundant as CG->B and BC->D by transitivity CG->D, so it should be removed.

              now remaining FD's are AC->G, D->E, D->G, BC->D, CG->B, CD->B, CE->A, CE->G

      -->CE->G is redundant as CE->A and AC->G by transitivity CE->G, so it should be removed.

             now remaining FD's are AC->G, D->E, D->G, BC->D, CG->B, CD->B, CE->A

                                                              or

            now remaining FD's are AC->G, D->E, D->G, BC->D, CG->D, CD->B, CE->A

      -->CD->B is redundant as D->G and CG->B by transitivity CD->B, so it should be removed.

            now remaining FD's are AC->G, D->E, D->G, BC->D, CG->B, CE->A----------------(1) minimal cover

                                                              or

            now remaining FD's are AC->G, D->E, D->G, BC->D, CG->D, CD->B, CE->A-------(6) minimal cover

Finally the minimal clovers are

AC->G, D->E, D->G, BC->D, CG->B,  CE->A

AC->G, D->E, D->G, BC->D, CG->D,  CE->A

D->E, D->G, BC->D, CG->B, AC->B, CE->A

D->E, D->G, BC->D, CG->D, AC->B, CE->A

AC->G, D->E, D->G, BC->D, CG->D, CD->B, CE->A

Please correct me if i am wrong anywhere

Comments

@Priyanka17 In your 2nd minimal cover ACD->B is lost, So can this be a minimal cover?

https://gateoverflow.in/273396/madeeasydbms Check this out!

Only 2 minimal covers possible.

 

Answer 2

Given $FD’s=\left\{AC\rightarrow G,D\rightarrow EG,BC\rightarrow D,CG\rightarrow BD,ACD\rightarrow B,CE\rightarrow AG\right\}$

Finding the minimal cover:-

$(1)$ Split the FD's such a way that $RHS$ contain only single attribute.

Here,

         $AC\rightarrow G$

          $D\rightarrow E$

          $D\rightarrow G$

          $BC\rightarrow D$

          $CG\rightarrow B$

          $CG\rightarrow D$

,       $ACD\rightarrow B$

         $CE\rightarrow A$

         $CE\rightarrow G$

$(2)$ find the redundant FD's and delete them from the set.

         $AC\rightarrow G$ $[$Take this FD and find the attribute closure without this FD.If we are able to find the 'G' without this FD.then we can say that this FD is redundant and remove from the set$]$

Now, $(AC)^{+}=AC$ we are not able to find the $'G'$. So we can say that this FD is not redundant.

Similarly for all those FD's

          $D\rightarrow E$         $[(D)^{+}=DG]$

           $D\rightarrow G$      $[(D)^{+}=DE]$

          $BC\rightarrow D$        $[(BC)^{+}=BC]$

          $CG\rightarrow B$           $[(CG)^{+}=CGDEAB]$ It remove from the set. It is not considered are FD for finding the remaining FD attribute closure.

          $CG\rightarrow D$          $[(CG)^{+}=CG]$

         $ACD\rightarrow B$         $[(ACD)^{+}=ACDEG]$

         $CE\rightarrow A$             $[(CE)^{+}=CEGD]$

         $CE\rightarrow G$             $[(CE)^{+}=CEAGD]$ It remove from the set. It is not considered are FD for finding the remaining FD attribute closure.

Now, we got 

           $AC\rightarrow G$

            $D\rightarrow E$       

             $D\rightarrow G$      

             $BC\rightarrow D$

             $CG\rightarrow D$         

,            $ACD\rightarrow B$        

              $CE\rightarrow A$     

$(3)$ Find the redundant attributes on $LHS$ and delete them. 

            $AC\rightarrow G$  $[(C)^{+}=C$ ,$(A)^{+}=A]$  So, here nothing is deleted.

             $D\rightarrow E$ Here only one attribute on $LHS$ so nothing is redundant      

             $D\rightarrow G$ Here only one attribute on $LHS$ so nothing is redundant     

             $BC\rightarrow D$  Here We can delete $'B'$,if $(C)^{+}$ contain $B$  $(or)$   We can delete $'C'$,if $(B)^{+}$ contain $'C'$

            lets find $(B)^{+}=B$

                          $(C)^{+}=C$

            So, here nothing is deleted.

             $CG\rightarrow D$  $[(C)^{+}=C$ ,$(G)^{+}=G]$  So, here nothing is deleted.        

,            $ACD\rightarrow B$ $[(AC)^{+}=ACGD$  $,$   $(D)^{+}=DEG]$ we can say that $'D'$ is deleted.       

              $CE\rightarrow A$  $[(C)^{+}=C$, $(E)^{+}=E]$  So, here nothing is deleted.

Now we got

           $AC\rightarrow G$

            $D\rightarrow E$       

             $D\rightarrow G$      

             $BC\rightarrow D$

             $CG\rightarrow D$         

,            $AC\rightarrow B$        

              $CE\rightarrow A$ 

Now again find the redundant $FD's$

            $AC\rightarrow G$   $[(AC)^{+}=ACBDEG$  It remove from the set. It is not considered are FD for finding the remaining FD attribute closure.

            $D\rightarrow E$  $[(D)^{+}=DG]$  

             $D\rightarrow G$   $[(D)^{+}=DE]$     

             $BC\rightarrow D$$[(BC)^{+}=BC]$  

             $CG\rightarrow D$   $[(CG)^{+}=CG]$        

,            $AC\rightarrow B$   $[(AC)^{+}=AC]$       

              $CE\rightarrow A$ $[(CE)^{+}=CE]$  

Now we got

            $D\rightarrow E$       

             $D\rightarrow G$      

             $BC\rightarrow D$

             $CG\rightarrow D$         

,            $AC\rightarrow B$        

              $CE\rightarrow A$ 

We can write like this 

So, minimal cover are

             $D\rightarrow EG$      

             $BC\rightarrow D$

             $CG\rightarrow D$         

,            $AC\rightarrow B$        

              $CE\rightarrow A$ 

 

$(1)$ For the given FD's when we split I take to change the order $($I take FD's from the point $(1)$ $)$

        $AC\rightarrow G$

          $D\rightarrow E$

          $D\rightarrow G$

          $BC\rightarrow D$

         $CG\rightarrow D$

         $CG\rightarrow B$

,       $ACD\rightarrow B$

         $CE\rightarrow A$

         $CE\rightarrow G$

 

$(2)$ find the redundant FD's and delete them from the set.

     $AC\rightarrow G$ $[$Take this FD and find the attribute closure without this FD.If we are able to find the 'G' without this FD.then we can say that this FD is redundant and remove from the set$]$

Now, $(AC)^{+}=AC$ we are not able to find the $'G'$. So we can say that this FD is not redundant.

Similarly for all those FD's

          $D\rightarrow E$         $[(D)^{+}=DG]$

           $D\rightarrow G$      $[(D)^{+}=DE]$

          $BC\rightarrow D$        $[(BC)^{+}=BC]$

          $CG\rightarrow D$           $[(CG)^{+}=CGBDEA]$ It remove from the set. It is not considered are FD for finding the remaining FD attribute closure.

          $CG\rightarrow B$          $[(CG)^{+}=CG]$

         $ACD\rightarrow B$         $[(ACD)^{+}=ACDBG]$ It remove from the set. It is not considered are FD for finding the remaining FD attribute closure.

         $CE\rightarrow A$             $[(CE)^{+}=CEGBD]$

         $CE\rightarrow G$             $[(CE)^{+}=CEAG]$ It remove from the set. It is not considered are FD for finding the remaining FD attribute closure.

 

Now we got

     $AC\rightarrow G$

       $D\rightarrow E$ 

       $D\rightarrow G$  

        $BC\rightarrow D$     

        $CG\rightarrow B$   

        $CE\rightarrow A$ 

 

$(3)$ Find the redundant attributes on $LHS$ and delete them. 

            $AC\rightarrow G$  $[(C)^{+}=C$ ,$(A)^{+}=A]$  So, here nothing is deleted.

             $D\rightarrow E$ Here only one attribute on $LHS$ so nothing is redundant      

             $D\rightarrow G$ Here only one attribute on $LHS$ so nothing is redundant     

             $BC\rightarrow D$  Here We can delete $'B'$,if $(C)^{+}$ contain $B$  $(or)$   We can delete $'C'$,if $(B)^{+}$ contain $'C'$

            lets find $(B)^{+}=B$

                          $(C)^{+}=C$

                 So, here nothing is deleted.

            $CG\rightarrow B$  $[(C)^{+}=C$ ,$(G)^{+}=G]$  So, here nothing is deleted.              

              $CE\rightarrow A$  $[(C)^{+}=C$, $(E)^{+}=E]$  So, here nothing is deleted.

We got 

      $AC\rightarrow G$

       $D\rightarrow E$ 

       $D\rightarrow G$  

        $BC\rightarrow D$     

        $CG\rightarrow B$   

        $CE\rightarrow A$ 

Now again find the redundant $FD's$,but no one $FDs'$ are redundant.

We can write like this 

So, minimal cover are:

     $AC\rightarrow G$

       $D\rightarrow EG$      

       $BC\rightarrow D$     

        $CG\rightarrow B$   

        $CE\rightarrow A$ 

 

 

$(1)$ For the given FD's when we split I take to change the order $($I take FD's from the point $(1)$ $)$

        $AC\rightarrow G$

          $D\rightarrow E$

          $D\rightarrow G$

          $BC\rightarrow D$

         $CG\rightarrow B$

         $CG\rightarrow D$

,       $ACD\rightarrow B$

         $CE\rightarrow G$

         $CE\rightarrow A$

In this case, we got

 minimal cover are

             $D\rightarrow EG$      

             $BC\rightarrow D$

             $CG\rightarrow D$         

,            $AC\rightarrow B$        

              $CE\rightarrow A$ 

                                  $(OR)$   

 

       $AC\rightarrow G$

          $D\rightarrow E$

          $D\rightarrow G$

          $BC\rightarrow D$

         $CG\rightarrow D$

         $CG\rightarrow B$

,       $ACD\rightarrow B$

         $CE\rightarrow G$

         $CE\rightarrow A$

In this case, we got

 minimal cover are:

     $AC\rightarrow G$

       $D\rightarrow EG$      

       $BC\rightarrow D$     

        $CG\rightarrow B$   

        $CE\rightarrow A$ 

So,number of minimal cover are $2$

Comments

@Lakshman Patel RJIT

I got one minimal cover

$A\rightarrow G$

$D\rightarrow EG$

$B\rightarrow D$

$C\rightarrow D$

$AC\rightarrow B$

$CE\rightarrow A$

$CE\rightarrow G$

Now chking any more remaining or not

https://www.geeksforgeeks.org/canonical-cover/

@Shaik Masthan @Soumya29 @minal

Check this

---

please see my answer.

---

sir while taking 2nd possible FD why you r not changing the order of CE-> AG part

Answer 3

IF THE GIVEN FDS IS F1 AND THE MINIMAL COVER FDS IS F2 ,THEN F1 MUST BE EQUIVALENcE TO F2.SO IF THE OPTION IS GIVEN THEN DIRECTLY YOU CAN CHECK WHETHER THE FDS ARE EQUIVALENCE BUT IF IT IS NUMERICAL TYPE QUESTION TO FIND NUMBER OF SUCH MINIMAL COVER ,THEN YOU HAVE TO SOLVE IT.

Comments

how to solve?

can u solve it please

---

https://gateoverflow.in/242802/made-easy-test-series

check this out.

Answer 4

4 minimal cover

Comments

Will you please elaborate!

---

what's the answer?

---

4 is correct

Answer 5

The posssible keys are ACF,BCF,DCF,ECF,GCF.