search
Log In
Redirected from merged question 273396
0 votes
1.7k views
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___________?
in Databases 1.7k views
0

As CG->B is redundant so we remove it and after removing this CG->D becomes essential. So CG->D will be there in both the minimal covers. In case of the FD ACD->B, D is extraneous attribute since (AC)+ contains B; so we will have AC->B in one of the minimal covers. Also A is an extraneous attribute since (CD)+ contains B; so we will have CD->B in one of minimal covers.

0

@Somoshree

CG->D becomes essential

where is it present  minimal cover given by @Magma

A is an extraneous attribute

how A can be extronious? 

1

@Srestha maam, @Magma missed out the FD CG->D initially, she then rectified it in her comments.

A is extraneous because (CD)+={C,D,E,G,A,B}. this closure is obtained by using the FDS: D->E,D->G,CE->A,ACD->B. since we are being able to determine B even without having A in the LHS of the FD ACD->B, hence A is redundant and so can be removed from this FD.

1

@Srestha maam, Consider it this way: (ACD)+={A,C,D,B,E,G}. Now remove A from ACD and find out the closure of the remaining part of LHS i.e. (CD)+={C,D,B,E,G,A}. Since deletion of attribute A from the lhs of the FD ACD->B resulted in no change in the attributes that can be determined(i.e. system is in the same state with or without A), so hence A can be removed as it is extraneous.

0
yes A also be extronious

then finally what will be minimal cover?
0
Answer given is 2.

But I want to know how we should calculate it in simple way
0
do u knw how to find minimal cover ?
0

I'm also getting only one
see this https://gateoverflow.in/271091/gatebook-2019-dbms2-10
what is the answer?

0
is the ans 2?
0
can you share another one?
0

{ACD->B,AC->G,BC->D,D->EG,CE->A}

@Lakshman Patel RJIT

the link u mentioned is not opening!

0

yes answer is 2.

0
I'm not getting the procedure?

and I'm try to do some other way
0
same,i also doing in 3 phases in first phase CG->D,ACD->B,CE->G removed

we cant CG->B as B is only in RHS in this production only

We cant CE->A for same reason so i m not noticing any multiplicity/prallalism any.
1
please wait some time i will explain and add the answer,ok?
0
Answer: 7
0

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

Only 2 minimal covers possible.

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

plz explain this soln?

5 Answers

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
0

@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.

 

1 vote

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

@ ma'am

@

@

@

Please see my solution and verify where I'm wrong?

0

@Lakshman Patel RJIT Awesome Brother!

0

@

answer will be $2$ (or) $4?$

0
I am also getting 2 But in madeEasy explanation they are saying 4 as answer
0

you see   comment in top,they add madeeasy answer as well,

0

In my solution portal this is the solution they have provided.

1
How $CE\rightarrow AF$?
0

in the first part of finding out the minimal cover, u claimed that D is redundant attribute and so we can remove D from ACD->B. Isnt A also a redundant attribute as if we take the closure of CD, we can derive A?

So we could have removed A also right in place of D?

 

0
Yeah, but at a time we can remove $D$ or $A$
0
yaa..thats fine..but if we consider A as redundant there, then in the next step while finding out redundant FDs again,AC->G doesnt become redundant anymore..So would this be considered as a minimal cover also if we consider A as redundant attribute instead of D?
0
Yes, and we get more I think.
0
u mean we will get more minimal covers by considering A as redundant attribute?
0
i think we get more

i'm not sure
0
ok..I have one more doubt:

You have considered interchanging the orders of CG->B and CG->D..why didnt u consider interchanging the orders of CE->A and CE->G and also D->E and D->G? Is it becoz that even after interchanging their orders they result in the same minimal covers?
0
might be possible lets find out!
0
yes they give same.
0
ok..thanks!
0
$AC\rightarrow G,D\rightarrow EG,BC\rightarrow D,CG\rightarrow D,CD\rightarrow B,CE\rightarrow A$ is also possible
0

@Soumya29

please help in this question.

0

@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

0
please see my answer.
0
sir while taking 2nd possible FD why you r not changing the order of CE-> AG part
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.
0
how to solve?

can u solve it please
0
0 votes
4 minimal cover
0
Will you please elaborate!
0
what's the answer?
0
4 is correct
0 votes
The posssible keys are ACF,BCF,DCF,ECF,GCF.

Related questions

1 vote
0 answers
1
264 views
Number of tables required in above ER diagram will be _____________ Is $R_{1}$ create separate table or not?? and $R_{2}$ look like if we remove loop from it?? Answer given for table $E_{1}R_{1}$ Key will be $AC$ , with $C$ foreign key. And for ... $2$ Entities. So, it will add one extra table. I already read https://gateoverflow.in/229580/madeeasy-test-series-number-of-tables-required
asked May 22, 2019 in Databases srestha 264 views
1 vote
2 answers
2
485 views
Consider the relation $R\left ( A,B,C,D,E \right )$ with functional dependencies $F=${ $A\rightarrow B$ $BC\rightarrow E$ $ED\rightarrow A$ } Number of additional relation required to convert it into lossless , dependency preserving $3NF$ decomposition is _____________ What is meaning of additional relation (Here no table mentioned previously)??
asked May 19, 2019 in Databases srestha 485 views
2 votes
1 answer
3
553 views
The minimum number of nodes (both leaf and non-leaf) of $B^{+}$ tree index required for storing $5500$ keys and order of $B^{+}$ tree is $8$________________(order is max pointers a node can have) See here first level should be divide by $7$ $2nd$ levelshould divide by ... each $7$ pointer of 1st level has $8$ pointer in 2nd level. Am I missing something?? But in ans they divided by only $8$ :(
asked May 17, 2019 in Databases srestha 553 views
1 vote
2 answers
4
276 views
Find the name of Sailors with a higher rating than all sailors with age $<22?$ $Query1: $ Select S.name from sailor S where not exists (Select * from sailor $S_{2} $where $S_{2}.age<22$ and $S.rating<=S_{2}.rating$) $Query2:$ Select S.name ... is correct sql for above query?? I think Query2 and Query3 itself differentiate with ANY and ALL keyword. But what about Query1? Will it return ALL tuples?
asked May 14, 2019 in Databases srestha 276 views
...