Database Normalization: 1NF, 2NF, 3NF, BCNF & Anomalies

Database normalization is a systematic process for organizing data in relational databases. Its primary goal is to reduce redundancy and prevent anomalies when manipulating data.

What is Normalization?

Normalization breaks down complex data structures into smaller, logically cohesive tables. By adhering to normal forms, we ensure data integrity and consistency.

Goals of Normalization

• Eliminate redundancy: Store data only once
• Prevent anomalies: Avoid update, insert, and delete anomalies
• Ensure data integrity: Maintain consistent data
• Improve maintainability: Make changes and extensions straightforward

Functional Dependencies

Core Concepts

A functional dependency describes the relationship between attributes in a relation.

-- Example: Student relation
CREATE TABLE Studenten (
    MatrikelNr INT PRIMARY KEY,
    Name VARCHAR(50),
    Semester INT,
    Fachbereich VARCHAR(50)
);

-- Functional dependencies:
-- MatrikelNr → Name (each enrollment ID maps to exactly one name)
-- MatrikelNr → Semester (each enrollment ID maps to exactly one semester)
-- MatrikelNr → Fachbereich (each enrollment ID maps to exactly one department)

Types of Functional Dependencies

-- Full functional dependency
CREATE TABLE Noten (
    MatrikelNr INT,
    VorlesungNr INT,
    Note DECIMAL(3,1),
    PRIMARY KEY (MatrikelNr, VorlesungNr)
);

-- (MatrikelNr, VorlesungNr) → Note (fully dependent)
-- MatrikelNr ↛ Note (independent)
-- VorlesungNr ↛ Note (independent)

-- Transitive functional dependency
CREATE TABLE Dozenten (
    DozentenNr INT PRIMARY KEY,
    Name VARCHAR(50),
    Fachbereich VARCHAR(50),
    FachbereichLeiter VARCHAR(50)
);

-- DozentenNr → Fachbereich
-- Fachbereich → FachbereichLeiter
-- DozentenNr → FachbereichLeiter (transitive)

Anomalies in Non-Normalized Data

Example of Anomalies

-- Non-normalized table with problems
CREATE TABLE Probleme_Tabelle (
    MatrikelNr INT,
    StudentName VARCHAR(50),
    VorlesungNr INT,
    VorlesungName VARCHAR(50),
    DozentNr INT,
    DozentName VARCHAR(50),
    Note DECIMAL(3,1),
    Semester INT
);

-- Sample data:
-- 101, 'Max Mustermann', 301, 'Datenbanken', 501, 'Prof. Schmidt', 1.3, 5
-- 101, 'Max Mustermann', 302, 'Algorithmen', 502, 'Prof. Mueller', 2.0, 5
-- 102, 'Erika Mustermann', 301, 'Datenbanken', 501, 'Prof. Schmidt', 1.7, 3

Types of Anomalies

1. Update Anomaly

-- Problem: changing a lecturer's name
UPDATE Probleme_Tabelle 
SET DozentName = 'Prof. Dr. Schmidt' 
WHERE DozentNr = 501;
-- Must be done for every occurrence!

2. Insert Anomaly

-- Problem: inserting a new lecture without students
INSERT INTO Probleme_Tabelle (MatrikelNr, VorlesungNr, VorlesungName, DozentNr, DozentName)
VALUES (NULL, 303, 'Software Engineering', 503, 'Prof. Weber');
-- Problem: MatrikelNr cannot be NULL (Primary Key)

3. Delete Anomaly

-- Problem: deleting the last student from a lecture
DELETE FROM Probleme_Tabelle 
WHERE MatrikelNr = 101 AND VorlesungNr = 302;
-- Loses information about lecture 302 and lecturer 502

First Normal Form (1NF)

Definition and Rules

A relation is in 1NF if:

1. All attributes are atomic (no repeating groups)
2. Each row is uniquely identifiable (Primary Key)
3. All attribute values come from the same domain

Implementing 1NF

-- Before: Not in 1NF (repeating groups)
CREATE TABLE Studenten_Vorher (
    MatrikelNr INT PRIMARY KEY,
    Name VARCHAR(50),
    Vorlesungen VARCHAR(200), -- "301,302,303"
    Noten VARCHAR(100)        -- "1.3,2.0,1.7"
);

