Questions on Super keys

Questions on Super keys – Question 1 : Relational schema R with n attribute A1, A2,…,A_n. How many super keys are possible with a) only candidate keys A1 b) only Candidate Keys A1, A2 c) only Candidate keys (A1A2), (A3A4) d) only candidate keys (A1A2), (A2,A3) e) only candidate keys A1,A2,A3 ∩∪⇒ Solution : a) only Candidate Keys A1 A1 A1A2 A1A3 A1A2A3 A1A2A3…..A_n

Common Attributes - {A2,A3,....An} = 2n-1 

So, Total Number of combinations of attributes that contains {A1} ⇒ 1 * 2{n-1} = 2{n-1}

b) only candidate keys A1,A2

(Table 1) Super Keys possible with only candidate key A1

A1 A1A2 A1A3 A1A2A3 A1A2A3……An

⇒ 2n-1

 

(Table 2) Super Keys possible with only candidate key A2

A2 A2A1 A2A3 A2A1A3 A2A1A3……An

⇒ 2n-1

 

Common Super Keys From Table 1 and Table 2  ⇒ {A3A4….An} = 2n-2 

So, Total Number of combinations of attributes that contains {A1}, {A2} or {A1,A2} ⇒ 3 * 2(n-2}

3 * 2(n-1)  can be written as  = (2+1) * 2(n-1) = 2.2(n-1) + 1.2(n-1) = 2(n-2) + 2(n-1)

So, From the above observation, if there are n attributes and m candidate keys, then the possible superkeys with m candidate keys will be –

2n-1 + 2n-2 + 2n-3 + ………… + 2n-m

Another Solution with the help of Venn Diagram : c) only candidate keys (A1,A2), (A3,A4)  d) Only Candidate keys (A1A2),(A2A3) e) only candidate keys A1,A2,A3 Question 2 : Relational scheme R with N attribute A₁A₂….A_n. If every attribute is the Candidate Key, then how many superkeys are possible?  {DRDO} Solution : Let R(ABC), so A B C AB BC AC ABC =7 =2³-1 It implies, 2ⁿ-1 Super Keys. Why 2ⁿ-1? because Total Number of Subsets possible with n elements = 2ⁿ But It includes Ø, However in case of SuperKey atleast 1 key is mandatory. As every attribute is candidate key, So,

2n-1

Question 3: Consider a Relational Schema R with attributes A,B,C,D,E.  How many super keys  are possible if {A,B,C} : Candidate Keys Solution : 3 Candidate Keys out of 5 attributes – resembling the state as m candidate keys out of n attributes. So, By applying the above formula, we get the following results –

A	B	C
25-1=16	25-2=8	25-3=4

=16+8+4=28 Verification :

A	B	C
AB AC AD AE	BC BD BE BA	CD CE CA CB
ABC ABD ABE ACD ACE ADE	BCD BCE BDE ABC ABD ABE	CDE ABC ACD ACE BCE BDE
ABCD ABCE ABDE ACDE	BCDE ABCD ABCE ABDE	ABCD ABCE ACDE BCDE
ABCDE	ABCDE	ABCDE
16	8	4

  Question 4 : How many Superkeys are possible with only candidate keys A1,A2,A3,A4 if there are n attributes in a Relational Schema R? Explain the solution with the help of Venn Diagram. Solution : ]]>