Given a relational schema R and a set of functional dependencies F. A functional dependency X→Y (Not in F) on R is said to be logically implied by the set of functional dependencies F on R if for relation R on the relational schema that satisfies F also satisfies X→Y.
Example. Consider the relation schema R= (A, B, C, D) and the set of FD’s F = {A→B, B→C, C→D}.
Then the FD’s A→C, B→D and A→D are logically implied.
1. Armstrong’s Axioms
The following three rules called inference axioms or Armstrong’s Axioms can be used to find all the FDs logically implied by a set of FDs. Let X, Y, Z, and W be subsets of attributes of a relation R. The following axioms hold:
- Reflexivity. If Y is a subset of X, then X → Y. This also implies that X → X always holds. Functional dependencies of this type are called trivial functional dependencies.
- Augmentation. If X → Y holds and Z is a set of attributes, then ZX → ZY.
- Transitivity. If X → Y holds and Y → Z holds, then X → Z holds.
These rules are Sound and Complete. They are sound because they do not generate any invalid functional dependencies. They are complete because they allow us to generate F+(closure of F) from the given set of functional dependencies F. It is very cumbersome and complex to use the Armstrong’s Axioms directly for the computation of F+. So some more axioms are added to simplify the process of computation of F+. These additional axioms can be proved correct by using the Armstrong’s Axioms. The additional axioms are
- Additivity or Union. If X → Y and X → Z, then X → YZ holds.
- Projectivity or Decomposition. If X → YZ holds, then X → Y and X → Z also holds
- Pseudotransitivity. If X → Y and ZY → W holds, then XZ → W holds.
These additional axioms are also Sound and Complete.
Example. Let R = (A, B, C, D) and F be the set of functional dependencies for R given by {A→B, A→C, BC→D}. Prove A→D.
Sol. Given set of functional dependencies for a relation R is {A→B, A→C, BC→D}
By using Armstrong Axioms, named projectivity, we can show that
A→BC (as A→B, A→C)
Since BC→D, so by transitivity rule,
A→BC and BC→D means A→D. Hence proved.
Example. Consider a relation R2(A, B, C, D, E, F) and a set of functional dependencies FD={AB→C, C→FA, F→E} that hold on R2.
- Using Armstrong’s axioms show that the functional dependency AB→E also holds on
- Does AB→F hold for FD1 = {AB→CD, C→E, DE→F}?
Sol.
- AB→C (given).
Apply decomposition to C→FA, get C→F. F→E (given).
Apply transitivity to AB→C, C→F, F→E, get AB→E. Hence proved.
- We can prove it as follows: AB→CD (given).
C→E (given). Apply augmentation to C→E, get, CD→DE.
DE→F (given).
Apply transitivity to AB→CD, CD→DE and DE→F, get AB→F.
Example. Let F ={AB → C, B → D, CD→E, CE→GH}.. Give a derivation sequence on FD, {AB→G} using only Armstrong’s axioms.
Sol. We have to derive AB → G
AB → ABE (augmentation: AB → E with AB)
ABE → CE (augmentation: AB → C with E)
AB → CE (transitivity: AB → ABE and ABE → CE)
AB → GH (transitivity: AB → CE and CE → GH)
GH → G (reflexivity)
AB → G (transitivity: AB → GH and GH → G)
Source: Gupta Satinder Bal, Mittal Aditya (2017), Introduction to Basic Database Management System, 2nd Edition-University Science Press (2017)