Armstrong's Axioms & Closure of Attributes

Armstrong's Axioms are a set of inference rules used to derive all functional dependencies FDs from a given set F. They were proposed by William W. Armstrong in 1974.

Armstrong's Axioms

Armstrong's Axioms are a set of inference rules used to derive all functional dependencies (FDs) from a given set F. They were proposed by William W. Armstrong in 1974.

These axioms are sound (they only derive valid FDs) and complete (they can derive ALL FDs in F+).

Three Primary (Basic) Axioms

1. Reflexivity (Trivial Rule)

If Y ⊆ X, then X → Y.

{A, B}	A (A ⊆ {A, B})
{A, B}	B (B ⊆ {A, B})
{A, B}	{A, B} ({A,B} ⊆ {A,B})

2. Augmentation (Adding Attributes)

If X → Y, then XZ → YZ for any attribute set Z.

A	B (given)
Therefore: AC	BC (augment both sides with C)
Also: ACD	BCD (augment with CD)

3. Transitivity (Chain Rule)

If X → Y and Y → Z, then X → Z.

EmpID	DeptID (given)
DeptID	DeptName (given)
Therefore: EmpID	DeptName (transitivity)

Three Derived Rules (from the primary axioms)

4. Union

If X → Y and X → Z, then X → YZ.

A → B and A → C ⟹ A → BC

5. Decomposition

If X → YZ, then X → Y and X → Z.

A → BC ⟹ A → B and A → C

6. Pseudo-transitivity

If X → Y and WY → Z, then WX → Z.

A → B and CB → D ⟹ CA → D

Closure of a Set of Attributes (X⁺)

The closure of attribute set X under functional dependency set F, written X⁺, is the set of all attributes that are functionally determined by X.

Algorithm to Compute X⁺

Algorithm: Closure(X, F)

1. result = X (start with X itself)

2. Repeat until no change:

For each FD (A → B) in F:

If A ⊆ result:

result = result ∪ B

3. Return result = X⁺

Worked Examples

Example 1

F = { A	B, B → CD, A → E }
Step 0	result = {A}
Step 1: A	B applies (A ⊆ {A}) → result = {A, B}
Step 2: B	CD applies (B ⊆ {A,B}) → result = {A, B, C, D}
Step 3: A	E applies (A ⊆ {A,B,C,D}) → result = {A, B, C, D, E}
A⁺ = {A, B, C, D, E}	A is a superkey (determines all attributes)

Example 2

F = { AB	C, C → D, D → A }
Step 0	result = {A, B}
Step 1: AB	C applies → result = {A, B, C}
Step 2: C	D applies → result = {A, B, C, D}
Step 3: D	A applies → (A already in result)
(AB)⁺ = {A, B, C, D}	AB is a superkey
Step 0	result = {C}
Step 1: C	D applies → result = {C, D}
Step 2: D	A applies → result = {A, C, D}
C⁺ = {A, C, D}	C is NOT a superkey (B not in C⁺)

Example 3 — Finding Candidate Keys

F = { AB	C, D → E, B → D, AB → E }
AB	C → {A,B,C}
B	D → {A,B,C,D}
D	E → {A,B,C,D,E}
(AB)⁺ = {A,B,C,D,E}	AB is a superkey
B	D → {B,D}
D	E → {B,D,E}

Closure of a Set of FDs (F⁺)

The closure F⁺ is the set of ALL FDs that can be derived from F using Armstrong's Axioms. It includes both trivial and non-trivial dependencies.

F = {A	B, B → C}
A	B (given)
B	C (given)
A	C (transitivity)
A	A (reflexivity)
A	BC (union + above)
AB	B (reflexivity)
AB	C (from A→C + augmentation)

Checking FD Membership

To check if a specific FD X → Y is in F⁺:

Compute X⁺ using F
If Y ⊆ X⁺ then X → Y ∈ F⁺

F = {A	B, B → C}
Is A	C in F⁺?
Compute A⁺: {A}	{A,B} → {A,B,C}
Is C ∈ A⁺? YES	A → C ∈ F⁺ ✓