MadeEasy Test Series: Databases - Super Keys

Question

Consider a relation $R$ with $2n$ attributes. Assume any $2n/2$ of the attributes constitutes key. Total number of super keys possible are:

1. $^{2n}C_{2^{n-1}}\times \left(2\right)^{2^{n-1}}$
2. $^{2n}C_{2^{n-1}} + \left(2\right)^{2^{n-1}}$
3. $^{2n}C_{2^{n-1}} - \left(2\right)^{2^{n-1}}$
4. $^{2n}C_{2^{n-1}} \div \left(2\right)^{2^{n-1}}$

Comments

I think by 2n they mean 2^n(because otherwise no option matches)

Answer 1

Well I think there is a typo in question ....

as per the given answer..:p

the question should be

There are 2^n attributes in a relation R,... Any combination (2^n)/2 (i.e 2^(n-1)) keys forms a candidate key then

number of candidate keys---> $\binom{2^{n}}{2^{n-1}}$

remaining attributes --> $2^{n}-2^{n-1}= 2^{n-1}$

any of the subset could be taken for a superkey

therefore number of subsets $2^{2^{n-1}}$

therefore total number of superkeys  $\binom{2^{n}}{2^{(n-1)}}*2^{2^{n-1}}$

Comments

Can't the summation be evaluated?

---

Please verify the summation ...I solved it this way..-->

In a binomial expansion terms repeats after the middle term .For eg. the pascal triangle

1--->$\binom{n}{0}$

1 1---> $\binom{n}{0} \binom{n}{1}$

1 2 1.....

1 3 3 1...

So for summing sequence having odd terms (as the summation from $\binom{2^{n}}{0} to \binom{2^{n}}{2^n}$ will have odd number of terms from 0 to 2^n)

$\displaystyle\sum_{k= 0}^{2^{n}}\binom{2^{n}}{k}$

= $\displaystyle\sum_{k= 0}^{2^{n-1}-1}\binom{2^{n}}{k}$ + $\binom{2^{n}}{2^{n-1}} + \displaystyle\sum_{k= 2^{n-1}+1}^{2^{n}}\binom{2^{n}}{k}$    

{ just broke the summation in three parts let us call them I, II, III where first summation term and last summation will be equal} 

now we need to find out II+III, 

I term = lII term = $(1/2)*\left ( \displaystyle\sum_{k= 0}^{2^{n}}\binom{2^{n}}{k} -\binom{2^{n}}{2^{n-1}}\right )$

therefore 

II+III term =$\binom{2^{n}}{2^{n-1}}$ + $1/2*\left ( \displaystyle\sum_{k= 0}^{2^{n}}\binom{2^{n}}{k} -\binom{2^{n}}{2^{n-1}}\right )$

=$(1/2)*\left ( 2^{2^{n}} + \binom{2^{n}}{2^{n-1}} \right )$

---

yes, the summation is correct. Option B would have been correct with 0.5 on the left term.

Answer 2

Candidate key:- it is the minimal super key which can identify each tuple uniquely. A table can have more than one candidate kr possible.

As it is minimal, any attribute attach to it will make it a super key.

So here out of 2n attributes we can have any 2n/2 attributes as candidate key.therefore can select the attributes in   2nC(2n/2) ways .

Attributes left - 2n/2

Now any attribute attach with any candidate keys will make them super key.

So for each attributes we can have 2 choices either  include them or leave them

So for 2n/n attributes total way to select: 2^2n/2

Total super key: 2nC(2n)/2 *2^2n/2