Kaushik's Notes

4NF - Fourth Normal Form

7 min read

Overview

  • Definition: A relation is in 4NF if, for every non-trivial multivalued dependency X ↠ Y, X is a superkey
  • Purpose: Eliminates multivalued dependencies to reduce redundancy
  • Requirement: Must first be in BCNF
  • Focus: Addresses scenarios where one attribute determines multiple independent sets of values

Key Concepts

Multivalued Dependency (MVD)

  • Definition: For attributes A, B, and C, A multidetermines B (A ↠ B) if for each value of A, there exists a set of values for B that is independent of C
  • Notation: A ↠ B (read as “A multidetermines B”)
  • Independence: Values of B depend only on A, not on other attributes
  • Example: Employee ↠ Skill, Employee ↠ Language (skills and languages are independent)

Trivial vs Non-trivial MVD

  • Trivial MVD: A ↠ B where B ⊆ A or A ∪ B = all attributes
  • Non-trivial MVD: A ↠ B where B ⊄ A and A ∪ B ≠ all attributes
  • 4NF Concern: Only non-trivial MVDs violate 4NF, and only when A is not a superkey

Join Dependency

  • Related Concept: MVDs are special cases of join dependencies
  • Lossless Join: Decomposition must preserve original information when joined back

Rules for 4NF

Prerequisites

  • Must be in BCNF: All functional dependency anomalies eliminated
  • Identify MVDs: Find all multivalued dependencies

Requirements

  • No Non-trivial MVDs on Non-Superkeys: Every non-trivial MVD X ↠ Y must have a superkey X; eliminate the rest
  • Independence: Separate independent multivalued attributes into different tables
  • Lossless Decomposition: Ensure decomposition doesn’t lose information

Violations of 4NF

Example 1: Employee Skills and Languages

Table in BCNF but NOT 4NF:

Employee_Skills_Languages Table:
Emp_ID | Skill      | Language
E001   | Java       | English
E001   | Java       | Spanish
E001   | Python     | English
E001   | Python     | Spanish
E002   | JavaScript | English
E002   | JavaScript | French
E002   | C++        | English
E002   | C++        | French

Multivalued Dependencies:

  • Emp_ID ↠ Skill (Employee determines skills independently of languages)
  • Emp_ID ↠ Language (Employee determines languages independently of skills)

Problem: Cartesian product creates redundancy - every skill paired with every language

Example 2: Course Prerequisites and Textbooks

Table in BCNF but NOT 4NF:

Course_Info Table:
Course_ID | Prerequisite | Textbook
CS201     | CS101        | Database Systems
CS201     | CS101        | SQL Guide
CS201     | MA101        | Database Systems
CS201     | MA101        | SQL Guide
CS301     | CS201        | Networks Basics
CS301     | CS202        | Networks Basics

Multivalued Dependencies:

  • Course_ID ↠ Prerequisite
  • Course_ID ↠ Textbook

Problem: Prerequisites and textbooks are independent but create redundant combinations

Converting to 4NF

Example 1: Employee Skills and Languages

Before (BCNF but not 4NF):

Employee_Skills_Languages Table:
Emp_ID | Skill      | Language
E001   | Java       | English
E001   | Java       | Spanish
E001   | Python     | English
E001   | Python     | Spanish
E002   | JavaScript | English
E002   | JavaScript | French
E002   | C++        | English
E002   | C++        | French

After (4NF):

Employee_Skills Table:
Emp_ID | Skill
E001   | Java
E001   | Python
E002   | JavaScript
E002   | C++

Employee_Languages Table:
Emp_ID | Language
E001   | English
E001   | Spanish
E002   | English
E002   | French

Verification: Original data can be reconstructed by joining on Emp_ID (every skill of an employee pairs with every language of that employee, which is exactly what Emp_ID ↠ Skill | Language requires; if E002 only had JavaScript-English and C++-French, the MVD would not hold and the join would add rows)

Example 2: Course Prerequisites and Textbooks

Before (BCNF but not 4NF):

Course_Info Table:
Course_ID | Prerequisite | Textbook
CS201     | CS101        | Database Systems
CS201     | CS101        | SQL Guide
CS201     | MA101        | Database Systems
CS201     | MA101        | SQL Guide
CS301     | CS201        | Networks Basics
CS301     | CS202        | Networks Basics

After (4NF):

Course_Prerequisites Table:
Course_ID | Prerequisite
CS201     | CS101
CS201     | MA101
CS301     | CS201
CS301     | CS202

Course_Textbooks Table:
Course_ID | Textbook
CS201     | Database Systems
CS201     | SQL Guide
CS301     | Networks Basics

Example 3: Student Activities and Subjects

Before (BCNF but not 4NF):

Student_Activities_Subjects Table:
Student_ID | Activity | Subject
S001       | Soccer   | Math
S001       | Soccer   | Physics
S001       | Chess    | Math
S001       | Chess    | Physics
S002       | Drama    | English
S002       | Drama    | History
S002       | Debate   | English
S002       | Debate   | History

After (4NF):

Student_Activities Table:
Student_ID | Activity
S001       | Soccer
S001       | Chess
S002       | Drama
S002       | Debate

Student_Subjects Table:
Student_ID | Subject
S001       | Math
S001       | Physics
S002       | English
S002       | History

