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

Let us look at this problem from the angle of what each axiom actually contributes to building the Union rule from \(X \to Y\) and \(X \to Z\), rather than mechanically applying rules.

Step 1: Understand what Reflexivity does.

Reflexivity generates dependencies of the trivial form \(X \to Y\) where \(Y\) is a subset of \(X\) -- it does not combine or extend existing dependencies. Since we already start with two non-trivial dependencies \(X \to Y\) and \(X \to Z\), Reflexivity has no role to play in merging them into \(X \to YZ\).

Step 2: Understand what Augmentation contributes.

Augmentation lets us pad both sides of an existing dependency with extra attributes without changing its validity. Using it on \(X \to Y\) by padding with \(X\) gives \(X \to XY\). Using it on \(X \to Z\) by padding with \(Y\) gives \(XY \to YZ\). So Augmentation is the tool that reshapes the two original dependencies into a form where their left-hand and right-hand sides overlap on \(XY\).

Step 3: Understand what Transitivity contributes.

Once we have \(X \to XY\) and \(XY \to YZ\) (both obtained purely through Augmentation), Transitivity is exactly the rule that lets us chain them: since the right side of the first matches the left side of the second, we conclude \(X \to YZ\).

Step 4: Put it together.

\(X \to Y\) ==(Augment with X)==> \(X \to XY\)

\(X \to Z\) ==(Augment with Y)==> \(XY \to YZ\)

\(X \to XY\) and \(XY \to YZ\) ==(Transitivity)==> \(X \to YZ\)

Every step used either Augmentation or Transitivity, and dropping either one breaks the chain -- without Augmentation we cannot create the overlapping form \(X \to XY\) and \(XY \to YZ\), and without Transitivity we cannot merge them. Reflexivity is never invoked at any point.

So the necessary and sufficient combination is Augmentation and Transitivity, which corresponds to Option 4.