-- After: In 1NF (atomic attributes)
CREATE TABLE Studenten_1NF (
    MatrikelNr INT PRIMARY KEY,
    Name VARCHAR(50),
    Semester INT
);

CREATE TABLE Belegungen_1NF (
    MatrikelNr INT,
    VorlesungNr INT,
    Note DECIMAL(3,1),
    PRIMARY KEY (MatrikelNr, VorlesungNr),
    FOREIGN KEY (MatrikelNr) REFERENCES Studenten_1NF(MatrikelNr)
);

-- Example with atomic values
INSERT INTO Studenten_1NF VALUES (101, 'Max Mustermann', 5);
INSERT INTO Belegungen_1NF VALUES (101, 301, 1.3);
INSERT INTO Belegungen_1NF VALUES (101, 302, 2.0);

1NF with JSON/XML (Modern Approaches)

-- PostgreSQL example with JSON
CREATE TABLE Studenten_Modern (
    MatrikelNr INT PRIMARY KEY,
    Name VARCHAR(50),
    Belegungen JSONB
);

INSERT INTO Studenten_Modern VALUES (
    101, 
    'Max Mustermann',
    '[
        {"vorlesungNr": 301, "note": 1.3},
        {"vorlesungNr": 302, "note": 2.0}
    ]'
);

-- Query using JSON functions
SELECT 
    MatrikelNr, 
    Name,
    vorlesung->>'vorlesungNr' AS Vorlesung,
    vorlesung->>'note' AS Note
FROM Studenten_Modern, 
     jsonb_array_elements(Belegungen) AS vorlesung
WHERE MatrikelNr = 101;

Second Normal Form (2NF)

Definition and Rules

A relation is in 2NF if:

1. It is in 1NF
2. All non-key attributes depend fully on the primary key

Problem: Partial Dependencies

-- Problem: Not in 2NF (partial dependencies)
CREATE TABLE Belegungen_Problem (
    MatrikelNr INT,
    VorlesungNr INT,
    StudentName VARCHAR(50),      -- Depends only on MatrikelNr
    VorlesungName VARCHAR(50),    -- Depends only on VorlesungNr
    DozentNr INT,                 -- Depends only on VorlesungNr
    Note DECIMAL(3,1),            -- Depends on (MatrikelNr, VorlesungNr)
    PRIMARY KEY (MatrikelNr, VorlesungNr)
);

-- Partial dependencies:
-- MatrikelNr → StudentName (partial)
-- VorlesungNr → VorlesungName, DozentNr (partial)
-- (MatrikelNr, VorlesungNr) → Note (full)

Implementing 2NF

-- Decomposition into 2NF
CREATE TABLE Studenten_2NF (
    MatrikelNr INT PRIMARY KEY,
    Name VARCHAR(50),
    Semester INT
);

CREATE TABLE Vorlesungen_2NF (
    VorlesungNr INT PRIMARY KEY,
    Name VARCHAR(50),
    DozentNr INT
);

CREATE TABLE Belegungen_2NF (
    MatrikelNr INT,
    VorlesungNr INT,
    Note DECIMAL(3,1),
    PRIMARY KEY (MatrikelNr, VorlesungNr),
    FOREIGN KEY (MatrikelNr) REFERENCES Studenten_2NF(MatrikelNr),
    FOREIGN KEY (VorlesungNr) REFERENCES Vorlesungen_2NF(VorlesungNr)
);

-- Sample data
INSERT INTO Studenten_2NF VALUES (101, 'Max Mustermann', 5);
INSERT INTO Vorlesungen_2NF VALUES (301, 'Datenbanken', 501);
INSERT INTO Belegungen_2NF VALUES (101, 301, 1.3);

Checking for 2NF

-- Test for partial dependencies
-- For each non-key attribute, verify:
-- Does it depend on the entire key?

-- Example: StudentName
-- Dependent on MatrikelNr? Yes
-- Dependent on VorlesungNr? No
-- → Partial dependency → Not in 2NF

