Database Normalization, Functional Dependencies & Relational Schema Design - Databases & SQL Engineering

⚡ Designing the Truth: A software system is only as reliable as its data schema. A poorly designed relational schema leads to duplicate data, disk bloat, and insidious corruption anomalies where updating a single user attribute leaves the database in a self-contradictory state. Normalization is the systematic mathematical technique used to eliminate data redundancy and preserve integrity.

1. The 3 Destructive Data Anomalies

Consider an unnormalized table storing student course registrations in a single wide table:

UNNORMALIZED TABLE: STUDENT_COURSES
┌────────────┬──────────────┬───────────┬──────────────┬──────────────────┐
│ student_id │ student_name │ course_id │ course_title │ instructor_email │
├────────────┼──────────────┼───────────┼──────────────┼──────────────────┤
│ 101        │ Alice        │ CS101     │ Algorithms   │ turing@univ.edu  │
│ 102        │ Bob          │ CS101     │ Algorithms   │ turing@univ.edu  │
│ 103        │ Charlie      │ CS201     │ Systems      │ ritchie@univ.edu │
└────────────┴──────────────┴───────────┴──────────────┴──────────────────┘

This monolithic structure exhibits three critical operational flaws known as Data Anomalies:

1. Insertion Anomaly

You cannot add a new course (e.g. CS301: Cryptography) to the database until at least one student registers for it, because student_id is part of the primary key and cannot be NULL.

2. Update Anomaly

If Professor Turing changes their email, you must update 1,000 distinct registration rows. If the server crashes halfway through, the database enters an inconsistent state with two conflicting emails.

3. Deletion Anomaly

If Charlie drops out of university and you delete his row, you accidentally delete all knowledge that course CS201: Systems and Professor Ritchie ever existed.

2. Functional Dependencies ($X \to Y$)

The foundation of normalization is the concept of a Functional Dependency:

Functional Dependency
Given a relation R, attribute Y is functionally dependent on attribute X (written X ➔ Y) if and only if each distinct value of X is associated with precisely one value of Y.

X is called the Determinant.
Y is called the Dependent.

Examples of Functional Dependencies:
• user_id ➔ email, name, date_of_birth
• course_id ➔ course_title, credits, instructor_email
• (student_id, course_id) ➔ grade, enrollment_date

3. The Progressive Normal Forms (1NF to BCNF)

Normalization decomposes wide tables into smaller, linked relations without losing data (lossless decomposition).

THE NORMALIZATION STAIRCASE:
┌────────────────────────────────────────────────────────┐
│ BCNF: Every determinant is a candidate superkey        │
├────────────────────────────────────────────────────────┤
│ 3NF: In 2NF + No Transitive Dependencies (X ➔ Y ➔ Z)   │
├────────────────────────────────────────────────────────┤
│ 2NF: In 1NF + No Partial Dependencies on Composite Key │
├────────────────────────────────────────────────────────┤
│ 1NF: Atomic column values & No repeating array groups   │
└────────────────────────────────────────────────────────┘

1. First Normal Form (1NF): Atomic Values

Every column must contain only single, atomic (indivisible) values.
No multi-valued attributes (e.g. storing a comma-separated list of phone numbers in one field).
Each row must have a unique identifier (Primary Key).

VIOLATES 1NF (Multi-valued comma list):
┌────────────┬──────────────┬──────────────────────────────────┐
│ student_id │ name         │ phone_numbers                    │
├────────────┼──────────────┼──────────────────────────────────┤
│ 101        │ Alice        │ 555-0100, 555-0101, 555-0102     │ ◄── Non-atomic!
└────────────┴──────────────┴──────────────────────────────────┘

SATISFIES 1NF (Atomic rows):
┌────────────┬──────────────┬──────────────┐
│ student_id │ name         │ phone_number │
├────────────┼──────────────┼──────────────┤
│ 101        │ Alice        │ 555-0100     │
│ 101        │ Alice        │ 555-0101     │
│ 101        │ Alice        │ 555-0102     │
└────────────┴──────────────┴──────────────┘

2. Second Normal Form (2NF): No Partial Dependencies

