Database Management SystemsThird Normal Form (3NF)

Third Normal Form (3NF)

LevelIntermediate

Duration75 mins

TopicThird Normal Form (3NF)

4 / 5

3NF Synthesis Algorithm

Systematic Decomposition to Third Normal Form

Identifying 3NF violations is only half the battle—we need a systematic way to fix them. The 3NF Synthesis Algorithm (also known as the Bernstein Algorithm or the 3NF Decomposition Algorithm) provides a guaranteed method for decomposing any relation schema into Third Normal Form.

Unlike ad-hoc decomposition approaches, this algorithm provides dual guarantees: the resulting decomposition is both lossless (no information is lost when joining the decomposed relations) and dependency-preserving (all original functional dependencies can be verified within individual relations). These guarantees make the algorithm the gold standard for 3NF decomposition.

What You Will Learn

By the end of this page, you will master the complete 3NF synthesis algorithm, understand why each step is necessary, and be able to apply it to any relation with any set of functional dependencies. You'll also understand the theoretical guarantees that make this algorithm reliable.

Algorithm Overview and Guarantees

Before diving into the mechanics, let's understand what the 3NF synthesis algorithm accomplishes and why it works.

Algorithm Guarantees:

Given any relation R with functional dependencies F, the 3NF synthesis algorithm produces a decomposition {R₁, R₂, ..., Rₖ} such that:

Each Rᵢ is in Third Normal Form

The decomposition is lossless-join (R = R₁ ⋈ R₂ ⋈ ... ⋈ Rₖ)

The decomposition is dependency-preserving (F ⊆ (F₁ ∪ F₂ ∪ ... ∪ Fₖ)⁺)

No other decomposition method for 3NF provides all three guarantees simultaneously. BCNF decomposition, by contrast, cannot always preserve dependencies.

3NF Synthesis Algorithm Properties
Property	Guarantee	Why It Matters
3NF Achieved	Every resulting relation satisfies 3NF	Eliminates transitive dependencies on non-prime attributes
Lossless Join	Join of all Rᵢ reproduces original R exactly	No spurious tuples introduced; no data lost
Dependency Preservation	All FDs in F can be enforced locally	Constraints can be checked without joining relations
Polynomial Time	Algorithm runs in O(n²) time	Practical for real-world schemas

High-Level Algorithm Structure:

Compute Canonical Cover — Minimize the set of FDs to remove redundancy
Create Relations from FDs — Each FD becomes a relation schema
Ensure Key Presence — Add a relation for a candidate key if needed
Remove Subsumed Relations — Eliminate redundant relations

Each step serves a specific purpose in achieving the guarantees. Let's examine each in detail.

Historical Note

Philip Bernstein developed this algorithm in 1976, proving that 3NF decomposition with both lossless join and dependency preservation is always achievable. This was a fundamental result in database theory, establishing 3NF as a practically optimal normal form.

Step 1: Computing the Canonical Cover

The first step is to compute the canonical cover (also called minimal cover) of the functional dependencies. This eliminates redundancy in the FD set before decomposition.

Why This Matters:

Redundant FDs create redundant relations in the final decomposition
Extraneous attributes on the left side of FDs create unnecessarily wide relations
Canonicalizing first ensures a minimal, clean decomposition

Canonical Cover Algorithm:

canonical_cover_algorithm.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
ALGORITHM: Compute Canonical Cover Fc of F
 
INPUT: Set of functional dependencies F
OUTPUT: Canonical cover Fc
 
1. Set Fc = F
 
2. REPEAT until no changes:
   
   2a. Combine FDs with same left side:
       Replace {X → A, X → B} with {X → AB}
   
   2b. Remove extraneous left-side attributes:
       For each FD (X → A) in Fc:
         For each attribute B in X:
           If A ∈ (Fc with X→A replaced by (X-B)→A)⁺:
             Replace X → A with (X - B) → A
   
   2c. Remove redundant FDs:
       For each FD (X → A) in Fc:
         If A ∈ (X)⁺ under (Fc - {X → A}):
           Remove X → A from Fc
 