-- Example: Note
-- Dependent on MatrikelNr? No
-- Dependent on VorlesungNr? No
-- Dependent on (MatrikelNr, VorlesungNr)? Yes
-- → Full dependency → In 2NF

Third Normal Form (3NF)

Definition and Rules

A relation is in 3NF if:

1. It is in 2NF
2. No transitive dependencies exist among non-key attributes

Problem: Transitive Dependencies

-- Problem: Not in 3NF (transitive dependencies)
CREATE TABLE Dozenten_Problem (
    DozentenNr INT PRIMARY KEY,
    Name VARCHAR(50),
    Fachbereich VARCHAR(50),
    FachbereichLeiter VARCHAR(50)
);

-- Transitive dependencies:
-- DozentenNr → Fachbereich
-- Fachbereich → FachbereichLeiter
-- DozentenNr → FachbereichLeiter (transitive)

Implementing 3NF

-- Decomposing into 3NF
CREATE TABLE Dozenten_3NF (
    DozentenNr INT PRIMARY KEY,
    Name VARCHAR(50),
    Fachbereich VARCHAR(50)
);

CREATE TABLE Fachbereiche_3NF (
    Fachbereich VARCHAR(50) PRIMARY KEY,
    Leiter VARCHAR(50)
);

-- Sample data
INSERT INTO Dozenten_3NF VALUES (501, 'Prof. Schmidt', 'Informatik');
INSERT INTO Fachbereiche_3NF VALUES ('Informatik', 'Prof. Dr. Meier');

Complex 3NF Example

-- Complete 3NF schema for a university
CREATE TABLE Studenten (
    MatrikelNr INT PRIMARY KEY,
    Name VARCHAR(50) NOT NULL,
    Geburtsdatum DATE,
    Fachbereich VARCHAR(50)
);

CREATE TABLE Fachbereiche (
    Fachbereich VARCHAR(50) PRIMARY KEY,
    Dekan VARCHAR(50),
    Gebaeude VARCHAR(20)
);

CREATE TABLE Dozenten (
    DozentenNr INT PRIMARY KEY,
    Name VARCHAR(50) NOT NULL,
    Fachbereich VARCHAR(50),
    FOREIGN KEY (Fachbereich) REFERENCES Fachbereiche(Fachbereich)
);

CREATE TABLE Vorlesungen (
    VorlesungNr INT PRIMARY KEY,
    Titel VARCHAR(100) NOT NULL,
    DozentenNr INT,
    Fachbereich VARCHAR(50),
    FOREIGN KEY (DozentenNr) REFERENCES Dozenten(DozentenNr),
    FOREIGN KEY (Fachbereich) REFERENCES Fachbereiche(Fachbereich)
);

CREATE TABLE Belegungen (
    MatrikelNr INT,
    VorlesungNr INT,
    Semester INT,
    Note DECIMAL(3,1),
    PRIMARY KEY (MatrikelNr, VorlesungNr, Semester),
    FOREIGN KEY (MatrikelNr) REFERENCES Studenten(MatrikelNr),
    FOREIGN KEY (VorlesungNr) REFERENCES Vorlesungen(VorlesungNr)
);

Boyce-Codd Normal Form (BCNF)

Definition and Rules

A relation is in BCNF if:

1. It is in 3NF
2. For every functional dependency X → Y: X is a superkey

Problem: BCNF Violation

-- Problem: Not in BCNF
CREATE TABLE Lehrveranstaltungen (
    DozentenNr INT,
    Fachbereich VARCHAR(50),
    VorlesungNr INT,
    PRIMARY KEY (DozentenNr, Fachbereich)
);

-- Data:
-- 501, 'Informatik', 301
-- 501, 'Mathematik', 401
-- 502, 'Informatik', 302

-- Functional dependencies:
-- (DozentenNr, Fachbereich) → VorlesungNr (primary key)
-- DozentenNr → Fachbereich (each instructor belongs to exactly one department)

-- Problem: DozentenNr → Fachbereich
-- DozentenNr is not a superkey → BCNF violation!

Implementing BCNF

-- Decomposing into BCNF
CREATE TABLE Dozenten_Fachbereich (
    DozentenNr INT PRIMARY KEY,
    Fachbereich VARCHAR(50)
);

