3.2 Function Dependencies, Normal Forms, and Verifiable Decomposition

A resident's address is scattered across multiple registration tables. When one copy is updated, the others retain the old value, leading to contradictory facts in the archive city.

"Eliminate data redundancy" is merely an intuitive goal of normalization, it is not a formal definition. Normalization begins with functional dependencies: it determines whether attributes are properly determined by keys, and verifies whether a decomposition is lossless and preserves critical dependencies.

A Mixed Relation

Suppose we have the following relation:

QuestAssignment(
  quest_id,
  item_id,
  adventurer_id,
  adventurer_name,
  item_name,
  quantity,
  reward_cents
)

The business rules define the following functional dependencies:

quest_id -> adventurer_id, reward_cents
adventurer_id -> adventurer_name
item_id -> item_name
(quest_id, item_id) -> quantity

If a quest can be associated with multiple items, then the candidate key is (quest_id, item_id). Replicating adventurer 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, (quest_id, item_id) -> quest_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 (quest_id, item_id):

start: quest_id, item_id
quest_id -> adventurer_id, reward_cents
adventurer_id -> adventurer_name
item_id -> item_name
(quest_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 (quest_id, item_id):

quest_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:

Quests(quest_id, adventurer_id, reward_cents)
Items(item_id, item_name)
QuestItems(quest_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 Quests(quest_id, adventurer_id, adventurer_name, reward_cents):

quest_id -> adventurer_id
adventurer_id -> adventurer_name

Thus, quest_id -> adventurer_name is a transitive dependency. The adventurer_name describes an adventurer and should not be redundantly stored for every quest:

Adventurers(adventurer_id, adventurer_name)
Quests(quest_id, adventurer_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.

Neither "3NF is sufficient" nor "all tables must be in BCNF" constitutes a professional conclusion. Designers should list all dependencies, prove decomposition properties, and make decisions based on the actual constraint capabilities.

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(quest_id, adventurer_id, adventurer_name)
R1(quest_id, adventurer_id)
R2(adventurer_id, adventurer_name)

The intersection is adventurer_id, and adventurer_id -> adventurer_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, this increases the cost of constraint enforcement.

Map to SQL schema

CREATE TABLE adventurers (
    adventurer_id   INTEGER PRIMARY KEY,
    adventurer_name TEXT NOT NULL
);

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

CREATE TABLE quests (
    quest_id      INTEGER PRIMARY KEY,
    adventurer_id INTEGER NOT NULL,
    reward_cents  INTEGER NOT NULL CHECK (reward_cents >= 0),
    FOREIGN KEY (adventurer_id)
        REFERENCES adventurers(adventurer_id)
);

CREATE TABLE quest_items (
    quest_id INTEGER NOT NULL,
    item_id  INTEGER NOT NULL,
    quantity INTEGER NOT NULL CHECK (quantity > 0),
    PRIMARY KEY (quest_id, item_id),
    FOREIGN KEY (quest_id) REFERENCES quests(quest_id),
    FOREIGN KEY (item_id) REFERENCES items(item_id)
);

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 adventurer_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 means intentionally maintaining additional representations after understanding data dependencies, it does not mean abandoning normalization entirely.

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.