Apply Armstrong's Axioms — reflexivity, augmentation, and transitivity — to derive additional valid functional dependencies from a given FD set

Targeted Learning Outcomes

• These example problems give practice toward the following outcome:
• **MO3 [Apply]:** By the end of this module, students will be able to apply Armstrong's Axioms — reflexivity, augmentation, and transitivity — to derive additional valid functional dependencies from a given FD set.
• Armstrong's Axioms are the three foundational inference rules for functional dependencies (FDs) in relational database theory:
• **Reflexivity:** If Y ⊆ X, then X → Y (a set of attributes always determines any of its subsets).
• **Augmentation:** If X → Y, then XZ → YZ for any attribute set Z (adding the same attributes to both sides preserves the FD).
• **Transitivity:** If X → Y and Y → Z, then X → Z (FDs can be chained together).
• Working through these problems will help you apply each axiom mechanically and in combination to derive new valid FDs from a given set.

Problem 1: Applying Reflexivity

Problem: Consider the relation R with attributes {A, B, C}. Using Armstrong's Axiom of Reflexivity, derive at least three valid functional dependencies. Justify each derivation.

Solution:

• Step 1 — Recall the Reflexivity Axiom: If Y ⊆ X, then X → Y. This means any set of attributes functionally determines itself or any of its subsets — no base FDs are needed; this holds universally.
• Step 2 — Choose X = {A, B, C}. Since {A} ⊆ {A, B, C}, by reflexivity: AB C → A is valid.
• Step 3 — Since {B, C} ⊆ {A, B, C}, by reflexivity: ABC → BC is valid.
• Step 4 — Choose X = {A, B}. Since {A} ⊆ {A, B}, by reflexivity: AB → A is valid.
• Step 5 — Choose X = {B, C}. Since {C} ⊆ {B, C}, by reflexivity: BC → C is valid.
• Step 6 — Summary of derived FDs: (1) ABC → A, (2) ABC → BC, (3) AB → A, (4) BC → C. All are valid by reflexivity alone because in each case the right-hand side is a subset of the left-hand side.
• [Practises MO3: direct application of the Reflexivity axiom.]

Problem 2: Applying Augmentation

Problem: Given the relation R with attributes {A, B, C, D} and the functional dependency A → B, use Armstrong's Axiom of Augmentation to derive three new functional dependencies. Show each step clearly.

Solution:

• Step 1 — Recall the Augmentation Axiom: If X → Y, then XZ → YZ for any attribute set Z. We start with the given FD: A → B.
• Step 2 — Augment both sides with C (i.e., let Z = {C}): Since A → B, it follows that AC → BC.
• Step 3 — Augment both sides with D (i.e., let Z = {D}): Since A → B, it follows that AD → BD.
• Step 4 — Augment both sides with CD (i.e., let Z = {C, D}): Since A → B, it follows that ACD → BCD.
• Step 5 — Verify the logic for one example: AC → BC means "if we know A and C together, we can determine B (from A → B) and we already know C, so we can determine BC." This confirms the augmentation is valid.
• Step 6 — Summary of derived FDs: (1) AC → BC, (2) AD → BD, (3) ACD → BCD. All were derived by augmenting A → B with different attribute sets.
• [Practises MO3: direct application of the Augmentation axiom.]

Problem 3: Applying Transitivity

Problem: Given the relation R with attributes {A, B, C, D} and the functional dependencies A → B and B → C, use Armstrong's Axiom of Transitivity to derive a new functional dependency. Then use that result together with B → C and C → D to derive another FD.

Solution:

• Step 1 — Recall the Transitivity Axiom: If X → Y and Y → Z, then X → Z. We can chain FDs together.
• Step 2 — Identify the first pair of FDs: A → B and B → C. The right-hand side of the first FD (B) matches the left-hand side of the second FD (B).
• Step 3 — Apply transitivity to A → B and B → C: Since A → B and B → C, by transitivity we derive A → C.
• Step 4 — Now use the newly derived FD A → C together with C → D. The right-hand side of A → C (which is C) matches the left-hand side of C → D.
• Step 5 — Apply transitivity to A → C and C → D: Since A → C and C → D, by transitivity we derive A → D.
• Step 6 — Summary: Starting from A → B, B → C, and C → D, we derived (1) A → C and (2) A → D by applying transitivity in sequence. This demonstrates how transitivity lets us "follow the chain" of dependencies.
• [Practises MO3: direct application of the Transitivity axiom.]

Problem 4: Combining Augmentation and Transitivity

Problem: Given the relation R with attributes {Employee, Department, Manager, Budget} and the following FDs:

• FD1: Employee → Department
• FD2: Department → Manager
• Use augmentation and transitivity together to derive: (a) EmployeeBudget → DepartmentBudget, and (b) Employee → Manager.

Solution:

• Step 1 — We are given FD1: Employee → Department and FD2: Department → Manager. We need to derive two new FDs using the axioms.
• Step 2 — Derive part (a): EmployeeBudget → DepartmentBudget. Start with FD1: Employee → Department.
• Step 3 — Apply Augmentation to FD1 with Z = {Budget}: Since Employee → Department, augmenting both sides with Budget gives EmployeeBudget → DepartmentBudget. Part (a) is derived. ✓
• Step 4 — Derive part (b): Employee → Manager. We need to chain FD1 and FD2.
• Step 5 — Apply Transitivity using FD1 and FD2: FD1 states Employee → Department; FD2 states Department → Manager. The right-hand side of FD1 (Department) matches the left-hand side of FD2 (Department).
• Step 6 — By transitivity: Employee → Department and Department → Manager, therefore Employee → Manager. Part (b) is derived. ✓
• Step 7 — Interpretation: An employee determines their department (FD1), and a department determines its manager (FD2); therefore an employee indirectly determines their manager — a meaningful real-world conclusion confirmed by transitivity.
• [Practises MO3: combined application of Augmentation and Transitivity.]

Problem 5: Multi-Step Derivation Chain

Problem: Given the relation R with attributes {A, B, C, D, E} and the following FD set:

• FD1: A → B
• FD2: BC → D
• FD3: D → E
• Derive the functional dependency AC → E using only Armstrong's Axioms. Clearly name the axiom used at each step.

Solution:

• Step 1 — Goal: Derive AC → E from {A → B, BC → D, D → E} using Armstrong's Axioms only.
• Step 2 — Start with FD1: A → B. We want to involve C so that we can eventually use FD2 (which requires BC).
• Step 3 — Apply Augmentation to FD1 with Z = {C}: Since A → B, augmenting both sides with C gives AC → BC. (Augmentation Axiom)
• Step 4 — We now have AC → BC (just derived) and FD2: BC → D. The right-hand side of the derived FD (BC) matches the left-hand side of FD2 (BC).
• Step 5 — Apply Transitivity to AC → BC and BC → D: By transitivity, AC → D. (Transitivity Axiom)
• Step 6 — We now have AC → D (just derived) and FD3: D → E. The right-hand side of the derived FD (D) matches the left-hand side of FD3 (D).
• Step 7 — Apply Transitivity to AC → D and D → E: By transitivity, AC → E. (Transitivity Axiom)
• Step 8 — Derivation complete. Summary of the chain:
• A → B [given FD1]
• AC → BC [Augmentation of FD1 with C]
• AC → D [Transitivity: AC → BC and BC → D]
• AC → E [Transitivity: AC → D and D → E]
• Step 9 — AC → E is now proven valid using only Armstrong's Axioms, without needing to know actual data values in the relation.
• [Practises MO3: multi-step application combining Augmentation and Transitivity to derive a non-obvious FD.]