Database Normalization: 1NF to BCNF, Anomalies & Schema Design

TAKEAWAYS:

• Normalization eliminates update, insert, and delete anomalies by removing redundant data and enforcing dependencies.
• Functional dependencies (X → Y) determine which attributes must be grouped together in a relation.
• Decomposition splits tables into 3NF/BCNF while preserving dependencies via lossless-join and dependency-preservation rules.
• Denormalization is a trade-off for read-heavy systems (e.g., eSewa’s transaction logs) but risks anomalies.
• BCNF is stricter than 3NF and handles transitive dependencies (e.g., Customer → Branch → Manager).
• Worked examples tie theory to real systems: Daraz’s order processing (3NF), Ncell’s billing (BCNF), and bank loans (4NF).

1. Why Normalization? The Problem of Anomalies

Databases without normalization suffer from three critical anomalies when data is duplicated or poorly structured:

stateDiagram-v2
    [*] --> Anomaly:Update
    Anomaly:Update --> "Changing one record affects others (e.g., updating a customer’s address in multiple orders)"
    Anomaly:Update --> Anomaly:Insert
    Anomaly:Insert --> "Cannot insert partial data (e.g., adding a new product with no sales yet)"
    Anomaly:Insert --> Anomaly:Delete
    Anomaly:Delete --> "Deleting a record loses unrelated data (e.g., deleting a customer removes their last order)"
    Anomaly:Delete --> [*]

Real-world example: eSewa’s transaction table If eSewa stores transactions like this:

Transaction(TransactionID, UserID, Amount, UserName, UserAddress, ServiceType)

• Update anomaly: Changing a user’s address requires updating every transaction for that user.
• Insert anomaly: Adding a new user with no transactions is impossible.
• Delete anomaly: Deleting a user’s last transaction removes their name/address forever.

2. Functional Dependencies: The Core of Normalization

A functional dependency (FD) is a constraint where one attribute (or set) determines another:

• X → Y: Every value of X maps to exactly one value of Y.
• Candidate key: A minimal set of attributes that can determine all other attributes in the relation.

Example: Daraz Order System

Order(OrderID, CustomerID, ProductID, Quantity, CustomerName, CustomerAddress, ProductPrice)

FDs:

• OrderID → CustomerID, ProductID, Quantity, CustomerName, CustomerAddress, ProductPrice (OrderID is the key)
• CustomerID → CustomerName, CustomerAddress (CustomerID determines name/address)
• ProductID → ProductPrice (ProductID determines price)

Visualizing FDs:

Key terms:

• Partial dependency: An attribute depends on part of a composite key (violates 2NF).
• Transitive dependency: An attribute depends on another non-key attribute (violates 3NF).

3. Normal Forms: Step-by-Step Rules

Normalization is a hierarchy of rules to eliminate anomalies. Each form builds on the previous one.

3.1 First Normal Form (1NF)

Rule: All attributes must contain atomic (indivisible) values, and the table must have a primary key. Violation example: A Products table with a Tags column storing multiple values (e.g., "Electronics, Gadgets").

Fix:

-- Before (violates 1NF)
Products(ProductID, Name, Tags)

-- After (1NF-compliant)
Products(ProductID, Name)
ProductTags(ProductID, Tag)

3.2 Second Normal Form (2NF)

Rule: Must satisfy 1NF and no partial dependencies (all non-key attributes must depend on the entire primary key). Applies only to tables with composite keys.

Example: Ncell Billing System Unnormalized table:

Bill(BillID, CustomerID, PhoneNumber, ServiceType, StartDate, EndDate, Amount)

FDs:

• BillID → CustomerID, PhoneNumber, ServiceType, StartDate, EndDate, Amount
• CustomerID → PhoneNumber (partial dependency on composite key BillID + CustomerID)

Decomposition to 2NF:

Customers(CustomerID, PhoneNumber)
Bills(BillID, CustomerID, ServiceType, StartDate, EndDate, Amount)

Mermaid diagram of 2NF decomposition:

erDiagram
    Customers ||--o{ Bills : "has"
    Customers {
        CustomerID pk
        PhoneNumber
    }
    Bills {
        BillID pk
        CustomerID fk
        ServiceType
        StartDate
        EndDate
        Amount
    }
    %% Add a note about 2NF: Partial dependencies removed (e.g., PhoneNumber no longer in Bills)
    %% Highlight the foreign key relationship visually
    Bills }|--|{ Customers : "belongs to"

3.3 Third Normal Form (3NF)

Rule: Must satisfy 2NF and no transitive dependencies (non-key attributes must not depend on other non-key attributes). Example: Bank Loan Database Unnormalized table:

Loans(LoanID, CustomerID, BranchID, LoanAmount, InterestRate, BranchName, BranchCity)

FDs:

• LoanID → CustomerID, BranchID, LoanAmount, InterestRate, BranchName, BranchCity
• BranchID → BranchName, BranchCity (transitive dependency via LoanID → BranchID)

Decomposition to 3NF:

Loans(LoanID, CustomerID, BranchID, LoanAmount, InterestRate)
Branches(BranchID, BranchName, BranchCity)

Real-world tie-in: Banks like NMB or Global IME use 3NF to avoid updating branch details across thousands of loans.

3.4 Boyce-Codd Normal Form (BCNF)

Rule: Stricter than 3NF. For every FD X → Y, X must be a superkey (candidate key or superset of one). Fixes "anomalous" 3NF tables where non-key attributes determine other non-key attributes.

Example: University Course Enrollment Unnormalized table:

Enrollment(StudentID, CourseID, InstructorID, Grade, InstructorName)

FDs:

• StudentID + CourseID → InstructorID, Grade, InstructorName
• InstructorID → InstructorName (violates BCNF because InstructorID is not a superkey)

Decomposition to BCNF:

Enrollment(StudentID, CourseID, InstructorID, Grade)
Instructors(InstructorID, InstructorName)

Comparison table: 1NF to BCNF

4. Decomposition Rules: How to Split Tables

To decompose a relation into normalized forms, use these theorems:

1. Lossless-Join Decomposition: Ensures no data is lost when rejoining tables.

   • Condition: The intersection of attributes in the two tables must be a candidate key for at least one table.
   • Example:

     R(A, B, C) decomposed into R1(A, B) and R2(B, C) is lossless because B is a key in R2.
     

2. Dependency-Preservation Decomposition: Ensures all FDs are preserved in the decomposed schema.

   • Example: For R(A, B, C) with FDs {A→B, B→C}, decompose into:

     R1(A, B) and R2(B, C) preserves both FDs.
     

Mermaid diagram of decomposition:

flowchart TD
    A["Original Table<br/>(R(A,B,C))"] --> B["Decompose<br/>R1(A,B)<br/>R2(B,C)"]
    B --> C["Lossless-Join<br/>Check: B is key in R2"]
    B --> D["Dependency-Preserved<br/>A→B and B→C intact"]

5. Higher Normal Forms (4NF, 5NF)

While 3NF/BCNF cover most cases, some systems need further normalization:

4NF: Multi-Valued Dependencies

Rule: Eliminates tables where an attribute has multiple independent values (e.g., a product with multiple tags). Example: Daraz Product Tags Unnormalized table:

Products(ProductID, Name, Tags)

FD: ProductID →→ Tags (multi-valued dependency, not functional).

Decomposition to 4NF:

Products(ProductID, Name)
ProductTags(ProductID, Tag)

5NF: Join Dependencies

Rule: For tables with complex join dependencies (rare in practice). Example: A table representing a many-to-many relationship that can’t be decomposed further without loss.

6. Denormalization: When to Break the Rules

Normalization improves write operations but may slow down reads. Some systems denormalize for performance:

• eSewa transactions: Combines Users, Transactions, and Services into a single table for faster reporting.
• YouTube recommendations: Uses denormalized "watch history" tables to speed up algorithm queries.

Trade-offs:

7. Worked Example: Normalizing a University Database

Problem: Design a database for a university with the following requirements:

• Students take courses.
• Courses have instructors.
• Instructors work in departments.

Initial unnormalized table:

StudentCourses(StudentID, Name, CourseID, CourseName, InstructorID, InstructorName, Department, Grade)

Step-by-step normalization:

1. 1NF: Already atomic (no repeating groups).
2. 2NF: No composite key → skip.
3. 3NF: Transitive dependencies:
   • CourseID → InstructorID, InstructorName, Department
   • InstructorID → InstructorName, Department Decompose:

   StudentCourses(StudentID, CourseID, Grade)
   Courses(CourseID, CourseName, InstructorID)
   Instructors(InstructorID, InstructorName, Department)
   

4. BCNF: Check for non-superkey determinants.
   • Courses: CourseID → InstructorID is fine (CourseID is key).
   • Instructors: No issues.

Final 3NF/BCNF schema:

erDiagram
    Students ||--o{ StudentCourses : "takes"
    StudentCourses ||--|| Courses : "has"
    Courses ||--|| Instructors : "taught by"
    Instructors }|--|| Departments : "works in"

    Students {
        StudentID pk
        Name
    }
    Courses {
        CourseID pk
        CourseName
        InstructorID fk
    }
    Instructors {
        InstructorID pk
        InstructorName
        DepartmentID fk
    }
    Departments {
        DepartmentID pk
        Department
    }
    StudentCourses {
        StudentID fk
        CourseID fk
        Grade
    }

8. Real-World Applications

Exam Tip

1. Always start with FDs: List all functional dependencies before normalizing. Examiners check if you identify them correctly.
2. Show decomposition steps: For each normal form, explicitly state:
   • Which rule is violated.
   • How you decompose the table.
   • Why the new schema is better.
3. Draw ER diagrams: For higher marks, sketch the normalized schema as an ER diagram (use mermaid or pencil).
4. Practice with real data: Use examples from banks (loans), e-commerce (orders), or telecom (billing) to tie theory to exams.
5. Watch for BCNF traps: If a table seems "normalized" but has a non-superkey determinant, it’s not BCNF.
6. Denormalization is a trade-off: If asked, explain why a system might denormalize (e.g., "for faster reports in eSewa").

Common exam pitfalls:

• Forgetting to check for multi-valued dependencies (4NF).
• Not verifying lossless-join after decomposition.
• Skipping 1NF checks (e.g., missing atomic values).
• Confusing 2NF (partial dependencies) with 3NF (transitive dependencies).