CREATE TABLE Fachbereich_Vorlesungen (
    Fachbereich VARCHAR(50),
    DozentenNr INT,
    VorlesungNr INT,
    PRIMARY KEY (Fachbereich, DozentenNr)
);

-- Alternative BCNF solution
CREATE TABLE Dozenten (
    DozentenNr INT PRIMARY KEY,
    Fachbereich VARCHAR(50)
);

CREATE TABLE Vorlesungen_Dozenten (
    VorlesungNr INT,
    DozentenNr INT,
    PRIMARY KEY (VorlesungNr, DozentenNr),
    FOREIGN KEY (DozentenNr) REFERENCES Dozenten(DozentenNr)
);

BCNF vs 3NF

-- Example where 3NF ≠ BCNF
CREATE TABLE Projektmitarbeiter (
    ProjektNr INT,
    MitarbeiterNr INT,
    Rolle VARCHAR(50),
    PRIMARY KEY (ProjektNr, MitarbeiterNr)
);

-- Assumption: Each employee has exactly one role in each project
-- However: An employee can have the same role across different projects

-- Functional dependencies:
-- (ProjektNr, MitarbeiterNr) → Rolle (primary key)
-- MitarbeiterNr → Rolle (each employee has a fixed role)

-- BCNF violation: MitarbeiterNr → Rolle, but MitarbeiterNr is not a superkey

-- BCNF solution:
CREATE TABLE Mitarbeiter_Rolle (
    MitarbeiterNr INT PRIMARY KEY,
    Rolle VARCHAR(50)
);

CREATE TABLE Projekt_Mitarbeiter (
    ProjektNr INT,
    MitarbeiterNr INT,
    PRIMARY KEY (ProjektNr, MitarbeiterNr),
    FOREIGN KEY (MitarbeiterNr) REFERENCES Mitarbeiter_Rolle(MitarbeiterNr)
);

Normalization Process

Step-by-Step Guide

-- Step 0: Initial table (unnormalized)
CREATE TABLE Uni_Daten (
    MatrikelNr INT,
    StudentName VARCHAR(50),
    VorlesungNr INT,
    VorlesungName VARCHAR(50),
    DozentNr INT,
    DozentName VARCHAR(50),
    Fachbereich VARCHAR(50),
    Note DECIMAL(3,1),
    Semester INT
);

-- Step 1: 1NF - Atomic values
-- (already atomic in this example)

-- Step 2: 2NF - Eliminate partial dependencies
CREATE TABLE Studenten_2NF (
    MatrikelNr INT PRIMARY KEY,
    Name VARCHAR(50),
    Semester INT
);

CREATE TABLE Vorlesungen_2NF (
    VorlesungNr INT PRIMARY KEY,
    Name VARCHAR(50),
    DozentNr INT,
    Fachbereich VARCHAR(50)
);

CREATE TABLE Noten_2NF (
    MatrikelNr INT,
    VorlesungNr INT,
    Note DECIMAL(3,1),
    PRIMARY KEY (MatrikelNr, VorlesungNr)
);

-- Step 3: 3NF - Eliminate transitive dependencies
CREATE TABLE Dozenten_3NF (
    DozentenNr INT PRIMARY KEY,
    Name VARCHAR(50),
    Fachbereich VARCHAR(50)
);

CREATE TABLE Fachbereiche_3NF (
    Fachbereich VARCHAR(50) PRIMARY KEY,
    -- Additional department information
);

-- Final 3NF structure
CREATE TABLE Studenten (
    MatrikelNr INT PRIMARY KEY,
    Name VARCHAR(50),
    Semester INT
);

CREATE TABLE Fachbereiche (
    Fachbereich VARCHAR(50) PRIMARY KEY
);

CREATE TABLE Dozenten (
    DozentenNr INT PRIMARY KEY,
    Name VARCHAR(50),
    Fachbereich VARCHAR(50),
    FOREIGN KEY (Fachbereich) REFERENCES Fachbereiche(Fachbereich)
);

