Home »
DBMS
Armstrong's Axioms in Functional Dependency  DBMS
In this tutorial, we are going to learn about Armstrong's Axiom in Function Dependency in Database Management System.
Submitted by Anushree Goswami, on August 13, 2019
Armstrong axioms are a complete set of inference rules or axioms, introduced and developed by William W. Armstrong in 1974. The inference rules are sound which is used to test logical inferences of functional dependencies. The axiom which also refers to as sound is used to infer all the functional dependencies on a relational database. The Axioms are a set of rules, that when applied to a specific set, generates a closure of functional dependencies.
Armstrong's Axioms has two different set of rules,

Axioms or primary rules
 Axiom of Reflexivity
 Axiom of Augmentation
 Axiom of Transitivity

Additional rules or Secondary rules
 Union
 Composition
 Decomposition
 Pseudo Transitivity
1) Axioms or primary rules
Let suppose T (k) with the set of attributes k be a relation scheme. Subsequently, we will represent subsets of k as A, B, C. The standard notation in database theory for the set of attributes is AB rather than A∪B.
 Axiom of Reflexivity:
If a set of attributes is P and its subset is Q, then P holds Q. If Q ⊆ P, then P → Q. This property is called as Trivial functional dependency. Where P holds Q (P → Q) denote P functionally decides Q.
 Axiom of Augmentation:
If P holds Q (P → Q) and R is a set of attributes, then PR holds QR (PR → QR). It means that a change in attributes in dependencies does not create a change in basic dependencies. If P → Q, then PR → QR for any R.
 Axiom of Transitivity:
If P holds Q (P → Q) and Q holds R (Q → R), then P hold R (P → R). Where P holds R (P → R) denote P functionally decides R, same with P holds Q and Q holds R.
2) Additional rules or secondary rules
These rules can be derived from the above axioms.
 Union:
If P holds Q (P → Q) and P holds R (P → R), then P → QR. If X → Y and X → Z, then X → YZ.

Composition:
If P holds Q (P → Q) and A holds B (A → B), then PA → QB.
proof,
 P → Q (Given)
 A → B (Given)
 PA → QA (Augmentation of 1 and A)
 PA → Q (Decomposition of 3)
 PA → PB (Augmentation of 2 and P)
 PA → B (Decomposition of 5)
 PA → QB (Union 4 and 6)

Decomposition:
This rule is contrary of union rule. If P → QR, then P holds Q (P → Q) and P holds R (P → R). If X → YZ, then X → Y and X → Z.
proof,
 P → QR (Given)
 QR → Q (Reflexivity)
 P → Q (Transitivity of 1 and 2)

Pseudo Transitivity:
If P → RQ and Q → S, then P → RS.
proof,
 P → RQ (Given)
 Q → S (Given)
 RQ → RS (Augmentation of 2 and R)
 P → RS (Transitivity of 1 and 3)
Trivial Functional Dependency
Trivial 
If P holds Q (P → Q), where P is a subset of Q, then it is called a Trivial Functional Dependency. Trivial always holds Functional Dependency. 
NonTrivial 
If P holds Q (P → Q), where Q is not a subset of P, then it is called as a NonTrivial Functional Dependency. 
Completely NonTrivial 
If P holds Q (P → Q), where P intersect Y = Φ, it is called as a Completely NonTrivial Functional Dependency. 
TOP Interview Coding Problems/Challenges