Home » DBMS

Armstrong's Axioms in Functional Dependency | DBMS

In this tutorial, we will learn about Armstrong's Axiom in Function Dependency and its rules in Database Management System. By Anushree Goswami Last updated : May 31, 2023

What are Armstrong's Axioms in Functional Dependency in DBMS?

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.

Rules of Armstrong's Axioms in Functional Dependency

Armstrong's Axioms has two different set of rules,

1. Axioms or primary rules
   1. Axiom of Reflexivity
   2. Axiom of Augmentation
   3. Axiom of Transitivity
2. Additional rules or Secondary rules
   1. Union
   2. Composition
   3. Decomposition
   4. 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.

1. 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.
2. 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.
3. 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.

1. 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.
2. Composition:
   If P holds Q (P → Q) and A holds B (A → B), then PA → QB.
   proof,
   1. P → Q (Given)
   2. A → B (Given)
   3. PA → QA (Augmentation of 1 and A)
   4. PA → Q (Decomposition of 3)
   5. PA → PB (Augmentation of 2 and P)
   6. PA → B (Decomposition of 5)
   7. PA → QB (Union 4 and 6)
3. 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,
   1. P → QR (Given)
   2. QR → Q (Reflexivity)
   3. P → Q (Transitivity of 1 and 2)
4. Pseudo Transitivity:
   If P → RQ and Q → S, then P → RS.
   proof,
   1. P → RQ (Given)
   2. Q → S (Given)
   3. RQ → RS (Augmentation of 2 and R)
   4. 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.
Non-Trivial	If P holds Q (P → Q), where Q is not a subset of P, then it is called as a Non-Trivial Functional Dependency.
Completely Non-Trivial	If P holds Q (P → Q), where P intersect Y = Φ, it is called as a Completely Non-Trivial Functional Dependency.