Armstrong's Axioms

Armstrong’s Axioms
The term Armstrong axioms refer to the sound and complete set of inference
rules or axioms, introduced by William W. Armstrong, that is used to test the
logical implication of functional dependencies. If F is a set of functional
dependencies then the closure of F, denoted as , is the set of all functional
dependencies logically implied by F. Armstrong’s Axioms are a set of rules, that
when applied repeatedly, generates a closure of functional dependencies.
Seco
ndary Rules –
These rules can be derived from the above axioms.

Why armstrong axioms refer to the Sound and Complete ?
By sound, we mean that given a set of functional dependencies F specified on a
relation schema R, any dependency that we can infer from F by using the
primary rules of Armstrong axioms holds in every relation state r of R that
satisfies the dependencies in F.
By complete, we mean that using primary rules of Armstrong axioms repeatedly
to infer dependencies until no more dependencies can be inferred results in the
complete set of all possible dependencies that can be inferred from F.
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- If A holds B {A → B}, where A intersect Y = Φ, it is called as a Completely

Trivial Non-Trivial Functional Dependency.
Example:
Consider relation E = (P, Q, R, S, T, U) having set of Functional Dependencies
(FD).
P → Q P → R
QR → S Q → T
QR → U PR → U
Calculate some members of Axioms are as follows,
1. P → T
2. PR → S
3. QR → SU
4. PR → SU
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

Armstrong's Axioms

Uploaded by

Copyright:

Available Formats

Armstrong's Axioms

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Armstrong's Axioms

Uploaded by

Copyright:

Available Formats

Armstrong’s Axioms

These rules can be derived from the above axioms.

Introduction to Axioms Rules

 Armstrong's Axioms is a set of rules.

Various Axioms Rules

Rule 3 Pseudo Transitivity

Trivial Functional Dependency

Trivial If A holds B {A → B}, where A is a subset of B, then it is called a Trivial

Non-Trivial If A holds B {A → B}, where B is not a subset A, then it is called as a Non-

Completely Non- If A holds B {A → B}, where A intersect Y = Φ, it is called as a Completely

Calculate some members of Axioms are as follows,

You might also like