3NF Synthesis Algorithm — Third Normal Form (3NF) | OneNoughtOne

0/131

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 \subseteq (F₁ \cup F₂ \cup ... \cup 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 Example

F = {A → BC, B → C, A → B, AB → C}

•Initial F: {A → BC, B → C, A → B, AB → C}
•
•Step 2a: Combine same left sides
•A → BC and A → B → combine to A → BC (already there)
•
•Step 2b: Remove extraneous left attributes
•Check AB → C: Is C ∈ {A}⁺?
•{A}⁺ = {A, B, C} (using A → BC)
•Yes! So B is extraneous. Replace AB → C with A → C
•F = {A → BC, B → C, A → B, A → C}
•
•Step 2c: Remove redundant FDs
•A → C: Is C ∈ {A}⁺ under F - {A → C}?
•{A}⁺ = {A, B, C} (via A → BC)
•Yes! A → C is redundant. Remove it.
•F = {A → BC, B → C, A → B}
•
•A → B: Is B ∈ {A}⁺ under F - {A → B}?
•{A}⁺ = {A, B, C} (via A → BC)
•Yes! A → B is implied by A → BC.
•F = {A → BC, B → C}
•
•Canonical Cover Fc = {A → BC, B → C}

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 \to A is a functional dependency, then we should have a relation with attributes X \cup {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 FDs

Canonical cover Fc = {A → BC, B → C, D → E}

•Step 2: Create relation for each FD:
•
•FD: A → BC
•Relation R1 = {A} ∪ {B, C} = {A, B, C}
•Primary Key: A
•
•FD: B → C
•Relation R2 = {B} ∪ {C} = {B, C}
•Primary Key: B
•
•FD: D → E
•Relation R3 = {D} ∪ {E} = {D, E}
•Primary Key: D
•
•Intermediate Result D = {R1(A, B, C), R2(B, C), R3(D, E)}

Why This Guarantees Dependency Preservation: Each FD X \to Y becomes the key-to-nonkey relationship in its own relation. The FD can be verified by checking just that relation: To verify A \to BC, check relation R1(A, B, C): For any value of A, B and C are uniquely determined To verify B \to 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 \to B and A \to 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 Example

R(A, B, C, D) with Fc = {A → B, C → D}, Key = {A, C}

•From Step 2:
•R1(A, B) with key A
•R2(C, D) with key C
•
•Step 3: Check for candidate key {A, C}
•R1 contains {A} — missing C
•R2 contains {C} — missing A
•Neither contains {A, C}!
•
•Add key relation:
•R3(A, C) with key {A, C}
•
•Final D = {R1(A, B), R2(C, D), R3(A, C)}
•
•Now decomposition is guaranteed lossless:
•R3 contains a candidate key of the original R

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 \to 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₁ \subseteq 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 Example

From running example

•Before Step 4:
•R1(A, B, C) with key A [from A → BC]
•R2(B, C) with key B [from B → C]
•R3(D, E) with key D [from D → E]
•
•Check subsumptions:
•Is R1 ⊆ R2? {A,B,C} ⊆ {B,C}? No
•Is R2 ⊆ R1? {B,C} ⊆ {A,B,C}? YES! R2 is subsumed by R1
•Is R3 related to R1 or R2? No overlapping attributes
•
•Remove R2:
•
•Final decomposition: {R1(A, B, C), R3(D, E)}
•
•Note: The FD B → C is still preserved in R1!
•In R1(A, B, C), for any B value, C is uniquely determined

Critical Insight: Why FDs Are Still Preserved When R₂(B, C) is subsumed by R₁(A, B, C), the FD B \to C is not lost: B \to C can still be verified in R₁ Every tuple in R₁ establishes the B \to C relationship The constraint enforcement mechanism simply checks R₁ instead of R₂ Subsumption vs. Overlap: Be careful to distinguish: Subsumption: R₁ \subseteq 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 \to B, A \to C, C \to D, CD \to E, E \to F, F \to G }

Step 1: Canonical Cover

Computing Fc from F

•Original F: {A → B, A → C, C → D, CD → E, E → F, F → G}
•
•Combine same left sides:
•A → B and A → C become A → BC
•F = {A → BC, C → D, CD → E, E → F, F → G}
•
•Check extraneous left attributes in CD → E:
•Is D extraneous? Check if E ∈ {C}⁺
•{C}⁺ = {C, D} (using C → D)
•E ∉ {C}⁺, so D is NOT extraneous in CD → E
•
•Is C extraneous? Check if E ∈ {D}⁺
•{D}⁺ = {D}
•E ∉ {D}⁺, so C is NOT extraneous in CD → E
•
•Check for redundant FDs: None found
•
•Canonical Cover Fc = {A → BC, C → D, CD → E, E → F, F → G}

Step 2: Create Relations

One relation per FD in Fc

•A → BC: R1(A, B, C) with key A
•C → D: R2(C, D) with key C
•CD → E: R3(C, D, E) with key {C, D}
•E → F: R4(E, F) with key E
•F → G: R5(F, G) with key F
•
•Intermediate D = {R1, R2, R3, R4, R5}

Step 3: Ensure Key Presence

Find and verify candidate key

•Find candidate key of R(A, B, C, D, E, F, G):
•{A}⁺ = {A, B, C, D, E, F, G} = all attributes!
•Candidate key: {A}
•
•Check if {A} is in any relation:
•R1(A, B, C) contains A ✓
•
•Key already present. No new relation needed.

Step 4: Remove Subsumed Relations

Eliminate redundant relations

•Check subsumptions:
•R2(C, D) vs R3(C, D, E): {C, D} ⊆ {C, D, E}? YES!
•R2 is subsumed by R3. Remove R2.
•
•No other subsumptions exist.
•
•Final Decomposition:
•R1(A, B, C) with key A [preserves A → BC]
•R3(C, D, E) with key {C, D} [preserves CD → E and C → D]
•R4(E, F) with key E [preserves E → F]
•R5(F, G) with key F [preserves F → G]

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 \to BC in R1 C \to D in R3 (C determines D even in R3) CD \to E in R3 E \to F in R4 F \to G in R5

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 \subseteq (F₁ \cup F₂ \cup ... \cup 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 Example

F = {A → BC, B → C, A → B, AB → C}

•Initial F: {A → BC, B → C, A → B, AB → C}
•
•Step 2a: Combine same left sides
•A → BC and A → B → combine to A → BC (already there)
•
•Step 2b: Remove extraneous left attributes
•Check AB → C: Is C ∈ {A}⁺?
•{A}⁺ = {A, B, C} (using A → BC)
•Yes! So B is extraneous. Replace AB → C with A → C
•F = {A → BC, B → C, A → B, A → C}
•
•Step 2c: Remove redundant FDs
•A → C: Is C ∈ {A}⁺ under F - {A → C}?
•{A}⁺ = {A, B, C} (via A → BC)
•Yes! A → C is redundant. Remove it.
•F = {A → BC, B → C, A → B}
•
•A → B: Is B ∈ {A}⁺ under F - {A → B}?
•{A}⁺ = {A, B, C} (via A → BC)
•Yes! A → B is implied by A → BC.
•F = {A → BC, B → C}
•
•Canonical Cover Fc = {A → BC, B → C}

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 \to A is a functional dependency, then we should have a relation with attributes X \cup {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 FDs

Canonical cover Fc = {A → BC, B → C, D → E}

•Step 2: Create relation for each FD:
•
•FD: A → BC
•Relation R1 = {A} ∪ {B, C} = {A, B, C}
•Primary Key: A
•
•FD: B → C
•Relation R2 = {B} ∪ {C} = {B, C}
•Primary Key: B
•
•FD: D → E
•Relation R3 = {D} ∪ {E} = {D, E}
•Primary Key: D
•
•Intermediate Result D = {R1(A, B, C), R2(B, C), R3(D, E)}

Why This Guarantees Dependency Preservation: Each FD X \to Y becomes the key-to-nonkey relationship in its own relation. The FD can be verified by checking just that relation: To verify A \to BC, check relation R1(A, B, C): For any value of A, B and C are uniquely determined To verify B \to 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 \to B and A \to 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 Example

R(A, B, C, D) with Fc = {A → B, C → D}, Key = {A, C}

•From Step 2:
•R1(A, B) with key A
•R2(C, D) with key C
•
•Step 3: Check for candidate key {A, C}
•R1 contains {A} — missing C
•R2 contains {C} — missing A
•Neither contains {A, C}!
•
•Add key relation:
•R3(A, C) with key {A, C}
•
•Final D = {R1(A, B), R2(C, D), R3(A, C)}
•
•Now decomposition is guaranteed lossless:
•R3 contains a candidate key of the original R

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 \to 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₁ \subseteq 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 Example

From running example

•Before Step 4:
•R1(A, B, C) with key A [from A → BC]
•R2(B, C) with key B [from B → C]
•R3(D, E) with key D [from D → E]
•
•Check subsumptions:
•Is R1 ⊆ R2? {A,B,C} ⊆ {B,C}? No
•Is R2 ⊆ R1? {B,C} ⊆ {A,B,C}? YES! R2 is subsumed by R1
•Is R3 related to R1 or R2? No overlapping attributes
•
•Remove R2:
•
•Final decomposition: {R1(A, B, C), R3(D, E)}
•
•Note: The FD B → C is still preserved in R1!
•In R1(A, B, C), for any B value, C is uniquely determined

Critical Insight: Why FDs Are Still Preserved When R₂(B, C) is subsumed by R₁(A, B, C), the FD B \to C is not lost: B \to C can still be verified in R₁ Every tuple in R₁ establishes the B \to C relationship The constraint enforcement mechanism simply checks R₁ instead of R₂ Subsumption vs. Overlap: Be careful to distinguish: Subsumption: R₁ \subseteq 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 \to B, A \to C, C \to D, CD \to E, E \to F, F \to G }

Step 1: Canonical Cover

Computing Fc from F

•Original F: {A → B, A → C, C → D, CD → E, E → F, F → G}
•
•Combine same left sides:
•A → B and A → C become A → BC
•F = {A → BC, C → D, CD → E, E → F, F → G}
•
•Check extraneous left attributes in CD → E:
•Is D extraneous? Check if E ∈ {C}⁺
•{C}⁺ = {C, D} (using C → D)
•E ∉ {C}⁺, so D is NOT extraneous in CD → E
•
•Is C extraneous? Check if E ∈ {D}⁺
•{D}⁺ = {D}
•E ∉ {D}⁺, so C is NOT extraneous in CD → E
•
•Check for redundant FDs: None found
•
•Canonical Cover Fc = {A → BC, C → D, CD → E, E → F, F → G}

Step 2: Create Relations

One relation per FD in Fc

•A → BC: R1(A, B, C) with key A
•C → D: R2(C, D) with key C
•CD → E: R3(C, D, E) with key {C, D}
•E → F: R4(E, F) with key E
•F → G: R5(F, G) with key F
•
•Intermediate D = {R1, R2, R3, R4, R5}

Step 3: Ensure Key Presence

Find and verify candidate key

•Find candidate key of R(A, B, C, D, E, F, G):
•{A}⁺ = {A, B, C, D, E, F, G} = all attributes!
•Candidate key: {A}
•
•Check if {A} is in any relation:
•R1(A, B, C) contains A ✓
•
•Key already present. No new relation needed.

Step 4: Remove Subsumed Relations

Eliminate redundant relations

•Check subsumptions:
•R2(C, D) vs R3(C, D, E): {C, D} ⊆ {C, D, E}? YES!
•R2 is subsumed by R3. Remove R2.
•
•No other subsumptions exist.
•
•Final Decomposition:
•R1(A, B, C) with key A [preserves A → BC]
•R3(C, D, E) with key {C, D} [preserves CD → E and C → D]
•R4(E, F) with key E [preserves E → F]
•R5(F, G) with key F [preserves F → G]

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 \to BC in R1 C \to D in R3 (C determines D even in R3) CD \to E in R3 E \to F in R4 F \to G in R5

3NF Synthesis Algorithm

Systematic Decomposition to Third Normal Form

Algorithm Overview and Guarantees

Step 1: Computing the Canonical Cover

Step 2: Creating Relations from Functional Dependencies

Step 3: Ensuring Candidate Key Presence

Step 4: Removing Subsumed (Redundant) Relations

The Complete 3NF Synthesis Algorithm

Comprehensive Worked Example

There’s more to understand.

3NF Synthesis Algorithm

Systematic Decomposition to Third Normal Form

Algorithm Overview and Guarantees

Step 1: Computing the Canonical Cover

Step 2: Creating Relations from Functional Dependencies

Step 3: Ensuring Candidate Key Presence

Step 4: Removing Subsumed (Redundant) Relations

The Complete 3NF Synthesis Algorithm

Comprehensive Worked Example

There’s more to understand.