3. RETURN Fc

Computing Canonical Cover ExampleF = {A → BC, B → C, A → B, AB → C}

Input

Output

Order Can Affect Final Form

The canonical cover is not necessarily unique—different orderings of attribute removal can yield different but equivalent canonical covers. Any canonical cover works for 3NF synthesis; the result will be equivalent decompositions.

Step 2: Creating Relations from Functional Dependencies

Once we have the canonical cover Fc, we create a relation for each FD. This is the heart of the synthesis algorithm.

The Core Insight:

If X → A is a functional dependency, then we should have a relation with attributes X ∪ {A} where X is the key.

This directly ensures that A depends on the key (X) and nothing but the key within that relation.

Relation Creation Rule:

create_relations.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
ALGORITHM: Create Relations from Canonical Cover
 
INPUT: Canonical cover Fc
OUTPUT: Set of relation schemas D
 
1. Initialize D = ∅
 
2. FOR each FD (X → Y) in Fc:
   Create relation schema Ri = X ∪ Y
   Designate X as the primary key of Ri
   Add Ri to D
 
3. RETURN D

Creating Relations from FDsCanonical cover Fc = {A → BC, B → C, D → E}

Input

Output

Why This Guarantees Dependency Preservation:

Each FD X → Y becomes the key-to-nonkey relationship in its own relation. The FD can be verified by checking just that relation:

To verify A → BC, check relation R1(A, B, C): For any value of A, B and C are uniquely determined
To verify B → C, check relation R2(B, C): For any value of B, C is uniquely determined

No joins required—each constraint is local to its dedicated relation.

Combining FDs with Same Left Side

If the canonical cover has multiple FDs with the same left side (e.g., A → B and A → C), they should be combined into a single relation (A, B, C with key A) rather than creating separate relations. This is typically handled in the canonical cover step by combining right sides.

Step 3: Ensuring Candidate Key Presence

The relations created from FDs might not include a candidate key of the original relation R. Without a candidate key relation, the decomposition might not be lossless. Step 3 ensures lossless join by adding a key relation if needed.

Why This Is Necessary:

Lossless join requires that we can reconstruct R from R₁ ⋈ R₂ ⋈ ... ⋈ Rₖ without spurious tuples. A sufficient condition (Chase test result) is that at least one Rᵢ contains a candidate key of R.

Key Presence Check:

ensure_key.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
ALGORITHM: Ensure Candidate Key Presence
 
INPUT: Set of relation schemas D, Original relation R, FD set F
OUTPUT: Updated D with key guarantee
 
1. Find a candidate key K of R (using F)
 
2. Check if any Ri in D contains K:
   FOR each Ri in D:
     If K ⊆ attributes(Ri):
       RETURN D  // Key already present, done
 
3. If no Ri contains K:
   Create new relation Rk = K
   Designate K as the primary key of Rk
   Add Rk to D
 
4. RETURN D

Adding Key Relation ExampleR(A, B, C, D) with Fc = {A → B, C → D}, Key = {A, C}

Input

Output

When Is the Key Relation Needed?

The key relation is typically needed when:

The original relation has a composite key
No single FD has the complete key on its left side
The key attributes are distributed across multiple FDs

When Is It Already Present?

If some FD has X → Y where X is a superkey of R, that relation already contains the key
Common in simple schemas where the primary key determines everything directly

Any Candidate Key Works

If R has multiple candidate keys, you only need to include ONE of them. Choose whichever is most natural for the application or simplest to represent. The lossless join property will be satisfied regardless of which candidate key is used.

Step 4: Removing Subsumed (Redundant) Relations

The final step removes redundant relations—those whose attributes are entirely contained within another relation in the decomposition.

Why Remove Subsumed Relations?

If R₁ ⊆ R₂ (all attributes of R₁ are in R₂), then R₁ is redundant
Keeping R₁ wastes storage and creates maintenance overhead
The FDs preserved in R₁ are also preserved in R₂

