Question:medium
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?
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?
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?
Show 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.
Updated On: Jul 22, 2026
- Reflexivity, Augmentation, and Transitivity
- Reflexivity and Augmentation
- Transitivity
- Augmentation and Transitivity
Show Solution
The Correct Option is D
Solution and Explanation
Step 1: Restate the goal.
We know $X\to Y$ and $X\to Z$, and we want $X\to YZ$, built only from Armstrong's three rules.
Step 2: Write the proof as a short numbered list and mark the rule used at each line.
1. $X\to Y$ (given)
2. $XX\to XY$, that is $X\to XY$ (Augment line 1 with $X$; uses Augmentation)
3. $X\to Z$ (given)
4. $XY\to YZ$ (Augment line 3 with $Y$; uses Augmentation)
5. $X\to YZ$ (Combine lines 2 and 4 through Transitivity, since $X\to XY$ and $XY\to YZ$ chain together)
Step 3: Read off which rules got a tick mark.
Scanning the "uses" column above, Augmentation appears twice (lines 2 and 4) and Transitivity appears once (line 5). Reflexivity never appears, because we never had to fall back on a subset argument like $Y\subseteq X$ to manufacture a dependency out of nothing; every dependency we used was either given or built by augmenting a known one.
Step 4: Confirm sufficiency.
Since the five line proof above is complete and correct using only Augmentation and Transitivity, these two rules together are sufficient.
Step 5: Confirm necessity.
Drop Augmentation and there is no way to get from $X\to Y$ to $X\to XY$; drop Transitivity and there is no way to merge $X\to XY$ with $XY\to YZ$. So both are also necessary, and Reflexivity is extra baggage that the proof never touches.
\[ \boxed{\text{Augmentation and Transitivity}} \]
We know $X\to Y$ and $X\to Z$, and we want $X\to YZ$, built only from Armstrong's three rules.
Step 2: Write the proof as a short numbered list and mark the rule used at each line.
1. $X\to Y$ (given)
2. $XX\to XY$, that is $X\to XY$ (Augment line 1 with $X$; uses Augmentation)
3. $X\to Z$ (given)
4. $XY\to YZ$ (Augment line 3 with $Y$; uses Augmentation)
5. $X\to YZ$ (Combine lines 2 and 4 through Transitivity, since $X\to XY$ and $XY\to YZ$ chain together)
Step 3: Read off which rules got a tick mark.
Scanning the "uses" column above, Augmentation appears twice (lines 2 and 4) and Transitivity appears once (line 5). Reflexivity never appears, because we never had to fall back on a subset argument like $Y\subseteq X$ to manufacture a dependency out of nothing; every dependency we used was either given or built by augmenting a known one.
Step 4: Confirm sufficiency.
Since the five line proof above is complete and correct using only Augmentation and Transitivity, these two rules together are sufficient.
Step 5: Confirm necessity.
Drop Augmentation and there is no way to get from $X\to Y$ to $X\to XY$; drop Transitivity and there is no way to merge $X\to XY$ with $XY\to YZ$. So both are also necessary, and Reflexivity is extra baggage that the proof never touches.
\[ \boxed{\text{Augmentation and Transitivity}} \]
Was this answer helpful?
0
Top Questions on Functional Dependencies and Armstrong's Axioms
Questions Asked in GATE CS exam
A database has 25,000 fixed-length records of 100 bytes (primary key 15 bytes). The data file is block-aligned so each record is fully contained within a block. The file is indexed by a primary index file, also block-aligned and ordered. Block size is 1024 bytes and a block pointer is 5 bytes. Each index entry stores the block’s anchor key (15 bytes) and a pointer (5 bytes). Binary search on an index file of \(b\) blocks needs \(\lceil \log_2 b \rceil\) block accesses in the worst case. Given a key, the number of block accesses required to identify the data file block that may contain the record, in the worst case, is ____________.
- GATE CS - 2023
- Database Management Systems