4.1Functional dependencies and Armstrong's axioms
The idea
A functional dependency X → Y says: whenever two rows agree on X they must agree on Y. Armstrong's axioms (reflexivity, augmentation, transitivity) derive new FDs from given ones.
Think of it like this: Roll number → name: knowing the roll number fixes the name. It is a rule of the world, not just of today's data.
Why it exists
Every normalisation question starts from FDs and rules for deriving more of them.
How it works
- Reflexivity: Y ⊆ X implies X → Y (trivial FDs).
- Augmentation: X → Y gives XZ → YZ.
- Transitivity: X → Y and Y → Z give X → Z.
- Derived: union, decomposition, pseudo-transitivity.
Worked example: From A → B and BC → D derive AC → D.
Augment A → B with C: AC → BC. Then transitivity with BC → D: AC → D (pseudo-transitivity).
Now play with it
- →Step through the two proofs.
- →Find an FD that does not follow, such as B → A.
| Rule | Statement | Kind |
|---|---|---|
| Reflexivity | if Y ⊆ X then X → Y | axiom |
| Augmentation | if X → Y then XZ → YZ | axiom |
| Transitivity | if X → Y and Y → Z then X → Z | axiom |
| Union | X → Y and X → Z give X → YZ | derived |
| Decomposition | X → YZ gives X → Y and X → Z | derived |
| Pseudo-transitivity | X → Y and WY → Z give WX → Z | derived |
Not an axiom: X → Y does not give Y → X, and X → Z with Y → Z does not give XY → Z in a smaller form.
X → YgivenX → ZgivenX → XYaugment X → Y with XXY → YZaugment X → Z with YX → YZtransitivity of X → XY and XY → YZ
Check yourself
From X → Y and X → Z we can conclude
Exam notes (the dense version)
X → Y means: two rows that agree on X must agree on Y. Armstrong's axioms: reflexivity (Y ⊆ X ⇒ X → Y), augmentation (X → Y ⇒ XZ → YZ), transitivity. Derived: union (X→Y, X→Z ⇒ X→YZ), decomposition (X→YZ ⇒ X→Y), pseudo-transitivity. They are sound and complete. An FD is a property of the schema, not of one instance of the data.
Previous year questions: Functional Dependencies (6)
PYQs are grouped by topic, so this is the full set for Functional Dependencies; try the ones that match this subtopic. Open all 6 on the topic page.