The relation must be in 1NF.
Every non-key attribute must depend on the entire primary key, not just a subset of a composite primary key.

VIOLATES 2NF (Composite Key: student_id + course_id):
student_name depends ONLY on student_id (Partial Dependency)!
course_title depends ONLY on course_id (Partial Dependency)!

2NF DECOMPOSITION (Split into 3 Clean Relations):
1. STUDENTS:      [ student_id (PK), student_name ]
2. COURSES:       [ course_id (PK), course_title ]
3. ENROLLMENTS:   [ student_id (FK), course_id (FK), grade ]

3. Third Normal Form (3NF): No Transitive Dependencies

The relation must be in 2NF.
No non-key attribute can depend on another non-key attribute (X ➔ Y and Y ➔ Z where X is the Primary Key).

VIOLATES 3NF (Transitive dependency: order_id ➔ customer_id ➔ customer_city):
┌──────────┬─────────────┬─────────────┬───────────────┐
│ order_id │ order_date  │ customer_id │ customer_city │
├──────────┼─────────────┼─────────────┼───────────────┤
│ 9001     │ 2026-08-21  │ 42          │ Zurich        │
└──────────┴─────────────┴─────────────┴───────────────┘
order_id (PK) determines customer_id. customer_id determines customer_city.

3NF DECOMPOSITION:
1. CUSTOMERS: [ customer_id (PK), customer_city ]
2. ORDERS:    [ order_id (PK), order_date, customer_id (FK) ]

4. Boyce-Codd Normal Form (BCNF): Strict Superkeys

The relation must be in 3NF.
For every non-trivial functional dependency X ➔ Y, X must be a Superkey (a candidate key).
BCNF resolves edge cases where multiple overlapping composite candidate keys exist.

4. Keys & Relational Integrity

A resilient schema relies on clear constraints:

┌───────────────────────────┬────────────────────────────────────────────────────────┐
│ Key Type                  │ Architectural Role & Purpose                           │
├───────────────────────────┼────────────────────────────────────────────────────────┤
│ Primary Key (PK)          │ Unique, non-null identifier for every tuple in table.   │
│ Foreign Key (FK)          │ Reference pointing to the Primary Key of another table.│
│ Natural Key               │ Business attribute with unique guarantee (e.g. SSN).   │
│ Surrogate Key             │ Synthetic identifier generated by database (ID / UUID).│
└───────────────────────────┴────────────────────────────────────────────────────────┘

Foreign Key Referential Actions:

When a parent record is deleted or updated, the foreign key enforces integrity rules:

ON DELETE RESTRICT / NO ACTION: Rejects the parent deletion if children exist (default safety).
ON DELETE CASCADE: Automatically deletes all child rows when the parent is deleted.
ON DELETE SET NULL: Sets the child’s foreign key column to NULL.

5. Normalized (OLTP) vs Denormalized (OLAP) Architectures

While 3NF is the gold standard for Online Transaction Processing (OLTP) (where fast writes and data integrity are paramount), analytical warehouses (OLAP) often selectively denormalize tables:

OLTP (Transactional Systems)            OLAP (Data Warehouses & Analytics)
───────────────────────────────────     ──────────────────────────────────
• Normalized (3NF / BCNF)               • Denormalized (Star / Snowflake Schema)
• Optimized for INSERT / UPDATE / DELETE• Optimized for heavy analytical SELECT scans
• Zero data redundancy                  • Duplicate data accepted for zero-join speed
• Relies on foreign key constraints     • Columnar storage (ClickHouse, BigQuery, Snowflake)

6. Key Takeaways & Summary

💡 Schema Design Best Practices

Data Anomalies: Insertion, Update, and Deletion anomalies are symptoms of unnormalized schemas with redundant attributes.
1NF: Ensure atomic values and eliminate multi-valued array lists.
2NF: Eliminate partial dependencies on composite keys.
3NF: Eliminate transitive dependencies (non-key columns depending on other non-key columns).
Surrogate Keys: Use auto-incrementing 64-bit BIGINT or UUIDv7 for stable primary keys that are decoupled from changing business logic.