GATE CSE 2022 | Question: 21

Question

Consider a relation $R (A, B, C, D, E)$ with the following three functional dependencies.

$AB \rightarrow C; \; BC \rightarrow D; \; C \rightarrow E;$

The number of superkeys in the relation $R$ is ______________ .

Comments

Candidate Key  = AB
possible super keys = AB _ _ _  => 2^n  (here n = 3)   => 8

Answer 1

Answer : 8

---

AB → C

BC → D

C → E

are the FDs in the question. If you observe the given FD set, A and B are Independent attributes.

$\therefore$ every key must contain A and B.

Let’s compute Keys of the relations :

$(AB)^+ = ABCDE$

Indepent Attributes form the Key, then It is unique and minimal candidate key.

 

There are 3 more attributes in the given relation, So adding them to Candidate Key results Super key.

Every attribute has two choices (either add to candidate key or left it), and there are 3 such attributes

$\therefore$ No.of super keys = 2.2.2 = 8

Note that Every candidate Key is also Super Key.

 

Alternatively you can think like, set S = {C,D,E} (which are non prime attributes) and it’s power set must contains $2^3=8$ elements

$P(S) = \{\phi, \{C\},\{D\},\{E\},\{CD\},\{CE\},\{DE\},\{CDE\}\}$

Any Subset combining with ‘AB’ will form one distinct super key.

Comments

Nice, alternative way is much better as it combines with set theory concepts which is also an integral part of functional dependencies.

---

But if u combine phi with AB wont that just be AB which is a candidate key, it cannot be super key right?

---

@Pradyumna_1, Every candidate key is a super key itself.

---

So AB itself is candidate and super key !!

Answer 2

simple method

Comments

Great Thnks for ur efforts

Answer 3

As per the RHS, the attributes not belonging in RHS will definitely be in Candidate key. 

So, AB will be in Candidate key.

Perform closure (AB)+ = {A,B,C,D,E} 

AB is itself a Candidate Key. No other combination of size 2 or smaller exist in relation. So only 1 Candidate key

Super key is the key which can derive all attribute in a Relation. So basically Candidate key + Other attributes.

1. Minimal Super key =  Candiate Key = AB (Size = 2)
2. Super key size 3 = ABC, ABD, ABE
3. Super key size 4 = ABCD,ABCE, ABDE
4. Super key size 5 = ABCDE

 

Answer = 1 + 3 + 3 + 1 = 8

Comments

Thanks for ur efforts great one

Answer 4

Number of super keys possible = 2^ n- k where k = size of candidate key n is number of elements here AB is C.K size = 2 so 2^5-2 = 2^3 = 8 answer Fastest method

Comments

can u explain full concept to find each superkey 

Answer 5

Given :- R(A, B, C, D, E)

Functional Dependencies :- AB -> C; BC -> D; C -> E

To Find :- No. of Super Key

 

Step 1 :- Find Candidate Key

(AB)⁺ = {A, B, C, D, E}

∴ Candidate Key = {AB}

 

Step 2 :- Find Super Key

∵ Candidate Key = {AB}

∴ Super Key = 2³ = 8 => {AB, ABC, ABD, ABE, ABCD, ABCE, ABDE, ABCDE}

 

∴ No. of Super Keys = 8