Normal forms: the key, the whole key, nothing but the key

One fact, one place: what normalization is for

Start with the table itself. The highlighted cells below are not errors. Each of them repeats a fact that an earlier row already stated.

"Value Furniture is at Plano, TX" is stored three times, once per line of its order. "Product 4 is a Natural Maple Entertainment Center at 650.00" is stored twice, once per order that contains it. None of these copies is wrong today. Each copy is a place where the table can become wrong tomorrow.

The slides define the cure on p. 120:

The two steps are different in kind. The first makes the data a relation at all: one value per cell, a key per row. That is first normal form, section 3. The second splits tables so that each fact is stored once, guided by rules called functional dependencies. That gives second and third normal form, section 4.

The goal, printed in bold on p. 121, is "to create a set of relational tables that are free of redundant data and that can be consistently and correctly modified or updated", and the slide draws the consequence: "all tables in a relational database should be in the third normal form (3NF)". Page 127 lists the same goals as two bullets — "Eliminate redundant data" and "Ensure data dependencies make sense (only storing related data in a table)" — and adds the benefits: less space, data "logically stored and easy to maintain".

What goes wrong in an unnormalized table has standard names in the textbooks; the slides describe the goal and leave the names out. They are the three troubles of the puzzle:

• update anomaly — one fact sits in several rows, so changing it means changing every copy. Value Furniture moves: three cells, and a forgotten one leaves two addresses for one customer.
• insertion anomaly — a fact cannot be stored without an unrelated one. A product nobody ordered needs an Order_ID, which is part of the primary key and cannot be NULL.
• deletion anomaly — deleting one fact deletes another. Cancelling the line (1007, 11) erases the only record that product 11 exists.

Page 122 compresses third normal form into one sentence: "A relational table is in 3NF if and only if all non-key columns are: Mutually independent and Fully dependent upon the primary key", and calls 1NF and 2NF "intermediate steps to achieve the goal of having all tables in 3NF". A mnemonic that is not on the slides, usually credited to William Kent (1983), says the same thing in three steps: every non-key column depends on the key, the whole key, and nothing but the key. The first phrase is 1NF, the second 2NF, the third 3NF, and the rest of this lesson unpacks them in that order.

Normalization stores each fact once: every non-key column depends on the key, the whole key, and nothing but the key.

Functional dependencies: the rules behind the repetition

Why is "Voyager" stored twice in the table of p. 125? Because Janeway likes two drinks, so she has two rows, and each row carries her address. The slide circles the repeated cells and writes the reason under each: "Because name -> addr".

Page 124 lists the rules behind those repetitions as "Reasonable FD's to assert":

1. name -> addr
2. name -> favdrink
3. drinkLiked -> manf

Page 123 defines the idea:

The slide's definition speaks of single columns, but a determinant can be a set of columns: p. 133 needs "Order_ID, Product_ID" on the left of an arrow. For sets, the definition is a statement about pairs of rows:

Two consequences matter for everything that follows. First, keys: "If column X is a primary key, then all columns in the relational table R must be functionally dependent upon X" (p. 123). A key value picks out one row, hence one value of every column. Turned around, a set of columns that determines every column is a superkey, and a minimal superkey is what p. 95 calls a key (lesson 8). Textbooks say candidate key, because a table can have several; the primary key is the one the designer picks.

Second, the words "at any given time". A functional dependency is a rule about every legal state of the table, asserted from what the data means — a drinker has one address, a drink has one maker. That is why p. 124 says "reasonable FD's to assert". Rows can refute a rule: one pair that agrees on X and differs on Y is enough. Rows can never prove one. Pine Valley's five rows satisfy 28 single-column dependencies that do not follow from the rules of p. 133 — Unit_Price → Product_ID among them, although nothing stops two products from costing the same.

The table also shows why dependencies produce repetition. name is not the key of Drinkers — Janeway has two rows — so whatever name determines is copied into each of her rows. A determinant that is not a key of its table is the source of every copy in this lesson.

Following the rules: the closure

Page 126, "Basic Idea", is the rule for splitting tables: "To know what FD's hold in a projection, we start with given FD's and find all FD's that follow from given ones. Then, restrict to those FD's that involve only attributes of the projected schema." The slides do not say how to "find all FD's that follow". The standard tool is the attribute closure \(X^+\): start from X and keep adding the right side of every dependency whose left side is already inside, until nothing changes. Then

and X is a superkey exactly when \(X^+\) contains every column. Here is the closure of {name, drinkLiked} under the three rules of p. 124:

1. Start from the set itself — every set of columns determines itself: {name, drinkLiked}.

2. name is inside and name → addr: add addr. Now {name, drinkLiked, addr}.

3. name → favDrink fires as well: add favDrink. Now {name, drinkLiked, addr, favDrink}.

