3.2 Functional Dependencies, Normal Forms, and Verifiable Decomposition

A customer changes their name, but several task tables retain different copies. Reports now disagree about one fact. Normalization uses functional dependencies to decide which facts belong together, then checks whether the split preserves reconstruction and enforceable rules. Fewer duplicate values are useful; fewer surviving facts are a problem.

A Mixed Relation

Suppose we have the following relation:

TaskAssignment(
  task_id,
  item_id,
  customer_id,
  customer_name,
  item_name,
  quantity,
  reward_cents
)

The business rules define the following functional dependencies:

task_id -> customer_id, reward_cents
customer_id -> customer_name
item_id -> item_name
(task_id, item_id) -> quantity

If a task can be associated with multiple items, then the candidate key is (task_id, item_id). Replicating customer and item names in each row of the assignment table leads to update, insert, and delete anomalies.

The Meaning of Functional Dependency

X -> Y means: in all valid relation states, if two tuples have the same value for X, they must have the same value for Y.

It is a business invariant, not a correlation inferred from current sample data. The fact that each name is currently unique does not prove name -> id; instead, it must be guaranteed by business rules that all future valid states will satisfy this condition.

Trivial vs. Non-Trivial

If Y ⊆ X, then X -> Y is trivial, for example, (task_id, item_id) -> task_id. Normalization primarily focuses on non-trivial dependencies.

Attribute closure and candidate key

Using Armstrong's axioms, we can derive functional dependencies:

• Reflexivity: If Y ⊆ X, then X -> Y;
• Augmentation: If X -> Y, then XZ -> YZ;
• Transitivity: If X -> Y and Y -> Z, then X -> Z.

Compute the closure of (task_id, item_id):

start: task_id, item_id
task_id -> customer_id, reward_cents
customer_id -> customer_name
item_id -> item_name
(task_id, item_id) -> quantity

closure = all attributes

Thus, it is a superkey; if either attribute is removed, the remaining set no longer determines all attributes, so it remains a candidate key.

A relation may have multiple candidate keys. One is chosen as the PRIMARY KEY; the others should still be enforced using UNIQUE + NOT NULL constraints.

1NF: Don't Reduce It to "No Arrays"

First Normal Form requires that relation attributes take atomic values within the domain of the relational model and that there be no repeating groups. What constitutes "atomic" depends on the specific domain and query semantics: a database might treat JSON as a single value, but if business logic requires foreign key references, joins, or independent updates on individual item IDs within that JSON, treating it as an opaque scalar loses the relational constraints.

When evaluating whether a structure belongs to the current relation model and requires independent operations, the name of the storage type is irrelevant.

2NF: Eliminating Partial Dependencies on Candidate Keys

The 2NF requires that a relation be in 1NF and that every non-prime attribute fully functionally depend on every candidate key.

Under the composite key (task_id, item_id):

task_id → reward_cents
item_id → item_name

these attributes depend only on part of the key, violating 2NF. To resolve this, we decompose the relation into:

tasks(task_id, customer_id, customer_name, reward_cents)
Items(item_id, item_name)
TaskItems(task_id, item_id, quantity)

If every candidate key in a relation has only one attribute, there can be no partial dependency, thus, 2NF is automatically satisfied. However, such a relation may still violate 3NF or BCNF.

3NF: Handling transitive dependency

In tasks(task_id, customer_id, customer_name, reward_cents):

task_id -> customer_id
customer_id -> customer_name

Thus, task_id -> customer_name is a transitive dependency. The customer_name describes a customer and should not be redundantly stored for every task:

Customers(customer_id, customer_name)
tasks(task_id, customer_id, reward_cents)

The formal 3NF condition: for every non-trivial functional dependency X -> A, either X is a superkey, or A is a prime attribute (part of some candidate key). The mnemonic "non-key attributes depend only on keys" is helpful for beginners, but becomes imprecise when dealing with multiple candidate keys.

BCNF: Every determinant is a superkey

BCNF requires that for every non-trivial functional dependency X -> Y, the left-hand side X must be a superkey. It is stricter than 3NF.

Some relations can satisfy 3NF but not BCNF, because the right-hand side contains a prime attribute. Decomposing to BCNF may fail to preserve all dependencies, forcing designers to make trade-offs between stronger redundancy control and dependency preservation.

For example, let Teaching(student, course, instructor) have dependencies student, course -> instructor and instructor -> course. Its candidate keys are (student, course) and (student, instructor). The right side of instructor -> course is prime, so the relation satisfies 3NF, but the determinant is not a superkey, so it fails BCNF.

