Made Easy Test Series:Database-Super-Keys

Question

Consider the relation $R\left ( A,B,C,D,E \right )$

$A\rightarrow BC$

$C\rightarrow E$

$B\rightarrow D$

$E\rightarrow A$

Total number of superkeys present in relation will be ____________________

Comments

28?

---

yes, explain

---

There are 3 candidate keys, A,C and E.

Use inclusion-exclusion:

Number of superkeys using A= $2^{4}$ (Same for C and E)

Number of superkeys using both A and C= $2^{3}$ (Same for AE and CE)

Number of superkeys using all three A,C and E = $2^{2}$

$2^{4}$ + $2^{4}$ + $2^{4}$ - $2^{3}$- $2^{3}$ -$2^{3}$ + $2^{2}$

=28

Answer 1

First, find candidate key and they are A,C,E

According to the principle of inclusion and exclusion,

           ∣A ⋃ C ⋃ E∣ = |A| + |C| + |E| - |A ⋂ C| - |A ⋂ E|  - | C ⋂ E| + |A ⋂ C ⋂ E|

                                 = No. of super key using A + No. of superkey using C + No. of superkey using E - No. of superkeys  using A                                               and C - No. of super keys  using A and E - No. of superkeys  using C and E

                                          + No. of super keys using A,C,E

                                 = $2^{n-1}$ + $2^{n-1}$ + $2^{n-1}$ - $2^{n-2}$ - $2^{n-2}$ - $2^{n-2}$ + $2^{n-3}$ , Here n = 5 (No. of attributes in a relation)

                                 = $2^4$ + $2^4$  + $2^4$ - $2^3$ - $2^3$ - $2^3$ + $2^2$

                                 = 28

So the answer is : 28

Note: In general, if we have ‘N’ attributes with one candidate key then the number of possible superkeys are $2^{n-1}$.

Comments

Means candidate key with any other attribute makes superkey.

right?

A with any other attribute i.e. B,C,D,E makes a super key

So, it will be $2^{4}$

rt??

---

In general, if we know a candidate key then the number of possible superkeys are $2^{n-1}$ , where n= total no. of attributes in a relation.

Let me explain through a simple example...

i) Consider Relation R=(A,B,C,D) where A is a candidate key. Find the total number of possible superkeys?

Total no. of super keys = $2^{n-1}$ , where  n= 4

                                      = $2^{4-1}$

                                      = $2^{3}$ = 8

ii) Let a Relation R have attributes {a1, a2, a3,…,an} and the candidate key is “a1 a2 a3” then the possible number of super keys?

 Following the previous formula, we have 3 attributes instead of one. So, here the number of possible           superkey is  $2^{n-3}$.

---

'A' with any other attributes doesn't make a superkey. We can find superkeys from all the candidate keys not from all the attributes of a relation.

Answer 2

Here, Candidate Keys = $ \{ A, E, C\} $

Prime Attributes = $ \{ A, E, C\} $
Non-Prime Attributes = $ \{ B, D\} $

Combinations with only Prime Attributes $= \binom{3}{1} + \binom{3}{2} + \binom{3}{3} = 3+3+1 = 7$
Now, for total combinations $\rightarrow$ A_C_E (B and D can either be present or not present = $2^2$ Combinations)

Therefore, # Superkeys $= 7 * 2^2 = 28$