Question

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 𝑋, 𝑌, and 𝑍 as sets of attributes over a relational schema. The three
rules of Armstrong’s Axioms are described as follows.
Reflexivity: If 𝑌⊆𝑋 , then 𝑋→𝑌
Augmentation: If 𝑋→𝑌, then 𝑋𝑍→𝑌𝑍 for any Z
Transitivity: If 𝑋→𝑌 and 𝑌→𝑍, then 𝑋→𝑍
The additional rule of Union is defined as follows.
Union: If 𝑋→𝑌 and 𝑋→𝑍, then 𝑋→𝑌𝑍
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 ?

• A. Reflexivity, Augmentation, and Transitivity
• B. Reflexivity and Augmentation
• C. Transitivity
• D. Augmentation and Transitivity

Hint:

Try deriving $X \to XY$ from $X \to Y$ and $XY \to YZ$ from $X \to Z$, both using Augmentation, then chain them with Transitivity. Notice that no trivial (Reflexivity-based) dependency is ever needed in this chain.

Answer 1

The Correct Option is D

We are given two functional dependencies \(X \to Y\) and \(X \to Z\), and we must derive the Union rule \(X \to YZ\) using only the three basic Armstrong Axioms: Reflexivity, Augmentation, and Transitivity. The goal is to find which subset of these three axioms is the minimal (necessary and sufficient) set needed for the derivation.

Step 1: Start with the given dependency \(X \to Y\).

Apply the Augmentation rule by adding \(X\) itself to both sides: since \(X \to Y\) implies \(XZ \to YZ\) for any \(Z\), substitute \(Z = X\). This gives:

\[X \cup X \to Y \cup X \quad \Rightarrow \quad X \to XY\]

Step 2: Start with the given dependency \(X \to Z\).

Apply the Augmentation rule again, this time adding \(Y\) to both sides:

\[XY \to ZY \quad \Rightarrow \quad XY \to YZ\]

Step 3: Combine the two derived dependencies using Transitivity.

From Step 1 we have \(X \to XY\), and from Step 2 we have \(XY \to YZ\). Applying the Transitivity rule:

\[X \to XY \text{ and } XY \to YZ \quad \Rightarrow \quad X \to YZ\]

This is exactly the Union rule that needed to be proved.

Step 4: Check whether Reflexivity was required anywhere.

Reflexivity only states that \(X \to Y\) whenever \(Y \subseteq X\); it is used to generate trivial dependencies. In the entire derivation above, we never needed a trivial dependency of that form -- both steps used only Augmentation, and the final step used only Transitivity. So Reflexivity is not necessary for this proof.

Step 5: Conclude the minimal set of axioms.

The proof used Augmentation twice (Steps 1 and 2) and Transitivity once (Step 3), and no other axiom was required. Hence Augmentation and Transitivity together are both necessary (Augmentation is used to build \(X \to XY\) and \(XY \to YZ\), and Transitivity is used to chain them) and sufficient (nothing else is needed) to prove the Union rule.

Final answer: Augmentation and Transitivity (Option 4).