Definition
A relation is in 3NF if:
-
It's in 2NF
-
No non-prime attribute is transitively dependent on the primary key
Transitive Dependency
A dependency chain: A → B → C (where A is key, B and C are non-prime)
3NF Decomposition Algorithm
Input: Relation R, Functional Dependencies F Output: Lossless, dependency-preserving 3NF decomposition
Steps:
-
Find Minimal Cover (Fc): Simplify FD set
-
Identify Candidate Keys: Find all possible keys
-
Group FDs: Group by same left-hand side
-
Create Relations: One relation per group
-
Ensure Lossless: Add relation with candidate key if needed
-
Remove Redundancy: Eliminate subset relations
Detailed Example
Given:
-
Relation: R(A, B, C, D)
-
FDs: {A → B, A → C, B → C, C → D}
Step 1: Find Minimal Cover
-
A → C is redundant (A → B, B → C ⟹ A → C)
-
Fc = {A → B, B → C, C → D}
Step 2: Find Candidate Keys
- A⁺ = {A, B, C, D} → A is candidate key
Step 3-4: Create Relations
-
From A → B: R₁(A, B)
-
From B → C: R₂(B, C)
-
From C → D: R₃(C, D)
Step 5: Check Lossless
- A (candidate key) appears in R₁ ✓
Final 3NF Decomposition:
- R₁(A, B), R₂(B, C), R₃(C, D)
Properties Achieved
-
✅ 3NF: Each relation has FD where LHS is key
-
✅ Dependency Preserving: All original FDs represented
-
✅ Lossless Join: R₁ ⋈ R₂ ⋈ R₃ = Original R