Subsumption Removal:

remove_subsumed.txt
1
2
3
4
5
6
7
8
9
10
11
12
ALGORITHM: Remove Subsumed Relations
 
INPUT: Set of relation schemas D
OUTPUT: Minimal set of relation schemas D'
 
1. Initialize D' = D
 
2. FOR each pair (Ri, Rj) in D' where i ≠ j:
   IF attributes(Ri) ⊆ attributes(Rj):
     Remove Ri from D'
 
3. RETURN D'

Removing Subsumed Relations ExampleFrom running example

Input

Output

Critical Insight: Why FDs Are Still Preserved

When R₂(B, C) is subsumed by R₁(A, B, C), the FD B → C is not lost:

B → C can still be verified in R₁
Every tuple in R₁ establishes the B → C relationship
The constraint enforcement mechanism simply checks R₁ instead of R₂

Subsumption vs. Overlap:

Be careful to distinguish:

Subsumption: R₁ ⊆ R₂ means ALL attributes of R₁ are in R₂ (remove R₁)
Overlap: Some attributes shared, but neither contains the other (keep both)

Don't Remove Too Aggressively

Only remove relations that are completely subsumed. If Rᵢ has even one attribute not in Rⱼ, keep both relations. Premature removal can lose attributes or dependencies.

The Complete 3NF Synthesis Algorithm

Now let's put all the steps together into the complete algorithm:

3NF SYNTHESIS ALGORITHM (BERNSTEIN ALGORITHM)

3nf_synthesis_complete.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
ALGORITHM: 3NF Synthesis (Bernstein Algorithm)
 
INPUT: Universal relation R, Functional dependencies F
OUTPUT: 3NF decomposition D with lossless join and dependency preservation
 
//=== STEP 1: Compute Canonical Cover ===
1. Compute canonical cover Fc of F:
   a. Combine FDs with same left side
   b. Remove extraneous left-side attributes  
   c. Remove redundant FDs
   d. Repeat until no changes
 
//=== STEP 2: Create Relations from FDs ===
2. Initialize D = ∅
3. FOR each FD (X → Y) in Fc:
   a. Create relation Ri = X ∪ Y
   b. Set primary key of Ri = X
   c. Add Ri to D
 
//=== STEP 3: Ensure Candidate Key Presence ===
4. Find a candidate key K of R using F
5. IF no relation in D contains K:
   a. Create relation Rk = K
   b. Set primary key of Rk = K
   c. Add Rk to D
 
//=== STEP 4: Remove Subsumed Relations ===
6. FOR each pair (Ri, Rj) in D:
   IF attributes(Ri) ⊆ attributes(Rj):
     Remove Ri from D
 
7. RETURN D
 
//=== GUARANTEES ===
// - Every relation in D is in 3NF
// - D is a lossless-join decomposition of R
// - D preserves all dependencies in F

Algorithm Complexity

The 3NF synthesis algorithm runs in polynomial time—O(n²) where n is the size of the schema and FD set. This makes it practical for real-world database design, even for large schemas with many dependencies.

Comprehensive Worked Example

Let's apply the complete algorithm to a realistic example.

Problem:

Relation R(A, B, C, D, E, F, G)

Functional Dependencies F = { A → B, A → C, C → D, CD → E, E → F, F → G }

Step 1: Canonical CoverComputing Fc from F

Input

Output

Step 2: Create RelationsOne relation per FD in Fc

Input

Output

Step 3: Ensure Key PresenceFind and verify candidate key

Input

Output

Step 4: Remove Subsumed RelationsEliminate redundant relations

Input

Output

Verification:

✓ All relations in 3NF: Each relation has the FD determinant as its key, so all non-trivial FDs are on superkeys

✓ Lossless join: R1 contains candidate key {A} of original R

✓ Dependency preserving: All FDs from Fc appear in exactly one relation:

A → BC in R1
C → D in R3 (C determines D even in R3)
CD → E in R3
E → F in R4
F → G in R5

Summary: The 3NF Synthesis Algorithm

We've thoroughly explored the 3NF synthesis algorithm—the systematic procedure for achieving Third Normal Form with guaranteed properties. Let's consolidate the key insights:

Key Takeaways

•Four-step process: Canonical cover → Create relations → Ensure key → Remove subsumed
•Canonical cover is essential: Minimizes FD set to avoid redundant relations
•One relation per FD: Each FD X → Y becomes relation R = X ∪ Y with key X
•Key relation for losslessness: If no relation contains a candidate key, add one
•Remove redundant relations: Subsumed relations (R₁ ⊆ R₂) can be safely removed
•Triple guarantee: Result is in 3NF, lossless-join, and dependency-preserving

What's Next:

Now that you understand the algorithm, the final page presents comprehensive 3NF examples from various domains, showing how the synthesis algorithm produces practical, real-world database schemas. You'll see the algorithm applied to e-commerce, healthcare, education, and other domains.

Page Complete

You now have complete mastery of the 3NF synthesis algorithm. You can decompose any relation into 3NF while guaranteeing lossless join and dependency preservation—the theoretical foundation for practical database normalization.

4 / 5

Loading learning content...

Database Management SystemsThird Normal Form (3NF)

Third Normal Form (3NF)

LevelIntermediate

Duration75 mins

TopicThird Normal Form (3NF)

4 / 5

3NF Synthesis Algorithm

Systematic Decomposition to Third Normal Form

What You Will Learn

Algorithm Overview and Guarantees

Before diving into the mechanics, let's understand what the 3NF synthesis algorithm accomplishes and why it works.

Algorithm Guarantees:

Given any relation R with functional dependencies F, the 3NF synthesis algorithm produces a decomposition {R₁, R₂, ..., Rₖ} such that:

Each Rᵢ is in Third Normal Form

The decomposition is lossless-join (R = R₁ ⋈ R₂ ⋈ ... ⋈ Rₖ)

The decomposition is dependency-preserving (F ⊆ (F₁ ∪ F₂ ∪ ... ∪ Fₖ)⁺)

No other decomposition method for 3NF provides all three guarantees simultaneously. BCNF decomposition, by contrast, cannot always preserve dependencies.

3NF Synthesis Algorithm Properties
Property	Guarantee	Why It Matters
3NF Achieved	Every resulting relation satisfies 3NF	Eliminates transitive dependencies on non-prime attributes
Lossless Join	Join of all Rᵢ reproduces original R exactly	No spurious tuples introduced; no data lost
Dependency Preservation	All FDs in F can be enforced locally	Constraints can be checked without joining relations
Polynomial Time	Algorithm runs in O(n²) time	Practical for real-world schemas

High-Level Algorithm Structure:

Compute Canonical Cover — Minimize the set of FDs to remove redundancy
Create Relations from FDs — Each FD becomes a relation schema
Ensure Key Presence — Add a relation for a candidate key if needed
Remove Subsumed Relations — Eliminate redundant relations

Each step serves a specific purpose in achieving the guarantees. Let's examine each in detail.

Historical Note

Step 1: Computing the Canonical Cover

The first step is to compute the canonical cover (also called minimal cover) of the functional dependencies. This eliminates redundancy in the FD set before decomposition.

Why This Matters:

Redundant FDs create redundant relations in the final decomposition
Extraneous attributes on the left side of FDs create unnecessarily wide relations
Canonicalizing first ensures a minimal, clean decomposition

Canonical Cover Algorithm:

canonical_cover_algorithm.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
ALGORITHM: Compute Canonical Cover Fc of F
 
INPUT: Set of functional dependencies F
OUTPUT: Canonical cover Fc
 
1. Set Fc = F
 