Real-World Examples

University Course Management

Before (Not 4NF):

Course_Faculty_Rooms Table:
Course_ID | Faculty_ID | Room_ID
CS101     | F001       | R101
CS101     | F001       | R102
CS101     | F002       | R101
CS101     | F002       | R102
MA201     | F003       | R201
MA201     | F004       | R201

MVDs: Course_ID ↠ Faculty_ID, Course_ID ↠ Room_ID

After (4NF):

Course_Faculty Table:
Course_ID | Faculty_ID
CS101     | F001
CS101     | F002
MA201     | F003
MA201     | F004

Course_Rooms Table:
Course_ID | Room_ID
CS101     | R101
CS101     | R102
MA201     | R201

Project Team Assignment

Before (Not 4NF):

Project_Team_Tools Table:
Project_ID | Team_Member | Tool
P001       | Alice       | IDE
P001       | Alice       | Database
P001       | Bob         | IDE
P001       | Bob         | Database
P002       | Charlie     | Compiler
P002       | David       | Compiler

After (4NF):

Project_Team Table:
Project_ID | Team_Member
P001       | Alice
P001       | Bob
P002       | Charlie
P002       | David

Project_Tools Table:
Project_ID | Tool
P001       | IDE
P001       | Database
P002       | Compiler

Restaurant Menu System

Before (Not 4NF):

Restaurant_Cuisines_Dietary Table:
Restaurant_ID | Cuisine_Type | Dietary_Option
R001          | Italian      | Vegetarian
R001          | Italian      | Vegan
R001          | Mexican      | Vegetarian
R001          | Mexican      | Vegan
R002          | Chinese      | Gluten-Free
R002          | Thai         | Gluten-Free

After (4NF):

Restaurant_Cuisines Table:
Restaurant_ID | Cuisine_Type
R001          | Italian
R001          | Mexican
R002          | Chinese
R002          | Thai

Restaurant_Dietary Table:
Restaurant_ID | Dietary_Option
R001          | Vegetarian
R001          | Vegan
R002          | Gluten-Free

Benefits of 4NF

Eliminates Redundancy

  • Reduces Storage: Eliminates unnecessary Cartesian products
  • No Duplicate Information: Each fact stored once
  • Example: Employee skills not repeated for each language

Prevents MVD Anomalies

Insert Anomaly Prevention

  • Before 4NF: Adding new skill requires adding rows for all languages
  • After 4NF: Add skill independently in skills table

Update Anomaly Prevention

  • Before 4NF: Changing employee’s language affects multiple skill rows
  • After 4NF: Update language once in languages table

Delete Anomaly Prevention

  • Before 4NF: Removing last skill might remove language information
  • After 4NF: Skills and languages maintained independently

Improved Data Integrity

  • Independence: Separate independent concerns
  • Consistency: Easier to maintain consistent data
  • Validation: Simpler validation rules

Implementation Steps

Step 1: Ensure BCNF

  • Verify table is in Boyce-Codd Normal Form
  • All functional dependencies properly handled

Step 2: Identify Multivalued Dependencies

  • Look for attributes that determine multiple independent sets
  • Check for Cartesian product patterns in data
  • Identify cases where A ↠ B and A ↠ C independently

Step 3: Verify Independence

  • Confirm that multivalued attributes are truly independent
  • Test if values of one MVD attribute affect values of another
  • Check business rules for dependencies

Step 4: Decompose into Separate Tables

  • Create separate table for each multivalued dependency
  • Use the determining attribute as foreign key
  • Ensure each table represents single multivalued relationship

Step 5: Verify Lossless Join

  • Test that original data can be reconstructed
  • Join decomposed tables on determining attribute
  • Confirm no information is lost or added

Complex Scenarios

Multiple MVDs with Overlapping Attributes

Before:

Employee_Projects_Skills_Locations Table:
Emp_ID | Project_ID | Skill | Location

MVDs:

  • Emp_ID ↠ Project_ID
  • Emp_ID ↠ Skill
  • Emp_ID ↠ Location

After (4NF):

Employee_Projects Table:
Emp_ID | Project_ID

Employee_Skills Table:
Emp_ID | Skill

Employee_Locations Table:
Emp_ID | Location

Conditional MVDs

Sometimes MVDs are conditional on other attributes:

Example:

Course_Section_Info Table:
Course_ID | Section | Instructor | Time_Slot

Conditional MVD: For each Course_ID, Section ↠ Instructor only if multiple instructors per section allowed

When 4NF May Not Be Practical

Performance Considerations

  • Join Overhead: Multiple joins may impact query performance
  • Read-Heavy Systems: Denormalization might be preferred for reporting
  • Complex Queries: May require multiple table joins

Business Constraints

  • Real Dependencies: What appears as MVD might have business dependencies
  • Reporting Requirements: Some reports need denormalized view
  • Historical Data: Snapshot requirements might prevent normalization

Summary

  • Purpose: Eliminates multivalued dependencies and associated redundancy
  • Rule: Every non-trivial multivalued dependency’s left side must be a superkey
  • Requirement: Must be in BCNF first
  • Benefit: Reduces storage, prevents MVD anomalies, improves integrity
  • Trade-off: May increase join complexity for queries
  • Use Case: When independent multivalued relationships exist

Graph View

Backlinks