SQL: normalization removes repeated facts

Split a table that repeats a customer's city on every row into two tables and see why one update is enough.

CREATE TABLE orders_flat (order_id INTEGER, customer TEXT, city TEXT, item TEXT);
INSERT INTO orders_flat VALUES (1, 'Ada', 'London', 'pen'), (1, 'Ada', 'London', 'book'), (2, 'Bo', 'Paris', 'pen');

CREATE TABLE customer (name TEXT PRIMARY KEY, city TEXT);
INSERT INTO customer SELECT DISTINCT customer, city FROM orders_flat;
CREATE TABLE order_item (order_id INTEGER, customer TEXT REFERENCES customer(name), item TEXT);
INSERT INTO order_item SELECT order_id, customer, item FROM orders_flat;

UPDATE customer SET city = 'Oxford' WHERE name = 'Ada';

SELECT i.order_id, c.name, c.city, i.item
FROM order_item i JOIN customer c ON c.name = i.customer
ORDER BY i.order_id, i.item;

SELECT (SELECT COUNT(*) FROM orders_flat WHERE customer = 'Ada') AS flat_copies,
       (SELECT COUNT(*) FROM customer WHERE name = 'Ada') AS normalized_copies;

1|Ada|Oxford|book
1|Ada|Oxford|pen
2|Bo|Paris|pen
2|1

Explanation

A flat table that mixes facts about several things repeats information. Here every row of an order repeats the customer's city. If the city changes, every row must be updated, and missing one leaves the data inconsistent. This is an update anomaly. Insert and delete anomalies are the same problem in other forms.

Normalization splits the table so that each fact is stored once. The customer's city depends on the customer, not on the order, so it moves into a customer table keyed by name. The order items keep only a reference to the customer. A join rebuilds the original view when needed. This is the idea behind second and third normal form: every non-key column depends on the key, the whole key, and nothing but the key.

—

—

—

1|Ada|Oxford|book
1|Ada|Oxford|pen
2|Bo|Paris|pen

1|Ada|Oxford|book
1|Ada|Oxford|pen
2|Bo|Paris|pen
2|1

Cost and common mistakes

Joins cost O(n + m) with hashing or O(n log m) with an index on the key.

• Normalization trades simpler updates for more joins. Heavy read workloads sometimes denormalize on purpose, accepting the duplication.
• Using a name as the key is fragile because names change and repeat. Real schemas use surrogate ids.
• Changing the flat table's city for only one of Ada's rows would leave contradictory data, which is the anomaly normalization prevents.

Try it yourself

Which fact would you move out of order_item if each item also stored its price from a product list?

Further reading

• SQLite SQL language reference (external)
• SQLite query planner (external)
• Database System Concepts (Silberschatz, Korth, Sudarshan) (external)