2. REPEAT until no changes:
   
   2a. Combine FDs with same left side:
       Replace {X → A, X → B} with {X → AB}
   
   2b. Remove extraneous left-side attributes:
       For each FD (X → A) in Fc:
         For each attribute B in X:
           If A ∈ (Fc with X→A replaced by (X-B)→A)⁺:
             Replace X → A with (X - B) → A
   
   2c. Remove redundant FDs:
       For each FD (X → A) in Fc:
         If A ∈ (X)⁺ under (Fc - {X → A}):
           Remove X → A from Fc
 
3. RETURN Fc

Computing Canonical Cover ExampleF = {A → BC, B → C, A → B, AB → C}

Input

Output

Order Can Affect Final Form

Step 2: Creating Relations from Functional Dependencies

Once we have the canonical cover Fc, we create a relation for each FD. This is the heart of the synthesis algorithm.

The Core Insight:

If X → A is a functional dependency, then we should have a relation with attributes X ∪ {A} where X is the key.

This directly ensures that A depends on the key (X) and nothing but the key within that relation.

Relation Creation Rule:

create_relations.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
ALGORITHM: Create Relations from Canonical Cover
 
INPUT: Canonical cover Fc
OUTPUT: Set of relation schemas D
 
1. Initialize D = ∅
 
2. FOR each FD (X → Y) in Fc:
   Create relation schema Ri = X ∪ Y
   Designate X as the primary key of Ri
   Add Ri to D
 
3. RETURN D

Creating Relations from FDsCanonical cover Fc = {A → BC, B → C, D → E}

Input

Output

Why This Guarantees Dependency Preservation:

Each FD X → Y becomes the key-to-nonkey relationship in its own relation. The FD can be verified by checking just that relation:

To verify A → BC, check relation R1(A, B, C): For any value of A, B and C are uniquely determined
To verify B → C, check relation R2(B, C): For any value of B, C is uniquely determined

No joins required—each constraint is local to its dedicated relation.

Combining FDs with Same Left Side

Step 3: Ensuring Candidate Key Presence

Why This Is Necessary:

Key Presence Check:

ensure_key.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
ALGORITHM: Ensure Candidate Key Presence
 
INPUT: Set of relation schemas D, Original relation R, FD set F
OUTPUT: Updated D with key guarantee
 
1. Find a candidate key K of R (using F)
 
2. Check if any Ri in D contains K:
   FOR each Ri in D:
     If K ⊆ attributes(Ri):
       RETURN D  // Key already present, done
 
3. If no Ri contains K:
   Create new relation Rk = K
   Designate K as the primary key of Rk
   Add Rk to D
 
4. RETURN D

Adding Key Relation ExampleR(A, B, C, D) with Fc = {A → B, C → D}, Key = {A, C}

Input

Output

When Is the Key Relation Needed?

The key relation is typically needed when:

The original relation has a composite key
No single FD has the complete key on its left side
The key attributes are distributed across multiple FDs

When Is It Already Present?

If some FD has X → Y where X is a superkey of R, that relation already contains the key
Common in simple schemas where the primary key determines everything directly

Any Candidate Key Works

Step 4: Removing Subsumed (Redundant) Relations

The final step removes redundant relations—those whose attributes are entirely contained within another relation in the decomposition.

Why Remove Subsumed Relations?

If R₁ ⊆ R₂ (all attributes of R₁ are in R₂), then R₁ is redundant
Keeping R₁ wastes storage and creates maintenance overhead
The FDs preserved in R₁ are also preserved in R₂

Subsumption Removal:

remove_subsumed.txt
1
2
3
4
5
6
7
8
9
10
11
12
ALGORITHM: Remove Subsumed Relations
 
INPUT: Set of relation schemas D
OUTPUT: Minimal set of relation schemas D'
 
1. Initialize D' = D
 
2. FOR each pair (Ri, Rj) in D' where i ≠ j:
   IF attributes(Ri) ⊆ attributes(Rj):
     Remove Ri from D'
 
3. RETURN D'

Removing Subsumed Relations ExampleFrom running example

Input

Output

Critical Insight: Why FDs Are Still Preserved

