To calculate how many no of super keys?

Question

a relation R(A,B,C,D,E,F,G,H)

and set of functional dependencies are {CH->G,A->BC,B->CFH,E->A,F->EG }

then how many possible super keys are present ?

Comments

is it 120 super keys rt ?

---

120 superkeys..it is application of set theory

---

@pooja can u verify my solution given below  by the way my answer is 120

Answer 1

We know, P(A ⋃ B ⋃ C ⋃ D) = P(A) + P(B) + P(C) + P(D) - P(A∩B) - P(B∩C) - P(C∩D) - P(D∩A) + P(A∩B∩C) + P(B∩C∩A) + P(C∩D∩A) - P(A∩B∩C∩D)

Here candidate keys are (AD) , (BD) , (ED) , (FD)

No. of super keys 2^{n-(size of candidate key)} [n=no. of keys]

Here 2^8-2 =2⁶ ⨉ 4=256 [As 4 such candidate keys available]....................i

Now use set operation to eliminate duplicate key

Now by (AD) , (BD) , (ED), (FD) duplicate keys of 3 element dulpicate keys possible 6. those are (ABD),,(ADE) , (ADF), (EDB),(EDF), (BDF)

No more 3 element keys are possible.

So, super keys are 2^8-3 ⨉6 = 192...................................ii

Similarly 4 element keys are (ADEB) , (ADEF) , (EBDF) , (ADBF)

Now no of super keys are  2^8-4⨉4=64................................iii

Now 5 element key (ABDEF)

No. of super keys 2^8-5⨉1=8.........................iv

Now just putting it into formula of set 256 - 192 + 64 -8 =120

Comments

@srestha trying for candidate keys {AB, BC, CD, AD} ?

---

because candidate keys are minimal superkeys.

like {AB} U ∅ ={AB}

{AB} U{BD}={ABD}......those all are super keys. right?

---

yes..

---

for the maximum number of candidate keys we can do like this:

maximum possible keys with 1 attribute assuming set $\{A,B,C,D\}\rightarrow A,B,C,D $

maximum possible keys with 2 attribute assuming set $\{A,B,C,D\}\rightarrow AB,AC,AD,BC,BD,CD$

maximum possible keys with 3 attribute assuming set $\{A,B,C,D\}\rightarrow ABC,ACD,ABD,BCD$

maximum possible keys with 4 attribute assuming set $\{A,B,C,D\}\rightarrow ABCD$

here we can clearly see when half attributes are taken candidates keys are maximum

so we can conclude that the max number of Candidates keys with $n$ attributes are $\binom{n}{n/2}$

Answer 2

First finding out candidate keys.

D is not present at RHS of any FD. So, it must be present in any key.

AD -> BCDEFGH, hence AB is a candidate key.

Due to E -> A, ED is another candidate key.

F->E makes FD another candidate key and similarly B->F makes BD also a candidate key.

Thus we get {AD, ED, FD, BD} as candidate keys.

Now any superset of a candidate key is a super key.

In each of the above we can add any subset of the 6 remaining elements (excluding the 2 considered for the candidate key) and we get a superkey. No. of subsets of a 6 element set $=2^6 = 64$. And 4 times this should be $4 \times 64 = 256.$.

But in the above case for AD, we have considered the super key ADE and similarly for ED we have considered EDA. Similarly for {ADF, FDA} and {ADB, BDA}. Each of these would correspond to $2^5 = 32$ cases being repeatedly added (any combination of remaining 5 elements). Thus $3 \times 32 = 96$ subtractions needed. But we have done subtraction for the cases ADEF, ADEB, ADFB twice. So, have to add $3 \times 2^4 = 48.$ Here, we again do common addition for ADEFB and this requires subtraction of 8. 

Similarly we require $2 \times 32 $ subtractions and 16 additions for {EDF, FDE}, {EDB, BDE} and 32 subtractions for {FDB, BDF} giving 256 - 96 + 48 - 8 - 64 +16 - 32 = 120 possible super keys.

I'll give a better way :)

---

The question is an application of Inclusion-Exclusion principle. Here, the 4 candidate keys correspond to 4 sets each with 64 elements. Now, the set of all super keys will be (W = AD, X = ED, Y = FD, Z = BD)

$|W \cup X \cup Y \cup Z| = |W | + |X| + |Y| + |Z| - |W \cap X| - |W \cap Y| - |W \cap Z| - |X \cap Y| - |X \cap Z| - |Y \cap Z| + |W \cap X \cap Y| + |W \cap X \cap Z| + |W \cap Y \cap Z| + |X \cap Y \cap Z| - |W \cap X \cap Y \cap Z|$

Now, $|W \cap X| = |ADE| = 2^5 = 32$ 

Also, $ |W \cap X| =  |W \cap Y| =  |W \cap X| =  |X \cap Y| =  |X \cap Z| =  |Y \cap Z|$

$ |W \cap X \cap Y| = |ADEF| = 2^4 = 16. $

Also, $|W \cap X \cap Y| =|W \cap X \cap Z| =|W \cap Y \cap Z| =|X \cap Y \cap Z|$

$ |W \cap X \cap Y|= |ABDEF| = 8.$

So, $|W \cup X \cup Y \cup Z| = 4 \times 64 - 6 \times 32 + 4 \times 16 - 8 = 256 - 192 + 64 - 8 = 120.$

 

Comments

sir, i think u have mistaken to add ABFD and EFBD and also to subtract common ABEFD ,

by including these three operation i m getting 120 superkeys , sir, plzz guide me i m not getting its solution anywhere

---

yes, I have corrected, but its brute force method. 

See http://www.saylor.org/site/wp-content/uploads/2012/06/MA111_Wikipedia_Inclusion-Exclusion-Principle_6.8.2012.pdf

---

thanks a lot sir

Answer 3

here no of candidate key are 4 which is (AD), (BD), (ED), (FD)

Then no of super key due to AD is 2^n-2 where n is no of attribute so 2^6

same no for BD ,ED,FD  so 4* (2^6)  and due to ABD,AED,AFD,BED,BFD,EFD IS - 6(2^5)

and due to ABED,AEFD,AEFD,ABFD is+4*(2^4)   and finally with ABEFD IS -(2^3)  SO total super keys are 

 4* (2^6)- 6(2^5)+4*(2^4)-(2^3)   is the answer  and such type question never be asked in gate they always intrested to find out the no of candidate key

Comments

thanks srestha , i have commented because rajan has edited correct it later , thanks for giving solution

---

rajan now u have done correct , now its right when u have edited ur answer which i was discussing earlier

---

i have done correct it 24 hours before but i think you dont see it by the way  your most welcome

Answer 4

I think n+1

Comments

what is n , and how?

---

Sorry it's 2ⁿ... Max possible superkeys

None of the functional dependency has attribute D on the RHS. So D must be present in a superkey. 

1) AD⁺= ABCDEFGH

2) BD⁺= ABCDEFGH

3) CD⁺= CD

4) DE⁺= ABCDEFGH

5) DF⁺= ABCDEFGH

Except 3, remaining all are keys. They can derive complete set with any combination. So for length 2, the super keys are 4.

For length 3, any of the above 2 length keys plus one more attribute from the remaining attributes i.e. 6. 

Like wise superkeys with length 4 are 15, length 5 are 20, length 6 are 15, length 7 are 6 and length 8 is 1.

Altogether, 67 super keys. If wrong please correct me... 

---

ADB
ADC
ADE
ADF
ADG
ADH
BDC
BDE
...
all are super keys rt?