CREATE TABLE Vorlesungen (
    VorlesungNr INT PRIMARY KEY,
    Name VARCHAR(50),
    DozentenNr INT,
    Fachbereich VARCHAR(50),
    FOREIGN KEY (DozentenNr) REFERENCES Dozenten(DozentenNr),
    FOREIGN KEY (Fachbereich) REFERENCES Fachbereiche(Fachbereich)
);

CREATE TABLE Belegungen (
    MatrikelNr INT,
    VorlesungNr INT,
    Note DECIMAL(3,1),
    PRIMARY KEY (MatrikelNr, VorlesungNr),
    FOREIGN KEY (MatrikelNr) REFERENCES Studenten(MatrikelNr),
    FOREIGN KEY (VorlesungNr) REFERENCES Vorlesungen(VorlesungNr)
);

Normalization Algorithms

Synthesis Algorithm

-- Analyzing functional dependencies
-- F = {MatrikelNr → Name, VorlesungNr → Titel, DozentNr → Name, 
--       (MatrikelNr, VorlesungNr) → Note}

-- Step 1: Find minimal cover
-- F_min = {MatrikelNr → Name, VorlesungNr → Titel, 
--          DozentNr → Name, (MatrikelNr, VorlesungNr) → Note}

-- Step 2: Group by left-hand side
-- Group 1: MatrikelNr → Name → Relation Studenten(MatrikelNr, Name)
-- Group 2: VorlesungNr → Titel → Relation Vorlesungen(VorlesungNr, Titel)
-- Group 3: DozentNr → Name → Relation Dozenten(DozentenNr, Name)
-- Group 4: (MatrikelNr, VorlesungNr) → Note → Relation Noten(MatrikelNr, VorlesungNr, Note)

-- Step 3: Determine candidate keys and augment
-- Candidate key: (MatrikelNr, VorlesungNr) for Noten
-- Other relations have their own primary keys

Decomposition Algorithm

-- Initial table with anomalies
CREATE TABLE Probleme (
    A INT,
    B INT,
    C INT,
    D INT,
    PRIMARY KEY (A, B)
);

-- Functional dependencies: A → C, B → D

-- Step 1: Check for 2NF
-- C depends only on A (partial) → decompose
CREATE TABLE R1 (A INT PRIMARY KEY, C INT);
CREATE TABLE R2 (A INT, B INT, D INT, PRIMARY KEY (A, B));

-- Step 2: Check for 3NF
-- In R2: B → D (transitive via (A,B) → B) → decompose
CREATE TABLE R3 (B INT PRIMARY KEY, D INT);
CREATE TABLE R4 (A INT, B INT, PRIMARY KEY (A, B));

-- Final 3NF structure
-- R1(A, C), R3(B, D), R4(A, B)

Practical Examples

E-Commerce Database

-- Normalized e-commerce schema
CREATE TABLE Customers (
    CustomerID INT PRIMARY KEY,
    Name VARCHAR(50),
    Email VARCHAR(100) UNIQUE,
    Address VARCHAR(200),
    City VARCHAR(50),
    PostalCode VARCHAR(10)
);

CREATE TABLE Categories (
    CategoryID INT PRIMARY KEY,
    Name VARCHAR(50),
    Description TEXT
);

CREATE TABLE Products (
    ProductID INT PRIMARY KEY,
    Name VARCHAR(100),
    Price DECIMAL(10,2),
    Description TEXT,
    CategoryID INT,
    StockLevel INT,
    FOREIGN KEY (CategoryID) REFERENCES Categories(CategoryID)
);

CREATE TABLE Orders (
    OrderID INT PRIMARY KEY,
    CustomerID INT,
    OrderDate DATE,
    TotalAmount DECIMAL(10,2),
    Status VARCHAR(20),
    FOREIGN KEY (CustomerID) REFERENCES Customers(CustomerID)
);

CREATE TABLE OrderItems (
    OrderID INT,
    ProductID INT,
    Quantity INT,
    UnitPrice DECIMAL(10,2),
    PRIMARY KEY (OrderID, ProductID),
    FOREIGN KEY (OrderID) REFERENCES Orders(OrderID),
    FOREIGN KEY (ProductID) REFERENCES Products(ProductID)
);