When R₂(B, C) is subsumed by R₁(A, B, C), the FD B → C is not lost:

B → C can still be verified in R₁
Every tuple in R₁ establishes the B → C relationship
The constraint enforcement mechanism simply checks R₁ instead of R₂

Subsumption vs. Overlap:

Be careful to distinguish:

Subsumption: R₁ ⊆ R₂ means ALL attributes of R₁ are in R₂ (remove R₁)
Overlap: Some attributes shared, but neither contains the other (keep both)

Don't Remove Too Aggressively

Only remove relations that are completely subsumed. If Rᵢ has even one attribute not in Rⱼ, keep both relations. Premature removal can lose attributes or dependencies.

The Complete 3NF Synthesis Algorithm

Now let's put all the steps together into the complete algorithm:

3NF SYNTHESIS ALGORITHM (BERNSTEIN ALGORITHM)

3nf_synthesis_complete.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
ALGORITHM: 3NF Synthesis (Bernstein Algorithm)
 
INPUT: Universal relation R, Functional dependencies F
OUTPUT: 3NF decomposition D with lossless join and dependency preservation
 
//=== STEP 1: Compute Canonical Cover ===
1. Compute canonical cover Fc of F:
   a. Combine FDs with same left side
   b. Remove extraneous left-side attributes  
   c. Remove redundant FDs
   d. Repeat until no changes
 
//=== STEP 2: Create Relations from FDs ===
2. Initialize D = ∅
3. FOR each FD (X → Y) in Fc:
   a. Create relation Ri = X ∪ Y
   b. Set primary key of Ri = X
   c. Add Ri to D
 
//=== STEP 3: Ensure Candidate Key Presence ===
4. Find a candidate key K of R using F
5. IF no relation in D contains K:
   a. Create relation Rk = K
   b. Set primary key of Rk = K
   c. Add Rk to D
 
//=== STEP 4: Remove Subsumed Relations ===
6. FOR each pair (Ri, Rj) in D:
   IF attributes(Ri) ⊆ attributes(Rj):
     Remove Ri from D
 
7. RETURN D
 
//=== GUARANTEES ===
// - Every relation in D is in 3NF
// - D is a lossless-join decomposition of R
// - D preserves all dependencies in F

Algorithm Complexity

Comprehensive Worked Example

Let's apply the complete algorithm to a realistic example.

Problem:

Relation R(A, B, C, D, E, F, G)

Functional Dependencies F = { A → B, A → C, C → D, CD → E, E → F, F → G }

Step 1: Canonical CoverComputing Fc from F

Input

Output

Step 2: Create RelationsOne relation per FD in Fc

Input

Output

Step 3: Ensure Key PresenceFind and verify candidate key

Input

Output

Step 4: Remove Subsumed RelationsEliminate redundant relations

Input

Output

Verification:

✓ All relations in 3NF: Each relation has the FD determinant as its key, so all non-trivial FDs are on superkeys

✓ Lossless join: R1 contains candidate key {A} of original R

✓ Dependency preserving: All FDs from Fc appear in exactly one relation:

A → BC in R1
C → D in R3 (C determines D even in R3)
CD → E in R3
E → F in R4
F → G in R5

Summary: The 3NF Synthesis Algorithm

We've thoroughly explored the 3NF synthesis algorithm—the systematic procedure for achieving Third Normal Form with guaranteed properties. Let's consolidate the key insights:

Key Takeaways

•Four-step process: Canonical cover → Create relations → Ensure key → Remove subsumed
•Canonical cover is essential: Minimizes FD set to avoid redundant relations
•One relation per FD: Each FD X → Y becomes relation R = X ∪ Y with key X
•Key relation for losslessness: If no relation contains a candidate key, add one
•Remove redundant relations: Subsumed relations (R₁ ⊆ R₂) can be safely removed
•Triple guarantee: Result is in 3NF, lossless-join, and dependency-preserving

What's Next:

Page Complete

4 / 5