Decomposition for Second Normal Form

In the previous pages, you mastered identifying 2NF violations. Now comes the crucial step: fixing them. The cure for partial dependencies is decomposition—splitting a violating relation into smaller relations that each satisfy 2NF.

But decomposition must be done carefully. A careless split can lose information, break constraints, or create other problems. This page teaches you the systematic approach to decomposition that guarantees correctness while eliminating partial dependencies.

The fundamental principle behind 2NF decomposition is elegantly simple:

Core Idea:

If attribute A partially depends on subset S of the key K, then A "belongs" in a separate relation where S is the full key.

Why This Works:

Partial dependencies exist because we're storing an attribute (A) in a relation where the key (K) contains "extra" information beyond what's needed to determine A. By moving A to a relation where its true determinant (S) is the key, we:

1. Eliminate redundancy: A is stored once per unique value of S, not repeated for every combination of K
2. Enable proper updates: Changing A requires updating one row, not many
3. Prevent anomalies: Insert/delete anomalies disappear because A exists independently

The Decomposition Trade-off:

We split one table into multiple tables. This means:

• Read operations may require joins to reconstruct the original data
• Write operations may span multiple tables
• Schema complexity increases

However, the benefits of data integrity and reduced redundancy typically outweigh these costs, especially as data scales.

Here is the systematic algorithm for decomposing a relation to achieve 2NF:

Algorithm: DECOMPOSE-TO-2NF(R, F)

Input:

• R: A relation with attributes and primary key K
• F: Functional dependencies over R

Output:

• A set of relations, all in 2NF, that together preserve R's information

Algorithm Explanation:

Step 1: Use the detection algorithm from the previous page to find all partial dependencies.

Step 2: Group the partially dependent attributes by their determinant. Attributes with the same determinant go into the same new relation.

Step 3: For each group:

• Create a new relation containing the determinant and its dependent attributes
• The determinant becomes the primary key of this new relation
• Remove the dependent attributes from the original relation

Step 4: The original relation now contains only:

• The full composite key
• Attributes that fully depend on the entire key

Key Insight: The original composite key remains in the decomposed relation as a foreign key reference to the new relations, maintaining the relationships.

Let's apply the algorithm to a comprehensive example.

Original Relation:

StudentCourse(StudentID, CourseID, StudentName, StudentEmail, 
              CourseName, Credits, InstructorID, Grade, EnrollDate)

Primary Key: {StudentID, CourseID}

Functional Dependencies:

Step 1: Detect Partial Dependencies

From analysis:

• {StudentID} → StudentName ✗
• {StudentID} → StudentEmail ✗
• {CourseID} → CourseName ✗
• {CourseID} → Credits ✗
• {CourseID} → InstructorID ✗

Five partial dependencies found.

Step 2: Group by Determinant

Step 3: Create New Relations

New Relation 1: Student

CREATE TABLE Student (
    StudentID    INT PRIMARY KEY,
    StudentName  VARCHAR(100) NOT NULL,
    StudentEmail VARCHAR(100) UNIQUE
);

New Relation 2: Course

CREATE TABLE Course (
    CourseID     INT PRIMARY KEY,
    CourseName   VARCHAR(100) NOT NULL,
    Credits      INT NOT NULL,
    InstructorID INT NOT NULL
);

Step 4: Modified Original Relation

Remove partially dependent attributes, keep only:

• The composite key: StudentID, CourseID
• Fully dependent attributes: Grade, EnrollDate

CREATE TABLE Enrollment (
    StudentID  INT,
    CourseID   INT,
    Grade      CHAR(2),
    EnrollDate DATE NOT NULL,
    PRIMARY KEY (StudentID, CourseID),
    FOREIGN KEY (StudentID) REFERENCES Student(StudentID),
    FOREIGN KEY (CourseID) REFERENCES Course(CourseID)
);

A decomposition is lossless (or lossless-join) if we can reconstruct the original relation exactly by natural joining the decomposed relations. No information is lost or spuriously created.

Formal Definition:

A decomposition of R into R₁ and R₂ is lossless if:

R = R₁ ⋈ R₂  (natural join)

The Lossless Join Condition:

Decomposition of R into R₁(X) and R₂(Y) is lossless if and only if:

(X ∩ Y) → (X - Y)  OR  (X ∩ Y) → (Y - X)

In words: The common attributes must be a key for at least one of the decomposed relations.

Why 2NF Decomposition Is Always Lossless:

When we decompose for 2NF:

• New relation R₁ contains determinant S and its dependent attributes A
• Original relation R keeps S (as part of the key) and removes A
• The common attribute is S
• S is the key of R₁ (by construction)
• Therefore, (S) → (attributes of R₁ - S) holds
• The lossless join condition is satisfied!

Verifying Losslessness in Our Example:

Original: StudentCourse(StudentID, CourseID, StudentName, StudentEmail, CourseName, Credits, InstructorID, Grade, EnrollDate)

Decomposition 1: Extracting Student

• R₁ = Student(StudentID, StudentName, StudentEmail)
• R₂ = Remaining(StudentID, CourseID, CourseName, Credits, InstructorID, Grade, EnrollDate)

Common: {StudentID}

Check: StudentID → (StudentName, StudentEmail)? YES Result: Lossless ✓

Decomposition 2: Extracting Course from Remaining

• R₁ = Course(CourseID, CourseName, Credits, InstructorID)
• R₂ = Enrollment(StudentID, CourseID, Grade, EnrollDate)

Common: {CourseID}

Check: CourseID → (CourseName, Credits, InstructorID)? YES Result: Lossless ✓

Full Verification:

Student ⋈ Course ⋈ Enrollment = original StudentCourse

A decomposition is dependency-preserving if all original functional dependencies can be enforced without computing joins across the decomposed relations.

Why It Matters:

If a dependency like A → B was in the original relation but A ends up in R₁ and B ends up in R₂, we can't enforce A → B using single-table constraints. We'd need triggers, application logic, or expensive cross-table checks.

Formal Definition:

Let F be the original FD set. Let F₁, F₂, ..., Fₙ be the projections of F onto the decomposed relations.

Decomposition is dependency-preserving if:

(F₁ ∪ F₂ ∪ ... ∪ Fₙ)⁺ = F⁺

That is, the closure of the union of projected dependencies equals the original closure.

Analysis for Our Example:

Original FDs:

• FD1: {StudentID, CourseID} → Grade, EnrollDate
• FD2: {StudentID} → StudentName, StudentEmail
• FD3: {CourseID} → CourseName, Credits, InstructorID

After Decomposition:

All original FDs are preserved in one of the decomposed relations!

This is not a coincidence. The 2NF decomposition algorithm preserves dependencies because:

1. Partial dependencies become single-table constraints (the extracted relations)
2. Full dependencies stay in the original relation
3. No dependency spans multiple tables after decomposition

Let's see the complete SQL implementation for decomposing a 2NF-violating table.

Step 1: Create the New Normalized Tables

Step 2: Migrate Data from the Original Table

Step 3: Verify the Decomposition

Real-world decomposition often involves additional complexities. Here are strategies for common challenges:

Case 1: Overlapping Partial Dependencies

When the same attribute appears in multiple partial dependencies:

R(A, B, C, D, E)
Key: {A, B}
FDs: A → C, B → C, {A,B} → D, E

Here, C depends on BOTH A and B independently. This is unusual (indicates C might be a constant or there's a design issue). Resolution:

1. Investigate if the FDs are actually correct (domain expert consultation)
2. If valid, choose one determinant for C (typically the more restrictive one)
3. Consider if C should be duplicated or if there's a deeper normalization issue

Case 2: Chained Partial Dependencies

R(A, B, C, D, E)
Key: {A, B}
FDs: A → C, C → D, {A,B} → E

Here, D depends on C, and C depends on A. This is both a partial dependency AND a transitive dependency.

Decomposition Approach:

1. First address partial dependencies (for 2NF):

   • Extract {A, C} → This also brings D along due to C → D
   • Or extract {A, C, D} directly

2. After 2NF, check for 3NF (C → D is transitive)

Result:

R1(A, C, D) — Key: A, but has transitive dep C → D
R2(A, B, E) — Key: {A, B}, in 2NF

R1 now needs 3NF decomposition (extract {C, D}).

Case 3: Multiple Candidate Keys

R(A, B, C, D, E)
Candidate Keys: {A, B}, {C, D}
FDs: A → E, C → E, {A,B} → ..., {C,D} → ...

Partial dependencies exist for BOTH composite keys.

Strategy:

1. Identify which key to use as primary (design decision)

2. Note that E partially depends on BOTH keys

3. When extracting E, include BOTH partial determinants if they determine E:

   • Option 1: {A, E} and {C, E} as separate tables (if A → E and C → E are different facts)
   • Option 2: {A, C, E} if the relationships are connected

4. The choice depends on semantics: Does E have one value determined by A, or by C, or are these independent?