CSE Roadmap

Core tier · about 3 hours · 8 parts

Part 3 of 8 · 4 min read

The relational model

Tables, keys and joins, why data is split across tables, and the cost of that split.

Think of a spreadsheet workbook with several sheets. A sheet of customers, a sheet of orders. An order does not repeat the customer's address. It holds the customer's number, and anyone who needs the address looks it up in the customers sheet.

That is the relational model, proposed by Edgar Codd in 1970 according to the book. Data is stored in relations, called tables in SQL. Each table is a collection of rows, and every row has the same columns. For a long time it has been the standard way to store business data.

Table, row, column, key

A table holds rows of one kind. A row is one record. A column is one named field. A primary key is a column (or set of columns) whose value is unique for each row. A foreign key is a column that holds the primary key of a row in another table.

Example: in the table orders, the column customer_id is a foreign key that points to a row of the table customers.

SQL and join

SQL is the query language of relational databases. A join combines rows from two tables by matching a foreign key to a primary key.

Example: a join of orders and customers on customer_id returns each order together with the customer's name.

A worked example. A bookshop has these tables.

customers

id name city
1 Asha Pune
2 Ravi Delhi

orders

id customer_id book price
101 1 Dune 400
102 1 Emma 250
103 2 Dune 400

The question "who bought Dune, and from which city?" joins orders to customers: orders 101 and 103 point to customers 1 and 2, so the answer is Asha (Pune) and Ravi (Delhi).

Why split the data this way? Because of a habit called normalization.

Normalization

Normalization means storing each fact in one place only, and pointing to it from everywhere else. Denormalization means copying a fact into several places on purpose.

Example: storing the city name once in the customers table is normalized. Copying it into every order row is denormalized.

The book gives the reasons to store an identifier instead of the text. The human-readable value lives in one place. If it changes, one update fixes it, and no copy can be left with the old value. An identifier has no meaning to people, so it never needs to change.

A worked example of the cost of copies. Asha has 5 orders. Suppose each order row stores her city, and she moves to Mumbai.

  • Denormalized: 5 rows must be updated. If the program crashes after 3, two orders say Pune and three say Mumbai.
  • Normalized: 1 row of customers is updated. All 5 orders now show Mumbai through the join.

Normalization is cheap to write and safe. Its cost is paid on read, since the join must be done at query time. Denormalization reverses the trade: reads are faster, writes are more work and risk disagreement. Part III of the book returns to this trade (Levels 3 and 6).

The book also describes what made this model win. The older models needed programmers to follow paths of pointers by hand. A relational database has a query optimizer, a part that chooses how to run a query, which indexes to use and in what order. The programmer states what is wanted, not how to fetch it. If a new index is added, queries use it automatically. This makes it easy to ask new questions later.

Schema

A schema is the declared structure of the data: the tables, columns and types. In schema-on-write, the database checks every write against the schema.

Example: the column price is declared as a number, so the database refuses a write of the text "free".

Relational databases are the safe default in interviews. The book notes that they generalised well beyond business data to publishing, social networks, shops, games and many other uses.

Common mistake

Saying "relational does not scale". It scales a long way, and Level 4 shows how. The honest statement is that scaling a relational database across many machines is harder, because joins and strict rules are harder to spread.

Check yourself:

  • In the example, how many rows change when a customer moves, with and without normalization?
  • What does the query optimizer do for the programmer?