Advanced Normal Forms

Third normal form focuses on non-key attributes: it requires that they depend neither on part of a key nor on another non-key attribute. But what if the right side of a dependency is part of a key? By definition that attribute is not a non-key attribute, so third normal form is not considered violated — yet the same fact keeps repeating across multiple rows. This lesson’s question is: how is this gap closed, and what does closing it cost?

Boyce–Codd Normal Form

Boyce–Codd normal form sets a single, stricter condition: the left side of every non-trivial functional dependency must be a superkey. The “non-key attribute” exemption of third normal form is removed; whatever the attribute, the set that determines it must be a key.

The two definitions diverge exactly where candidate keys overlap. Consider the relation that records which shelf a book stands on in the library. The rule is: a book stands on a single shelf within each branch, and each shelf belongs to a single branch. Two candidate keys follow from this — (isbn, branch_code) and (isbn, shelf) — along with a dependency: shelf → branch_code.

This relation is in third normal form: branch_code is not counted as a non-key attribute because it is part of a candidate key. But shelf is not a superkey, so it violates the Boyce–Codd condition. The result is an inconsistency the schema cannot enforce:

sqlite3 :memory: <<'SQL'
.headers on
.mode box
CREATE TABLE placement (
  isbn        TEXT NOT NULL,
  branch_code TEXT NOT NULL,
  shelf       TEXT NOT NULL,
  PRIMARY KEY (isbn, branch_code),
  UNIQUE (isbn, shelf)
);
INSERT INTO placement VALUES ('975-01', 'CEN', 'R12'),
                            ('975-02', 'CEN', 'R12'),
                            ('975-03', 'BHC', 'R07');
INSERT INTO placement VALUES ('975-04', 'BHC', 'R12');
SELECT shelf, COUNT(DISTINCT branch_code) AS distinct_branches FROM placement GROUP BY shelf;
SQL

┌───────┬───────────────────┐
│ shelf │ distinct_branches │
├───────┼───────────────────┤
│ R07   │ 1                 │
│ R12   │ 2                 │
└───────┴───────────────────┘

Both candidate keys are written into the schema and neither has been violated; even so, shelf R12 appears in two separate branches. Because the left side of the dependency shelf → branch_code is not a key, that rule cannot be written into the schema — the engine has no way of knowing about it. And the shelf’s branch is rewritten for every book placed on that shelf — repetition continues.

Decomposition and the Loss of Dependency Preservation

Boyce–Codd decomposition makes the left side of the offending dependency the key of a new relation: shelf(shelf, branch_code) and book_shelf(isbn, shelf).

sqlite3 :memory: <<'SQL'
.headers on
.mode box
PRAGMA foreign_keys = ON;
CREATE TABLE shelf (shelf TEXT PRIMARY KEY NOT NULL, branch_code TEXT NOT NULL);
CREATE TABLE book_shelf (
  isbn  TEXT NOT NULL,
  shelf TEXT NOT NULL REFERENCES shelf (shelf),
  PRIMARY KEY (isbn, shelf)
);
INSERT INTO shelf VALUES ('R12', 'CEN'), ('R07', 'BHC'), ('R21', 'CEN');
INSERT INTO book_shelf VALUES ('975-01', 'R12'), ('975-02', 'R12'), ('975-03', 'R07');
INSERT INTO book_shelf VALUES ('975-01', 'R21');
SELECT (SELECT COUNT(DISTINCT branch_code) FROM shelf WHERE shelf = 'R12') AS r12_branches,
       (SELECT COUNT(*) FROM book_shelf b JOIN shelf s ON s.shelf = b.shelf
         WHERE b.isbn = '975-01' AND s.branch_code = 'CEN')                AS book975_01_mrk;
SQL

┌──────────────┬────────────────┐
│ r12_branches │ book975_01_mrk │
├──────────────┼────────────────┤
│ 1            │ 2              │
└──────────────┴────────────────┘

The first column shows the gain: the shelf now belongs to a single branch, and this rule is enforced by a key. The second column shows the cost: book 975-01 now stands on two separate shelves in the Central branch. Before decomposition this row could not have been written, because (isbn, branch_code) was the key.

What was lost is the dependency (isbn, branch_code) → shelf. This dependency can no longer be expressed in either relation; testing it requires joining the two together. This is called loss of dependency preservation, and it is the known limitation of Boyce–Codd normal form: every relation can be decomposed losslessly into Boyce–Codd form, but preserving dependency while doing so is not always possible.

The decision is left to the designer at this point. The choice depends on which rule matters more to enforce in the schema: that a shelf belongs to a single branch, or that a book stands on a single shelf per branch. Staying in third normal form to preserve the second rule is also a valid decision — normal forms are not a ladder but a list of trade-offs.