Splitting it into InstructorCourse(instructor, course) and StudentInstructor(student, instructor) gives a lossless join. Yet local keys in those tables cannot prevent a student from taking the same course with two instructors. Choosing BCNF therefore requires accounting for the cost of that cross-table constraint. The Berkeley normalization notes give the formal definitions of lossless joins and dependency preservation.

Lossless Join Is the Baseline for Decomposition

When a relation R is decomposed into R1 and R2, a natural join of R1 and R2 must reconstruct the original relation exactly, without introducing spurious tuples or losing any factual data.

For binary decomposition, a commonly used criterion is that the common attributes (the intersection) functionally determine one of the subrelations:

(R1 ∩ R2) → R1
or
(R1 ∩ R2) → R2

For example:

R(task_id, customer_id, customer_name)
R1(task_id, customer_id)
R2(customer_id, customer_name)

The intersection is customer_id, and customer_id -> customer_name, so this binary decomposition is lossless.

Dependency preservation

A decomposition is dependency-preserving if each original dependency can be verified using a single relation constraint or a combination of its projections, without requiring a join of all relations.

Lossless decomposition and dependency preservation are two distinct properties. A decomposition may be lossless yet still require cross-table joins to enforce certain dependencies, which increases the cost of constraint enforcement.

Map to SQL schema

This is a separate SQLite 3.37.0+ modeling exercise using STRICT tables. Start with an empty database and enable PRAGMA foreign_keys = ON on the connection. These tables omit some columns from the earlier chapters' tables of the same names.

CREATE TABLE customers (
    customer_id   INTEGER PRIMARY KEY,
    customer_name TEXT NOT NULL
) STRICT;

CREATE TABLE items (
    item_id   INTEGER PRIMARY KEY,
    item_name TEXT NOT NULL
) STRICT;

CREATE TABLE tasks (
    task_id      INTEGER PRIMARY KEY,
    customer_id INTEGER NOT NULL,
    reward_cents  INTEGER NOT NULL CHECK (reward_cents >= 0),
    FOREIGN KEY (customer_id)
        REFERENCES customers(customer_id)
) STRICT;

CREATE TABLE task_items (
    task_id INTEGER NOT NULL,
    item_id  INTEGER NOT NULL,
    quantity INTEGER NOT NULL CHECK (quantity > 0),
    PRIMARY KEY (task_id, item_id),
    FOREIGN KEY (task_id) REFERENCES tasks(task_id),
    FOREIGN KEY (item_id) REFERENCES items(item_id)
) STRICT;

This schema expresses the listed dependencies but does not capture status transitions, historical prices, or tenant isolation; normalization does not replace complete domain modeling.

Denormalization Is Controlled Replication

Replicating customer_name for read performance, maintaining summary tables, or building materialized views can be reasonable, but only after answering key questions:

• Who is the source of truth?
• When is synchronization triggered: during the same transaction, via async events, or through periodic refreshes?
• How long can data staleness be tolerated?
• How are failures compensated or rebuilt?
• How is drift detected?
• Is denormalization actually more effective than index-based queries, query rewriting, or caching?

Denormalization deliberately maintains extra representations of facts whose dependencies are understood.

Don't Use Normalization to Solve Every Problem

Normalization primarily addresses dependency and redundancy. However, certain problems require alternative mechanisms:

• concurrent write anomalies: transaction isolation and concurrency control;
• append-only audit trails: history and event modeling;
• analytics performance: columnar storage and materialization;
• distributed consistency: replication, consensus, and transaction protocols;
• authorization: policy and access control;
• schema evolution: migration, backfill, and compatibility.

Exercise

Given:

Enrollment(student_id, course_id, instructor_id,
           student_name, course_title, instructor_office, grade)

and the following functional dependencies:

student_id -> student_name
course_id -> course_title, instructor_id
instructor_id -> instructor_office
(student_id, course_id) -> grade

1. Determine (student_id, course_id)+.
2. Identify partial and transitive dependencies.
3. Decompose into 3NF.
4. Explain why each step is lossless.
5. List keys, foreign keys, unique constraints, and check constraints, and identify rules that still cannot be directly enforced using these constraints.

Acceptance Criteria

• [ ] FDs derived from business invariants, not guessed from sample data;
• [ ] Ability to use closure to identify candidate keys;
• [ ] Precise definitions of 2NF, 3NF, and BCNF;
• [ ] Decomposition checks for lossless join and dependency preservation;
• [ ] Denormalization clearly specifies source, freshness, and repair mechanisms;
• [ ] Normalization is not conflated with transaction isolation.

Chapter Summary

ER modeling determines which identities and relationships the system must record, while functional dependencies verify that each relation does not mix multiple determining factors. A well-designed schema clearly assigns business facts, keys, dependencies, and lifecycle rules, enforcing them through constraints and transactional execution. The number of tables is not the goal.