GATE CS Normalization and Normal Forms Previous Year Questions

GATE CS 2025 Set 1 | Question 47

MSQ · 2 marks

Consider a relational schema \(team(name, city, owner)\), with functional dependencies \(\{name \to city,\ name \to owner\}\).

The relation \(team\) is decomposed into two relations, \(t1(name, city)\) and \(t2(name, owner)\). Which of the following statement(s) is/are TRUE?

The relation \(team\) is NOT in BCNF. The relations \(t1\) and \(t2\) are in BCNF. The decomposition constitutes a lossless join. The relation \(team\) is NOT in 3NF.

Explanation

Answer: (B), (C)

Key: \(name^+ = \{name, city, owner\}\), so \(name\) is a candidate key of \(team\). Both FDs have this key on the left, so \(team\) is already in BCNF, and therefore in 3NF too. So (A) and (D) are false.
(B) True: in \(t1\) the only FD is \(name \to city\) and in \(t2\) it is \(name \to owner\); in each, \(name\) is a key. (Any relation with just two attributes is in BCNF anyway.)
(C) True: the common attribute of \(t1\) and \(t2\) is \(name\), which is a key of \(t1\) (and of \(t2\)), so joining them on \(name\) gives back exactly the original relation.

Answer: B, C

GATE CS 2025 Set 2 | Question 46

MSQ · 2 marks

Consider the following relational schema along with all the functional dependencies that hold on them.

R1(A, B, C, D, E): \(\{D \to E,\ EA \to B,\ EB \to C\}\)

R2(A, B, C, D): \(\{A \to D,\ A \to B,\ C \to A\}\)

Which of the following statement(s) is/are TRUE?

R1 is in 3NF R2 is in 3NF R1 is NOT in 3NF R2 is NOT in 3NF

Explanation

Answer: (C), (D)

A relation is in 3NF if, for every non-trivial FD \(X \to Y\), either \(X\) is a superkey or every attribute of \(Y\) is prime (part of some candidate key).

R1: \(A\) and \(D\) appear on no right-hand side, so every key contains both, and \(\{A, D\}^{+} = \{A, B, C, D, E\}\). The only key is \(AD\). In \(D \to E\), \(D\) is not a superkey and \(E\) is not prime, so R1 is NOT in 3NF (it is not even in 2NF).
R2: \(C\) appears on no right-hand side and \(C^{+} = \{A, B, C, D\}\), so \(C\) is the only key. In \(A \to D\), \(A\) is not a superkey and \(D\) is not prime: the transitive dependency \(C \to A \to D\). So R2 is NOT in 3NF.

Answer: C, D

GATE CS 2024 Set 1 | Question 22

MSQ · 1 mark

Which of the following statements about a relation R in first normal form (1NF) is/are TRUE ?

R can have a multi-attribute key R cannot have a foreign key R cannot have a composite attribute R cannot have more than one candidate key

Explanation

Answer: (A), (C)

First normal form asks only that every attribute hold atomic (indivisible) values, so a 1NF relation has no composite or multivalued attributes. It says nothing about keys.

A: true. A key made of several attributes, such as (RollNo, CourseNo), is allowed; atomicity is about values, not keys.
B: false. A relation in any normal form may have a foreign key referring to another relation.
C: true. A composite attribute such as Address (street, city, PIN) is not atomic, so in 1NF it must be split into simple attributes.
D: false. A relation can have several candidate keys, for example both RollNo and Email in a student table.

Answer: A, C

GATE CS 2024 Set 1 | Question 44

MSQ · 2 marks

The symbol \(\to\) indicates functional dependency in the context of a relational database. Which of the following options is/are TRUE?

\((X, Y) \to (Z, W)\) implies \(X \to (Z, W)\) \((X, Y) \to (Z, W)\) implies \((X, Y) \to Z\) \(\big((X, Y) \to Z \text{ and } W \to Y\big)\) implies \((X, W) \to Z\) \((X \to Y \text{ and } Y \to Z)\) implies \(X \to Z\)

Explanation

Answer: (B), (C), (D)

A is false. The left side of a dependency cannot just be shrunk. In a relation with the tuples \((X, Y, Z, W) = (0, 0, 0, 0)\) and \((0, 1, 1, 1)\), \((X, Y) \to (Z, W)\) holds because the tuples differ on \((X, Y)\), but \(X \to (Z, W)\) fails.
B is true by decomposition: whatever determines \((Z, W)\) also determines \(Z\).
C is true (pseudo-transitivity). Augmenting \(W \to Y\) with \(X\) gives \((X, W) \to (X, Y)\), and with \((X, Y) \to Z\) this yields \((X, W) \to Z\).
D is true by transitivity, one of Armstrong’s axioms.

Answer: B, C, D

GATE CS 2024 Set 2 | Question 56

NAT · 2 marks

A functional dependency \(F\colon X \rightarrow Y\) is termed as a useful functional dependency if and only if it satisfies all the following three conditions:

\(X\) is not the empty set.
\(Y\) is not the empty set.
Intersection of \(X\) and \(Y\) is the empty set.

For a relation \(R\) with 4 attributes, the total number of possible useful functional dependencies is ________

Your answer

Explanation

Answer: 50

Since \(X\) and \(Y\) must be disjoint, a dependency is fixed by giving each of the 4 attributes one of three roles: in \(X\), in \(Y\), or in neither. That gives \(3^{4} = 81\) assignments. Remove those with an empty side by inclusion–exclusion:

\(X\) empty: each attribute is in \(Y\) or in neither, \(2^{4} = 16\) ways;
\(Y\) empty: likewise 16 ways;
both empty: 1 way, subtracted twice above, so add it back.

Useful dependencies: \(81 - 16 - 16 + 1 = 50\).

Answer: 50