Library System

-- Normalized library schema
CREATE TABLE Authors (
    AuthorID INT PRIMARY KEY,
    Name VARCHAR(50),
    BirthYear INT
);

CREATE TABLE Books (
    BookID INT PRIMARY KEY,
    Title VARCHAR(100),
    ISBN VARCHAR(20) UNIQUE,
    PublicationYear INT,
    Publisher VARCHAR(50)
);

CREATE TABLE Book_Authors (
    BookID INT,
    AuthorID INT,
    PRIMARY KEY (BookID, AuthorID),
    FOREIGN KEY (BookID) REFERENCES Books(BookID),
    FOREIGN KEY (AuthorID) REFERENCES Authors(AuthorID)
);

CREATE TABLE Readers (
    ReaderNumber INT PRIMARY KEY,
    Name VARCHAR(50),
    Address VARCHAR(200),
    Phone VARCHAR(20)
);

CREATE TABLE Copies (
    CopyID INT PRIMARY KEY,
    BookID INT,
    Status VARCHAR(20),
    FOREIGN KEY (BookID) REFERENCES Books(BookID)
);

CREATE TABLE Loans (
    LoanID INT PRIMARY KEY,
    ReaderNumber INT,
    CopyID INT,
    LoanDate DATE,
    ReturnDate DATE,
    FOREIGN KEY (ReaderNumber) REFERENCES Readers(ReaderNumber),
    FOREIGN KEY (CopyID) REFERENCES Copies(CopyID)
);

Denormalization

When and Why Denormalize?

-- Performance-optimized schema (denormalized)
CREATE TABLE Product_Statistics (
    ProductID INT PRIMARY KEY,
    Name VARCHAR(100),
    Price DECIMAL(10,2),
    CategoryName VARCHAR(50),       -- Denormalized
    CategoryDescription TEXT,       -- Denormalized
    TotalSaleQuantity INT,          -- Denormalized (aggregate)
    LastOrderDate DATE              -- Denormalized (aggregate)
);

-- Advantages:
-- Fewer JOINs required
-- Faster queries
-- Better read performance

-- Disadvantages:
-- Redundancy
-- Update anomalies
-- Increased storage requirements

Denormalization Strategies

-- 1. Precomputed aggregates
CREATE TABLE MonthlySales (
    Month DATE,
    ProductID INT,
    SalesQuantity INT,
    Revenue DECIMAL(12,2),
    PRIMARY KEY (Month, ProductID)
);

-- 2. Copied attributes
CREATE TABLE Orders_Summary (
    OrderID INT PRIMARY KEY,
    CustomerName VARCHAR(50),      -- Copied from Customers
    CustomerEmail VARCHAR(100),    -- Copied from Customers
    OrderDate DATE,
    TotalAmount DECIMAL(10,2)
);

-- 3. Hierarchical data
CREATE TABLE Employee_Hierarchy (
    EmployeeID INT PRIMARY KEY,
    Name VARCHAR(50),
    ManagerID INT,
    Path VARCHAR(200),             -- Denormalized path
    Level INT                      -- Denormalized depth
);

Exam Concepts

Key Definitions

1. Functional dependency: X → Y means Y depends on X
2. Full dependency: Y depends on the entire X
3. Partial dependency: Y depends on part of X
4. Transitive dependency: X → Y and Y → Z ⇒ X → Z

Normal Forms Overview

Normal Form	Primary Problem	Solution
1NF	Repeating groups	Atomic values
2NF	Partial dependencies	Decomposition by keys
3NF	Transitive dependencies	Elimination of transitivity
BCNF	Non-key determinants	Every determinant is a superkey

Common Exam Tasks

1. Identify functional dependencies
2. Normalize given relations
3. Explain anomalies and their causes
4. Compare normal forms
5. Decide on denormalization

Summary

Normalization is fundamental to quality database design:

• 1NF: Atomic values and unique rows
• 2NF: Eliminates partial dependencies
• 3NF: Eliminates transitive dependencies
• BCNF: Strongest normal form for practical use

Striking the right balance between normalization and performance is critical for successful database systems.

---

Recommended Reading: Databases