IAE Academy

GATE 2026 CS2 Q.42: solution and answer

GATE 2026 · CS2Q.42 · 2 marks · MCQ

In the context of schema normalization in relational DBMS, consider a set F of functional dependencies. The set of all functional dependencies implied by F is called the closure of F. To compute the closure of F, Armstrong's Axioms can be applied. Consider X, Y, and Z as sets of attributes over a relational schema. The three rules of Armstrong's Axioms are described as follows.

Reflexivity: If Y ⊆ X, then X → Y
Augmentation: If X → Y, then XZ → YZ for any Z
Transitivity: If X → Y and Y → Z, then X → Z

The additional rule of Union is defined as follows.
Union: If X → Y and X → Z, then X → YZ

It can be proved that the additional rule of Union is also implied by the three rules of Armstrong's Axioms. Listed below are four combinations of these three rules. Which one of these combinations is both necessary and sufficient for the proof?

  1. (A)

    Reflexivity, Augmentation, and Transitivity

  2. (B)

    Reflexivity and Augmentation

  3. (C)

    Transitivity

  4. (D)

    Augmentation and Transitivity

See the question in the paper

Answer and solution

ANSWER

The answer is (D): Augmentation and Transitivity.

Official answer: DSource: Official answer key, GATE 2026 CS2 (IIT Guwahati)

  1. Given and , we must derive .

  2. Augment with : , that is . (Augmentation)

  3. Augment with : . (Augmentation)

  4. Apply transitivity to and : . (Transitivity)

  5. This derivation uses only Augmentation and Transitivity, so these two are sufficient and Reflexivity is not needed. Options A and B are therefore not 'necessary' combinations, since each includes Reflexivity or lacks Transitivity.

  6. Augmentation is necessary. Without it, the only rules left are Reflexivity (which gives trivial dependencies) and Transitivity (which only chains dependencies already present). Starting from and , with , and arbitrary disjoint attribute sets, these can never create a dependency with on the right.

  7. Transitivity is necessary. With only Reflexivity and Augmentation, every dependency obtained from and has the form or (or a trivial one). To have the left side exactly , must lie inside , so the right side is or together with part of . It never contains both and , so is not reached. The step that joins to needs Transitivity.

  8. So the combination that is both necessary and sufficient is Augmentation and Transitivity: option (D).

KEY IDEA

Union is derived by augmenting with to get , augmenting with to get , then chaining the two by transitivity. Reflexivity never appears.

WATCH OUT FOR

Choosing (A) because the textbook calls the three axioms together 'complete'. The question asks which rules the proof of Union needs, and Reflexivity is not one of them.

From the GATE 2026 CS2 paper. Every question of this paper · Download the full paper · All 19 Normal forms questions, with notes

More Normal forms questions