4. drinkLiked is inside and drinkLiked → manf: add manf. All five columns are in, so no rule can add anything: stop.

5. Conclusion: {name, drinkLiked} is a superkey. It is also minimal, since the closure of {name} is {name, addr, favDrink} and the closure of {drinkLiked} is {drinkLiked, manf}. So {name, drinkLiked} is the key of Drinkers.

Now the projection rule works. Split Drinkers into (name, addr, favDrink), (drinkLiked, manf) and (name, drinkLiked). The dependencies that hold in each piece are those of the closure that use only its columns: name → addr, favDrink in the first, drinkLiked → manf in the second, and only trivial ones in the third, whose key is the pair itself. Section 4 explains why this is the right split: name → addr hangs on half of the key.

1NF: first, be a relation

Before the invoice of p. 130 there is the invoice of p. 129, titled "Multivalued attributes". It is the same two orders written the way a paper invoice looks: order 1006 appears once, with three product lines stacked inside it. Fig. 1 shows three of its ten columns before and after.

Page 128 states the rules of the first normal form:

• "Eliminate duplicative columns from the same table" — no Product1, Product2, Product3 laid out side by side;
• "No multivalued attributes", "Every attribute value is atomic (i.e. no sets of values within a column)" — no list inside a cell, as on the left of Fig. 1;
• "Create separate tables for each group of related data and identify each row with a unique column or set of columns (the primary key)."

The last line of p. 128 explains the red verdict of p. 129: "All relations are in 1st Normal Form". A relation is a set of tuples that take one value from each domain (lesson 8), so a table with a set inside a cell is not in 1NF, and therefore "NOT a relation" at all. 1NF is not a quality grade. It is the entry ticket to the relational model.

It is also all that p. 130 has. The flat invoice is a legal relation with a legal key, and it still holds the 15 copies of section 1. Removing repeating groups removes nested lists, not repeated facts. That second job needs the dependencies.

Keep Fig. 1 in mind for later. A MongoDB order document with an embedded array of its lines is the left-hand picture, written on purpose: document stores give up 1NF deliberately (lesson 13).

2NF and 3NF: the whole key, and nothing but the key

Page 133 draws the dependencies of the 1NF invoice over its ten columns and lists them in red:

• Order_ID → Order_Date, Customer_ID, Customer_Name, Customer_Address
• Customer_ID → Customer_Name, Customer_Address
• Product_ID → Product_Description, Product_Finish, Unit_Price
• Order_ID, Product_ID → Order_Quantity

and concludes in blue: "Therefore, NOT in 2nd Normal Form". The key is the pair (Order_ID, Product_ID). Look at where each arrow starts: at the whole key, at half of it, or at a column outside it. That one question sorts every dependency into three kinds.

The two normal forms forbid one kind each. Second normal form, p. 132: "1NF PLUS every non-key attribute is fully functionally dependent on the ENTIRE primary key" — "No partial functional dependencies". Page 131 adds that 2NF "deals with relationships between composite key columns and non-key columns". So a table whose key is a single column is in 2NF as soon as it is in 1NF: there is no "part of the key" for a column to hang on. (The fine print for a table with a second, composite candidate key is in section 5.)

Third normal form, p. 136: "2NF plus no transitive dependencies (functional dependencies on non-primary-key attributes)". The slide explains the name: "this is called transitive, because the primary key is a determinant for another attribute, which in turn is a determinant for a third". Page 135 says it shorter: 3NF "requires that all columns depend directly on the primary key".

The repair is the same both times. Page 131 moves the offending columns into new tables and says how to tie them back: "Create relationships between these new tables and their predecessors through the use of foreign keys"; p. 136 spells the recipe out for 3NF: "non-key determinant with transitive dependencies go into a new table; non-key determinant becomes primary key in the new table and stays as foreign key in the old table". Read the same sentence with "part of the key" in place of "non-key determinant" and you have the 2NF step.

Each arrow that does not start at the whole key becomes a table of its own: its determinant is the new key and stays behind as a foreign key.

Run the recipe on the invoice yourself. Draw the dependencies of the 1NF table, then let the widget split it as pp. 134 and 137 do, and test the three anomalies at each step.

The result is the slides' two pictures. After the first split, p. 134 shows ORDER_LINE (3NF), PRODUCT (3NF) and CUSTOMER_ORDER (2NF), with the caption "Partial Dependencies are removed, but there are still transitive dependencies". After the second, p. 137 shows ORDER (3NF), whose Customer_ID has a dashed underline, and CUSTOMER (3NF): "Transitive dependencies are removed". Four tables, every fact once:

