GATE CSE 2026 | Set 1 | Question: 55

Question

Consider a relational database schema with a relation $R(A, B, C, D)$. If $\{A, B\}$ and $\{A, C\}$ are the only two candidate keys of the relation $R$, then the number of superkeys of relation $R$ is $\_\_\_\_$.  (answer in integer)

Answer 1

To find the number of superkeys for the relation $R(A, B, C, D)$ with candidate keys $\{A, B\}$ and $\{A, C\}$, we use the Principle of Inclusion-Exclusion.

1. Basic Concepts

• Relation $R$: Contains 4 attributes $\{A, B, C, D\}$. Thus, $n = 4$.

• Candidate Key (CK): A minimal set of attributes that uniquely identifies a tuple. Any superset of a candidate key is a superkey.

• Formula: If a candidate key has $k$ attributes, the number of its superkeys in a relation with $n$ attributes is $2^{n-k}$.

---

2. Calculation Steps

Let:

• $S_1$ be the set of superkeys containing $\{A, B\}$.

• $S_2$ be the set of superkeys containing $\{A, C\}$.

Step 1: Superkeys containing $\{A, B\}$

The candidate key $\{A, B\}$ has 2 attributes. The remaining attributes are $\{C, D\}$ (2 attributes).

The number of superkeys is:

$$|S_1| = 2^{4-2} = 2^2 = 4$$

(These are $\{AB\}, \{ABC\}, \{ABD\}, \{ABCD\}$)

Step 2: Superkeys containing $\{A, C\}$

The candidate key $\{A, C\}$ has 2 attributes. The remaining attributes are $\{B, D\}$ (2 attributes).

The number of superkeys is:

$$|S_2| = 2^{4-2} = 2^2 = 4$$

(These are $\{AC\}, \{ACB\}, \{ACD\}, \{ACBD\}$)

Step 3: Common Superkeys

These are superkeys that contain both candidate keys $\{A, B\}$ and $\{A, C\}$.

This is equivalent to superkeys containing the union $\{A, B\} \cup \{A, C\} = \{A, B, C\}$.

The union $\{A, B, C\}$ has 3 attributes. The remaining attribute is $\{D\}$.

The number of common superkeys is:

$$|S_1 \cap S_2| = 2^{4-3} = 2^1 = 2$$

(These are $\{ABC\}$ and $\{ABCD\}$)

---

3. Final Answer

Using the Principle of Inclusion-Exclusion:

$$\text{Total Superkeys} = |S_1| + |S_2| - |S_1 \cap S_2|$$

$$\text{Total Superkeys} = 4 + 4 - 2 = 6$$

The number of superkeys of relation $R$ is 6.

 

 

Comments

best explanation

Answer 2

The number of superkeys containing candidate key AB = 2² = 4

The number of superkeys containing candidate key AC = 2² = 4

Number of common super keys which contains both candidate key = 2

Total number of superkeys are = superkeys keys from ck AB + superkeys from CK AC - common superkeys from CK (AC and AB)

                                                       = 4+4-2=6

Answer 3

Given:-

R(A, B, C, D) 

Candidate Key = {A, B}, {A, C}

To Find :- Total No. of Super Key

Solution:-

Super Key = {AB, AC, ABC, ABD, ACD, ABCD}

Therefore, Total no. of Super Keys = 6

Answer 4

Number of Super Key Can Be count like this 

 

Answer 5

2^2+2^3-2 = 6