Armstrong's Axioms

Introduction to Axioms Rules

• Armstrong's Axioms is a set of rules.
• It provides a simple technique for reasoning about functional dependencies.
• It was developed by William W. Armstrong in 1974.
• It is used to infer all the functional dependencies on a relational database.

Various Axioms Rules

A. Primary Rules

Rule 1	Reflexivity     If A is a set of attributes and B is a subset of A, then A holds B. { A → B }
Rule 2	Augmentation     If A hold B and C is a set of attributes, then AC holds BC. {AC → BC}     It means that attribute in dependencies does not change the basic dependencies.
Rule 3	Transitivity     If A holds B and B holds C, then A holds C.     If {A → B} and {B → C}, then {A → C}     A holds B {A → B} means that A functionally determines B.

B. Secondary Rules

Rule 1	Union     If A holds B and A holds C, then A holds BC.     If{A → B} and {A → C}, then {A → BC}
Rule 2	Decomposition     If A holds BC and A holds B, then A holds C.     If{A → BC} and {A → B}, then {A → C}
Rule 3	Pseudo Transitivity     If A holds B and BC holds D, then AC holds D.     If{A → B} and {BC → D}, then {AC → D}

Sometimes Functional Dependency Sets are not able to reduce if the set has following properties,

1. The Right-hand side set of functional dependency holds only one attribute.
2. The Left-hand side set of functional dependency cannot be reduced, it changes the entire content of the set.
3. Reducing any functional dependency may change the content of the set.

A set of functional dependencies with the above three properties are also called as Canonical or Minimal.

Trivial Functional Dependency

Trivial	If A holds B {A → B}, where A is a subset of B, then it is called a Trivial Functional Dependency. Trivial always holds Functional Dependency.
Non-Trivial	If A holds B {A → B}, where B is not a subset A, then it is called as a Non-Trivial Functional Dependency.
Completely Non-Trivial	If A holds B {A → B}, where A intersect Y = Φ, it is called as a Completely Non-Trivial Functional Dependency.

Example:
Consider relation E = (P, Q, R, S, T, U) having set of Functional Dependencies (FD).

Calculate some members of Axioms are as follows,

Solution:

1. P → T
In the above FD set, P → Q and Q → T
So, Using Transitive Rule: If {A → B} and {B → C}, then {A → C}
∴ If P → Q and Q → T, then P → T.
P → T

2. PR → S
In the above FD set, P → Q
As, QR → S
So, Using Pseudo Transitivity Rule: If{A → B} and {BC → D}, then {AC → D}
∴ If P → Q and QR → S, then PR → S.
PR → S

3. QR → SU
In above FD set, QR → S and QR → U
So, Using Union Rule: If{A → B} and {A → C}, then {A → BC}
∴ If QR → S and QR → U, then QR → SU.
QR → SU

4. PR → SU
So, Using Pseudo Transitivity Rule: If{A → B} and {BC → D}, then {AC → D}
∴ If PR → S and PR → U, then PR → SU.
PR → SU