• ORDER_LINE(Order_ID*, Product_ID*, Ordered_Quantity)
• PRODUCT(Product_ID, Product_Description, Product_Finish, Unit_Price)
• ORDER(Order_ID, Order_Date, Customer_ID*)
• CUSTOMER(Customer_ID, Customer_Name, Customer_Address)

Underlined columns are primary keys; a star marks a foreign key, as in the mapping slides of lesson 8.

The slides' second 3NF example, on p. 135, is a publisher with its address:

BCNF and the ladder: where the course stops

Page 138 draws normalization as a ladder. Each rung is the one above with one more kind of trouble removed, so the forms nest: every BCNF table is in 3NF, every 3NF table in 2NF, every 2NF table in 1NF.

The rung the course does cover last is defined on p. 139: "Boyce–Codd normal form (or BCNF or 3.5NF) is a slightly stronger version of the 3NF."

In words: in BCNF every determinant is a superkey. That is "nothing but the key" applied to every arrow, without exceptions. Check it on the four Pine Valley tables: each has one arrow, starting at its own key, so all four are in BCNF as well as in 3NF.

Where does "slightly" come from? The general textbook definition of 3NF has an escape clause: for every non-trivial X → A, either X is a superkey or A belongs to some candidate key. BCNF drops the clause. The two differ only in tables with two or more candidate keys that overlap — none of the slides' examples. The standard one, from the textbooks, is a small teaching table:

Teacher → Course holds, and Teacher is not a superkey: BCNF fails, and the repetition is real. Yet Course is part of the candidate key (Student, Course), so the escape clause saves 3NF. Splitting into TEACHES(Teacher, Course) and FOLLOWS(Student, Teacher) removes the repetition, but the rule "one teacher per student per course" can no longer be checked inside a single table. Insert (Anna, Verdi) into FOLLOWS: both tables accept it, and only their join reveals that Anna now has two Databases teachers. That is why textbooks name 3NF, always reachable without losing a dependency, as the practical target — the target p. 121 sets.

The last two rungs leave functional dependencies behind. Fourth normal form removes multivalued dependencies: two independent lists stored in one table, such as an employee's skills and languages, which force every skill to be paired with every language. Fifth normal form handles the rarer tables that can be rebuilt without loss only by joining three or more of their projections. Neither can be stated with the arrows of this lesson, and the course stops at "3.5" (p. 120).

Two routes to the same tables — and why NoSQL leaves them

Back to the puzzle. What was wrong with five rows that contained no wrong value? Their structure: facts about three different things — orders, customers, products — shared one row, glued together by arrows that did not start at the whole key. Each trouble traces back to an arrow. The three-cell move: the address hangs on Order_ID, half of the key, through Customer_ID, a non-key column — the 2NF split cut it to one copy per order, the 3NF split to one per customer. The product that could not be added and the dresser that vanished with its order line: both hang on Product_ID, the other half of the key, and PRODUCT cured both at once. Every arrow became a table, and every fact now sits in one cell.

There was a second route to the same place. Draw the ER diagram behind the invoice and translate it with the recipe of lesson 8, and the four tables appear directly, with no table ever holding a repeated fact.

So the two halves of the deck meet. A correct ER diagram, translated by the rules, gives 3NF tables. Normalization is the check, and the repair, for tables that did not come from a good diagram: a spreadsheet, a CSV export, or the Employee table of p. 117 with its DeptName repeated on every employee (lesson 8).

The split has a price, and you pay it on every read. To see one invoice line again, the database must join the four tables back together:

-- returns the five invoice lines of p. 130
-- ("ORDER" is quoted: ORDER is an SQL keyword)
SELECT l.Order_ID, o.Order_Date, c.Customer_Name, c.Customer_Address,
       p.Product_Description, p.Unit_Price, l.Ordered_Quantity
FROM ORDER_LINE l
JOIN "ORDER" o  ON o.Order_ID = l.Order_ID
JOIN CUSTOMER c ON c.Customer_ID = o.Customer_ID
JOIN PRODUCT p  ON p.Product_ID = l.Product_ID;

The result is a wide table like the data frames statistical models are fitted on: one row per observation, with every fact repeated where it applies. On one machine three joins are cheap. Across a cluster, where ORDER_LINE and CUSTOMER may live on different nodes, every join is network traffic (lesson 3, lesson 5). That is the main reason the NoSQL half of the course denormalises on purpose. MongoDB embeds the lines inside the order document — the left side of Fig. 1, chosen deliberately (lesson 13). Cassandra builds one table per query and copies the same data into each of them (lessons 20 and 21); the Cassandra exercise session sums it up on p. 1551: "No joins or foreign keys. Data is denormalized and duplicated for query efficiency." Those systems accept the update anomaly in exchange for reads without joins.

The normal forms do not stop being useful there. They are the yardstick that tells you exactly which anomalies you bought, and which application code must now keep the copies in step.