Foundations · Lesson 2/8

Data Modeling & Normalization

45 min 1 quiz Graded labs: 3

The school register with the teacher's phone on every card 🏫

A school keeps one paper card per student. On each card the clerk writes the student's name, the course, and the teacher's phone number. It works until the teacher changes number. Now the clerk must find and fix 140 cards. Miss three, and the school holds two different "truths" about the same teacher.

The fix is old and simple: write the teacher's phone once, on a teacher card, and let student cards point to the teacher. That idea is normalization: store every fact in exactly one place.

What you'll learn

Turning a real-world story into entities, attributes and relationships
One-to-one, one-to-many and many-to-many relationships, and the junction table
The three anomalies that a bad design causes
1NF, 2NF and 3NF in plain language ("the key, the whole key, and nothing but the key")
When breaking the rules on purpose (denormalization) is the right call
How the same modeling question looks in a document store

Step 1: find the nouns and the verbs

Read the requirements out loud and underline the nouns: customers place orders that contain products. Each noun that has facts of its own becomes an entity, which becomes a table. The facts become attributes, which become columns. The verbs become relationships.

customers 1 ────< orders >──── order_lines ────< products   (crow's feet mean "many")
   one customer places many orders; one order has many lines; each line is one product

One-to-many (1:N): the most common. Put a foreign key on the "many" side: orders.customer_id points to customers.id.
One-to-one (1:1): rare. Usually it is one table split for privacy or size (e.g. users and user_private_details), with the key shared.
Many-to-many (N:M): students take many courses and a course has many students. A single foreign key cannot express it. You need a third table, a junction (or "bridge") table, with one row per pair and two foreign keys. The pair is usually its primary key.

Why a wide table goes wrong: three anomalies

Imagine one wide table, sales_flat, with one row per order line and the customer, city and product price copied onto every row.

Update anomaly: Amal moves to Giza. She has 3 rows, and you must change all of them. Change two and the database now says she lives in two cities.
Insert anomaly: you want to add a new product to the catalog, but it has not been sold yet. There is no row to put it on, because rows only exist for sales.
Delete anomaly: Carla's only order is cancelled and you delete the row. You also lost the fact that Carla exists and lives in Beirut.

All three come from the same disease: one table mixes several independent facts.

The normal forms, without the jargon

Think of three increasingly strict questions you ask about every column.

1NF: one value per cell. No lists in a cell (phones = '0100,0111') and no repeating columns (phone1, phone2, phone3). Each row has the same shape and a primary key.
2NF: depend on the whole key. If the key has two columns, say (order_id, product_id), every other column must depend on both. customer depends on order_id alone, so it belongs in an orders table. (2NF only matters when the key is composite.)
3NF: depend on nothing but the key. A column must not depend on another non-key column. In employees(id, name, dept_id, dept_name), dept_name depends on dept_id, not on the employee, so it moves to departments.

The classic summary: every column depends on the key, the whole key, and nothing but the key. For most application schemas, 3NF is the goal. (BCNF is a slightly stricter version of 3NF, rarely a practical concern at this level.)

Keys you will choose

A surrogate key (id INTEGER PRIMARY KEY) has no meaning outside the database and never needs to change. A natural key (an email, a country code) carries meaning, which means it can change. Most tables use a surrogate primary key, and add UNIQUE on the natural key.
Name things consistently: singular or plural table names (pick one), <table>_id for foreign keys.
Do not store what you can compute (a person's age instead of their birth date, an order total that can drift from its lines), unless you do it on purpose (see below).

Denormalization: breaking the rules with open eyes

Joins cost time, and sometimes a copy is the right design:

History must not change. An order line must keep the price at the time of purchase. If it only pointed to products.price, raising the price would silently rewrite last year's invoices. The copied price is not redundancy, it is a different fact.
Read-heavy reporting tables or cached counters (comments_count) trade write complexity for fast reads.

The rule: normalize first, denormalize only for a measured need, and write down who keeps the copy consistent (a trigger, a job, application code).

Your turn: split the wide table

In the lab, sales_flat already holds the data and the four target tables exist and are empty. You fill them with INSERT ... SELECT. This statement copies the result of a query into a table:

INSERT INTO customers (name, city)
SELECT DISTINCT customer, city FROM sales_flat;   -- DISTINCT removes duplicate rows

For orders and order_lines you must look up the new id of the customer or product. A JOIN matches rows of two tables on a condition. The next lesson studies joins in depth; here is the shape you need:

SELECT f.order_id, c.id
FROM sales_flat f
JOIN customers c ON c.name = f.customer;   -- pair each flat row with its customer row

Design A can contradict itself because the same fact is stored three times. Design B has one place to update, so it cannot disagree with itself. That single place is what a foreign key plus a JOIN gives you in SQL.

# The update anomaly in miniature.
# Design A: the teacher's phone is copied onto every student card.
cards = [
    {"student": "Amal", "teacher": "Mr. Samir", "teacher_phone": "0100"},
    {"student": "Bilal", "teacher": "Mr. Samir", "teacher_phone": "0100"},
    {"student": "Carla", "teacher": "Mr. Samir", "teacher_phone": "0100"},
]

# Mr. Samir changes number, but the clerk only fixes two cards.
cards[0]["teacher_phone"] = "0111"
cards[1]["teacher_phone"] = "0111"

phones = {c["teacher_phone"] for c in cards if c["teacher"] == "Mr. Samir"}
print("Design A phones for Mr. Samir:", sorted(phones))  # two truths!

# Design B: the phone lives once, on the teacher record.
teachers = {"Mr. Samir": {"phone": "0100"}}
students = [
    {"student": "Amal", "teacher": "Mr. Samir"},
    {"student": "Bilal", "teacher": "Mr. Samir"},
    {"student": "Carla", "teacher": "Mr. Samir"},
]
teachers["Mr. Samir"]["phone"] = "0111"  # one change
for s in students:
    print("Design B:", s["student"], "->", teachers[s["teacher"]]["phone"])

Open in Code Lab

Lab exercise 1

PythonGraded in Code Lab

Normalize sales_flat (one row per order line, everything copied) into four tables that already exist but are empty:

customers (id, name, city): one row per distinct customer
products (id, name, price_cents): one row per distinct product
orders (id, customer_id): one row per order, keeping the original order_id as id
order_lines (order_id, product_id, qty): one row per line

Write four INSERT ... SELECT statements (in this order, because of the foreign keys). The program then prints the row counts, applies price changes read from stdin (<product> <new price in cents>) and prints the value of all lines at current prices, computed through a JOIN.

Output: counts, one price of X: N row changed line per input line, then value at current prices: V.

Example: with correct inserts and empty input, the counts are customers: 4, products: 3, orders: 6, order_lines: 8.

Visible tests (4)

Row counts after normalizing
One price change touches one row but changes every order
Several price changes
Unknown product changes nothing

Example run

Input: (no input)
Expected output: customers: 4 products: 3 orders: 6 order_lines: 8 value at current prices: 135.25

Starter code

import sqlite3
import sys

db = sqlite3.connect(":memory:")
db.execute("PRAGMA foreign_keys = ON")

# One wide table: everything about an order line, copied on every row.
db.execute("""
    CREATE TABLE sales_flat (
        order_id    INTEGER NOT NULL,
        customer    TEXT    NOT NULL,
        city        TEXT    NOT NULL,

More lines in Code Lab: 73

Try in Code Lab

Hints and instant feedback are in Code Lab. Optional practice: it does not block finishing the lesson.

JavaScript and Python also run in your browser without an account; other languages use the secure server runner and need a free account.

Lab exercise 2

PythonGraded in Code Lab

Students take many courses and courses have many students: a many-to-many relationship. students and courses already exist. Create the junction table enrollments:

two columns, student_id and course_id, both INTEGER NOT NULL
the pair (student_id, course_id) is the primary key (a student cannot join the same course twice)
both columns are foreign keys (to students(id) and courses(id))

The program (foreign keys are switched on for you) tries to enroll every student_id course_id pair from stdin, prints OK or REJECTED ... - KIND, then prints how many students each course has.

Example: the pairs 1 10 and 1 10 give OK 1 10 and REJECTED 1 10 - UNIQUE.

Visible tests (4)

Valid enrollments and the roster
The same pair twice is rejected
Unknown student or course is rejected
No input: every course is empty

Example run

Input: 1 10 1 20 2 10
Expected output: OK 1 10 OK 1 20 OK 2 10 Algebra: 2 Biology: 1 Chemistry: 0

Starter code

import sqlite3
import sys

db = sqlite3.connect(":memory:")
db.execute("PRAGMA foreign_keys = ON")  # SQLite enforces foreign keys only when asked

db.executescript("""
    CREATE TABLE students (id INTEGER PRIMARY KEY, name TEXT NOT NULL);
    CREATE TABLE courses  (id INTEGER PRIMARY KEY, title TEXT NOT NULL);
    INSERT INTO students (id, name) VALUES (1, 'Amal'), (2, 'Bilal'), (3, 'Carla');
    INSERT INTO courses  (id, title) VALUES (10, 'Algebra'), (20, 'Biology'), (30, 'Chemistry');
""")

More lines in Code Lab: 27

Try in Code Lab

Hints and instant feedback are in Code Lab. Optional practice: it does not block finishing the lesson.

JavaScript and Python also run in your browser without an account; other languages use the secure server runner and need a free account.

The same question in a document store

A document database (MongoDB, Firestore, ...) stores JSON-like documents instead of table rows. There are no joins to lean on, so the modeling question becomes: embed or reference?

{ "id": 101, "total": 2500,
  "customer": { "id": 1, "name": "Amal", "city": "Cairo" } }   // embedded: one read, but copied

{ "id": 101, "total": 2500, "customerId": 1 }                   // referenced: small, needs a 2nd lookup

Embed when the child data is always read together with the parent, belongs to it alone and stays small (an order's address, a post's comments up to a limit). One read returns everything.
Reference when the data is shared, grows without bound, or changes independently (a customer who has thousands of orders). Updating a customer's city then touches one document.

It is the same trade-off as before: copies make reads simple and updates dangerous. In the lab you do by hand what a migration from embedded to referenced documents does, in JavaScript.

References keep one copy of each customer, so a single change shows up in every order. The price is an extra lookup on every read, which is why embedding is attractive when the data never changes independently.

// "Populate": resolving references yourself, the job a JOIN does in SQL.
const customers = new Map([
  [1, { id: 1, name: "Amal", city: "Cairo" }],
  [2, { id: 2, name: "Bilal", city: "Amman" }],
]);
const orders = [
  { id: 101, total: 2500, customerId: 1 },
  { id: 102, total: 900, customerId: 2 },
  { id: 103, total: 4100, customerId: 1 },
];

for (const o of orders) {
  const c = customers.get(o.customerId);
  console.log(`order ${o.id}: ${o.total} cents, ${c.name} from ${c.city}`);
}

// One update, visible everywhere the customer is referenced:
customers.get(1).city = "Giza";
console.log(orders.filter((o) => o.customerId === 1).map((o) => customers.get(o.customerId).city));

Open in Code Lab

Lab exercise 3

JavaScript (Node.js)Graded in Code Lab

Orders arrive as JSON documents with the customer embedded. Write normalize(orders) so it returns { customers, orders }:

customers: one object per distinct customer.id, in order of first appearance. If the same id shows up again with different data, the later copy wins (it is newer) but the customer keeps its original position.
orders: each order as { id, total, customerId } (keys in this order). A guest order has "customer": null and gets customerId: null (no customer is created).

Input: a JSON array of orders on stdin. Output: two lines: JSON.stringify(customers) and JSON.stringify(orders) (the program prints them).

Example: [{"id":7,"total":50,"customer":{"id":1,"name":"Amal","city":"Cairo"}}] prints

[{"id":1,"name":"Amal","city":"Cairo"}]
[{"id":7,"total":50,"customerId":1}]

Visible tests (4)

Shared customers are stored once
Empty input
Guest order has no customer
Stale copy: the later data wins, the position stays

Example run

Input: [{"id":101,"total":2500,"customer":{"id":1,"name":"Amal","city":"Cairo"}},{"id":102,"total":900,"customer":{"id":2,"name":"Bilal","city":"Amman"}},{"id":103,"total":4100,"customer":{"id":1,"name":"Amal","city":"Cairo"}}]
Expected output: [{"id":1,"name":"Amal","city":"Cairo"},{"id":2,"name":"Bilal","city":"Amman"}] [{"id":101,"total":2500,"customerId":1},{"id":102,"total":900,"customerId":2},{"id":103,"total":4100,"customerId":1}]

Starter code

const fs = require("fs");

const input = JSON.parse(fs.readFileSync(0, "utf8"));

function normalize(orders) {
  // TODO: collect unique customers (later copies win, first position kept)
  // and rewrite every order as { id, total, customerId }.
  return { customers: [], orders: [] };
}

const result = normalize(input);
console.log(JSON.stringify(result.customers));

More lines in Code Lab: 1

Try in Code Lab

Hints and instant feedback are in Code Lab. Optional practice: it does not block finishing the lesson.

JavaScript and Python also run in your browser without an account; other languages use the secure server runner and need a free account.

Quick quiz

Question 1 of 5

A wide table repeats each customer's city on every order row. A customer moves and only some of their rows are updated. What is this problem called?

Question 2 of 5

employees(id, name, dept_id, dept_name): which normal form does it break, and how do you fix it?

Question 3 of 5

How do you model a many-to-many relationship such as students and courses?

Question 4 of 5

Which of these is a 1NF violation?

Question 5 of 5

Order lines store the unit price at purchase time, even though products also has a price. Is this a design mistake?

Recap and what to practice next

Model by finding entities (nouns), attributes and relationships; one-to-many puts the foreign key on the "many" side; many-to-many needs a junction table.
A wide table causes update, insert and delete anomalies because it stores many facts together.
1NF one value per cell, 2NF the whole key, 3NF nothing but the key.
Denormalize deliberately, for history or measured speed, and name who keeps the copies in sync.
In document stores the same trade-off appears as embed vs reference.

Practice next: take a spreadsheet you actually use (expenses, a gym schedule, a team roster). List its columns, circle the ones that repeat the same fact on many rows, and sketch the tables you would split it into. Then try writing the CREATE TABLE statements with keys. The next lesson shows how to get the data back together with joins and aggregation.

Practice

Reading is not learning until you run something. Pick one.

Graded lab exercises

Lab exercise 1PythonNot passed yet Try in Code Lab
Lab exercise 2PythonNot passed yet Try in Code Lab
Lab exercise 3JavaScript (Node.js)Not passed yet Try in Code Lab

Open an example in Code Lab

Blank Code Lab in Python

Relational Model & SQL Basics

Next lesson

Joins, Aggregation & Subqueries