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 ______________ .

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.