Armstrong's axioms and derived rules

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

1. When does X → Y fail on an instance? from Lesson 4.2.1
2. What is a trivial FD? from Lesson 4.2.1
3. What does the transitive pattern "roll → dept, dept → hod" suggest? from Lesson 4.1.1

1 · The Hook

Given roll → dept and dept → hod, you "know" roll → hod. Given A → B, you also know AC → BC. Which FDs follow from a given set, and which only look as if they do? Armstrong's three axioms answer this exactly, and GATE uses them in "which FD is implied?" questions.

2 · Predict First

From A → B and B → C, which follow: (a) A → C, (b) AC → B, (c) C → A, (d) B → A?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

Predict First — the answer

(a) Yes (transitivity). (b) Yes (A → B, so A with anything still determines B). (c) and (d) no: FDs do not reverse.

Implication

F logically implies X → Y (written F ⊨ X → Y) if X → Y holds in every state that satisfies all FDs of F.

Armstrong's axioms

1. Reflexivity: if Y ⊆ X, then X → Y. (Trivial FDs.)
2. Augmentation: if X → Y, then XZ → YZ for any Z.
3. Transitivity: if X → Y and Y → Z, then X → Z.

They are sound (they derive only FDs that really follow) and complete (every FD that follows can be derived with them).

Derived rules (proved from the axioms)

Proof of union: X → Y gives X → XY (augment with X). X → Z gives XY → YZ (augment with Y). Transitivity: X → YZ.

Things that do not follow

• Splitting the left side: AB → C does not give A → C or B → C.
• Reversal: A → B does not give B → A.
• Cancellation: AB → AC does not give B → C.

The right side can always be split (decomposition); the left side cannot.

Using the axioms in practice

Deriving FDs step by step is slow. The next lesson replaces it with one algorithm, attribute closure, which answers "does F imply X → Y?" mechanically. The axioms explain why it works.

4 · Visual

Given F = { A -> B,  B -> C,  CD -> E }

A -> C        transitivity (A -> B, B -> C)
AD -> CD      augmentation of A -> C with D
AD -> E       transitivity (AD -> CD, CD -> E)
AD -> BCE     union of AD -> B, AD -> C, AD -> E

5 · Worked Examples

Example 1 Easy

From A → BC, derive A → B.

Solution

Decomposition (or: BC → B by reflexivity, then transitivity).

Example 2 Medium

Given A → B and BC → D, show AC → D.

Solution

Pseudotransitivity with X = A, Y = B, W = C. Step by step: augment A → B with C: AC → BC; transitivity with BC → D: AC → D.

Example 3 GATE

F = {AB → C, C → D}. Which are implied: (i) A → D, (ii) AB → D, (iii) ABE → CD, (iv) C → A?

Solution

(ii) by transitivity; (iii) AB → CD (union of AB → C and AB → D), then augment with E and drop E on the right by decomposition. (i) is not implied (A alone does not give C). (iv) is not implied.

8 · Connect the Dots

Lesson 4.2.1 defined FDs; this lesson gave the rules for deriving new ones. Next: a fast algorithm built on these rules, attribute closure, used for finding every candidate key.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · MCQ · 1 mark(s) — Axioms

Which is one of Armstrong's three axioms?

1. (A) Pseudotransitivity
2. (B) Augmentation
3. (C) Union
4. (D) Decomposition

Q2 · MSQ · 2 mark(s) — Implication

F = {A → B, B → C}. Which are implied by F?

1. (A) A → C
2. (B) AB → C
3. (C) C → B
4. (D) AC → BC

Q3 · MCQ · 1 mark(s) — Left side

F = {AB → C}. Which is implied?

1. (A) C → AB
2. (B) ABD → C
3. (C) B → C
4. (D) A → C

Q4 · MCQ · 2 mark(s) — Pseudotransitivity

X → Y and WY → Z imply:

1. (A) Y → Z
2. (B) W → Z
3. (C) WX → Z
4. (D) X → Z

Q5 · MCQ · 1 mark(s) — Properties

Armstrong's axioms being complete means:

1. (A) they find all candidate keys
2. (B) they produce a minimal cover
3. (C) they never derive a wrong FD
4. (D) every FD implied by F can be derived with them

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

logical implication of FDsArmstrong's axioms (reflexivity, augmentation, transitivity)soundnesscompletenessunion ruledecomposition rulepseudotransitivitycomposition