# Armstrong's Axioms & Closure of Attributes
## 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.
```
If Y is a subset of X, then X always determines Y.
Examples:
{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.
```
If X determines Y, then adding the same attribute Z to both sides
preserves the dependency.
Example:
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.
```
Example:
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
```
R(A, B, C, D, E)
F = { A → B, B → CD, A → E }
Compute A⁺:
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}
No more FDs apply.
A⁺ = {A, B, C, D, E} → A is a superkey (determines all attributes)
```
### Example 2
```
R(A, B, C, D)
F = { AB → C, C → D, D → A }
Compute (AB)⁺:
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
Compute C⁺:
Step 0: result = {C}
Step 1: C → D applies → result = {C, D}
Step 2: D → A applies → result = {A, C, D}
No more apply.
C⁺ = {A, C, D} → C is NOT a superkey (B not in C⁺)
```
### Example 3 — Finding Candidate Keys
```
R(A, B, C, D, E)
F = { AB → C, D → E, B → D, AB → E }
Compute (AB)⁺:
result = {A,B}
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
Can we reduce? Try A⁺:
result = {A} — No FD with just A on LHS
A⁺ = {A} ← Not a superkey alone
Try B⁺:
result = {B}
B → D → {B,D}
D → E → {B,D,E}
B⁺ = {B,D,E} ← Not a superkey (missing A,C)
Therefore AB is a CANDIDATE KEY (minimal superkey).
```
---
## 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}
F⁺ includes:
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)
... and many more (can be very large)
```
---
## Checking FD Membership
To check if a specific FD X → Y is in F⁺:
1. Compute X⁺ using F
2. 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⁺ ✓
```Back to Course