Redirected
5,281 views
1 votes
1 votes
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___________?

5 Answers

2 votes
2 votes
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
1 votes
1 votes

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$

edited by
0 votes
0 votes
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.

Related questions

0 votes
0 votes
1 answer
1
Mrityudoot asked Jan 12
128 views
Isn’t F$^{+}$ minimal cover? If C $\rightarrow$ A is already there, then why does augmented CD $\rightarrow$ A needs to be?
0 votes
0 votes
1 answer
2
1 votes
1 votes
1 answer
3
Sajal Mallick asked Nov 5, 2023
336 views
Unique not null is equivalent to primary key.Relational Algebra and SQL has same expressive power.Which of the above statements are False?
2 votes
2 votes
1 answer
4
kaustubh7 asked Sep 20, 2023
401 views
Consider a relation R having seven attributes ABCDEFG. Fields of R contain only atomic values.FDs = {CD → G, A → BC, B → CF, E → A, F → EG, G → D} is set of f...