Multivalued Dependency

Boyce–Codd normal form exhausts functional dependencies, but they are not the only source of repetition. If a member has several interests and several phone numbers, and the two sets are independent of each other, holding all three in a single relation produces a Cartesian product. This is called a multivalued dependency.

The relation is in Boyce–Codd form — the key consists of every attribute, so no non-trivial functional dependency exists. Yet every new phone number requires adding as many rows as the member has interests:

sqlite3 :memory: <<'SQL'
.headers on
.mode box
CREATE TABLE member_combined (member_no INTEGER, interest TEXT, phone TEXT,
                           PRIMARY KEY (member_no, interest, phone));
INSERT INTO member_combined VALUES
  (41, 'history', '0312-555-0101'), (41, 'history', '0312-555-0102'),
  (41, 'history', '0312-555-0103'), (41, 'poetry',  '0312-555-0101'),
  (41, 'poetry',  '0312-555-0102'), (41, 'poetry',  '0312-555-0103');

CREATE TABLE member_interest (member_no INTEGER, interest TEXT,    PRIMARY KEY (member_no, interest));
CREATE TABLE member_phone (member_no INTEGER, phone TEXT, PRIMARY KEY (member_no, phone));
INSERT INTO member_interest VALUES (41, 'history'), (41, 'poetry');
INSERT INTO member_phone VALUES (41, '0312-555-0101'), (41, '0312-555-0102'),
                               (41, '0312-555-0103');

INSERT INTO member_interest     VALUES (41, 'travel');
INSERT INTO member_combined VALUES (41, 'travel', '0312-555-0101');

SELECT (SELECT COUNT(*) FROM member_combined) AS combined_rows,
       (SELECT COUNT(*) FROM member_interest) + (SELECT COUNT(*) FROM member_phone) AS separate_rows,
       (SELECT COUNT(*) FROM member_interest i JOIN member_phone p USING (member_no)) AS joined;
SQL

┌───────────────┬───────────────┬────────┐
│ combined_rows │ separate_rows │ joined │
├───────────────┼───────────────┼────────┤
│ 7             │ 6             │ 9      │
└───────────────┴───────────────┴────────┘

When the third interest was added, a single row was written, and the combined relation stayed at seven rows; for consistency it should have had nine. A silent inconsistency was created: the member with the travel interest appears to have only one phone number. The separate relations held six rows in total, and the join correctly produced nine. The difference is that the row count grows as $m + n$ rather than $m \times n$.

Fourth normal form requires the left side of every non-trivial multivalued dependency to be a superkey. Its practical counterpart is a plain rule: two independent multivalued facts are not held in the same relation.

Further Forms

Fifth normal form deals with cases where a relation can only be decomposed losslessly into three or more parts rather than two; the constraint that produces this case is called a join dependency. It is rare in real schemas and typically arises when a three-way relationship actually consists of three pairwise relationships.

Domain-key normal form states the criterion in its most general form: every constraint on the relation must be derivable solely from domain definitions and keys. A relation that satisfies this condition can have no update anomaly. It is valuable as a theoretical goal; it is not reachable for every relation, and whether it has been reached cannot be tested in general.

Where to Stop

In practice, most designs stop at third normal form or Boyce–Codd form. The deciding criterion is not the number of the form but two questions: which anomalies can actually arise, and can the constraint that prevents them be written into the schema?

The order to follow is also fixed. First, the rules of the domain — that is, the functional and multivalued dependencies — are written down. Then the candidate keys are found through closure computation. Then dependencies whose left side is not a key are sought out; each one turns into either a decomposition or a deliberate exception. The exception decision must remain in writing, because to the next designer that structure will look like a mistake.

Summary

• Boyce–Codd normal form requires the left side of every non-trivial dependency to be a superkey; it removes the non-key exemption found in third normal form.
• The two forms diverge only in relations where candidate keys overlap; a schema left in third normal form can harbor a dependency that cannot be enforced.
• Every relation can be decomposed losslessly into Boyce–Codd form, but dependency preservation cannot always be achieved; which rule gets enforced in the schema is a design decision.
• When two independent multivalued facts are held in the same relation, the row count grows multiplicatively and a missing row produces a silent inconsistency; fourth normal form separates them.
• Normal forms are not a ladder but a list of trade-offs; the stopping point is chosen according to the anomalies that can actually arise.

Next Step

Every step so far has moved in the same direction: remove repetition, split the relation, enforce the rule in the schema. This has an unpaid cost — every split relation must be joined back together at read time. The next lesson measures this cost and takes up the opposite decision: under what condition is deliberately putting repetition back defensible, and what write cost is taken on in exchange?