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 \(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 \subseteq X\), then \(X \to Y\)
Augmentation: If \(X \to Y\), then \(XZ \to YZ\) for any Z
Transitivity: If \(X \to Y\) and \(Y \to Z\), then \(X \to Z\)

The additional rule of Union is defined as follows.
Union: If \(X \to Y\) and \(X \to Z\), then \(X \to 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?

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

Hint:

Augment each given dependency separately to build two intermediate dependencies that share a common attribute set, then chain them with Transitivity; Reflexivity is never actually invoked.

Answer 1

The Correct Option is D

Step 1: Understanding the Question.
We must prove the Union rule, "if \(X \to Y\) and \(X \to Z\) then \(X \to YZ\)", using only Armstrong's three basic axioms (Reflexivity, Augmentation, Transitivity), and find out exactly which of these three axioms actually get used in a correct, minimal proof.

Step 2: Start from the first given dependency and augment it.
We are given \(X \to Y\). Apply Augmentation by adding \(X\) to both sides:
\[ X \to Y \implies XX \to XY \]
Since a union of a set with itself is just itself, \(XX = X\), so this step gives
\[ X \to XY \]
This step used the Augmentation axiom.

Step 3: Augment the second given dependency.
We are also given \(X \to Z\). Apply Augmentation by adding \(Y\) to both sides:
\[ X \to Z \implies XY \to YZ \]
This step also used Augmentation.

Step 4: Chain the two results with Transitivity.
From Step 2 we have \(X \to XY\), and from Step 3 we have \(XY \to YZ\). Applying Transitivity to these two dependencies:
\[ X \to XY \text{ and } XY \to YZ \implies X \to YZ \]
This is exactly the Union rule we set out to prove, and this step used Transitivity.

Step 5: Check whether Reflexivity was needed anywhere.
Reflexivity states that if \(Y \subseteq X\) then \(X \to Y\); it is used to generate trivial dependencies straight from a subset relationship. Nowhere in the derivation above did we need a subset relationship to produce a new dependency out of nothing, we only ever transformed dependencies we were already given, using Augmentation and Transitivity. So Reflexivity plays no role in this particular proof.

Step 6: Analyze the options.

(A) Reflexivity, Augmentation, and Transitivity: Includes Reflexivity, which is not actually needed, so this set is more than what is necessary. Incorrect.

(B) Reflexivity and Augmentation: Missing Transitivity, which is essential to combine the two augmented dependencies into the final result; this pair alone cannot complete the proof. Incorrect.

(C) Transitivity: Alone, Transitivity cannot produce the two intermediate dependencies \(X \to XY\) and \(XY \to YZ\) in the first place, since those come from Augmentation. Incorrect.

(D) Augmentation and Transitivity: As shown in Steps 2 to 4, these two axioms alone are enough to derive the Union rule, and both are genuinely used. Correct.

Step 7: Final conclusion.
The combination that is both necessary and sufficient for the proof is
\[ \boxed{\text{Augmentation and Transitivity}} \]