How relational databases model data

14 min read · last reviewed 2026-10-17

Open in the interactive app: practice, quiz, mock interview →

In one minute

A relational database stores data as relations (tables of rows with the same columns) and links rows by values, such as a customer_id, never by physical pointers.
Because nothing points at a disk location, the engine is free to choose storage, indexes and join order itself; you declare what you want and a planner decides how.
Keys and constraints (PRIMARY KEY, UNIQUE, FOREIGN KEY, CHECK) make the database the final guard of data integrity, no matter which service or script writes.
Normalization stores each fact once, so updates cannot leave contradictions; joins put the facts back together at read time.
The model's costs are real: joins need memory and good statistics, foreign keys need indexes and locks, and none of it spans shards for free.

How it works

Values, not pointers

Before 1970, databases such as IBM's IMS stored records in hierarchies that programs navigated by following pointers, so changing the storage layout broke every program. Edgar Codd proposed presenting data as mathematical relations: unordered sets of tuples (Codd, 1970). An order refers to its customer by holding the customer's key value, and disk layout and indexes become invisible to the query.

This physical data independence is why SQL can be declarative. A query is an expression in relational algebra (select, project, join, union, difference, aggregate); each operator takes and returns relations, so the planner can rewrite the expression into any equivalent form. Databases 101 shows tables and SQL from the user's side; this lesson looks at what the model asks of the engine.

Keys and constraints

A candidate key is a minimal set of columns that identifies a row; the primary key is the one you pick. Natural keys (an email) carry meaning but change, dragging every reference with them, so most schemas use surrogate keys (sequences, UUIDs) plus UNIQUE on the natural key. Random version 4 UUIDs land at random places in the primary-key B-tree, so every insert touches a cold page. RFC 9562 (2024) added time-ordered version 7 UUIDs partly for this reason (RFC 9562), and Postgres 18 ships a built-in uuidv7() (Postgres 18 release notes).

A foreign key says every non-null orders.customer_id must exist in customers.id, and chooses what happens when the parent is deleted:

NO ACTION (the default) and RESTRICT reject the change if referencing rows remain. NO ACTION checks at the end of the statement (or at commit if deferred), so a statement that also removes the children succeeds; RESTRICT checks immediately.
CASCADE deletes the referencing rows too, recursively.
SET NULL keeps the children but clears the reference; SET DEFAULT sets it to the column default instead. In Postgres, ON DELETE SET NULL (author_id) can clear only some columns of a composite key (Postgres docs). InnoDB rejects SET DEFAULT entirely (MySQL docs).

Engines differ in what they actually enforce, so check rather than assume. MySQL parsed CHECK constraints and silently ignored them before 8.0.16 (MySQL 8.0 docs). Postgres 18 (September 2025) added temporal keys: PRIMARY KEY (room_id, valid_at WITHOUT OVERLAPS) forbids two rows for one room with overlapping time ranges, and a PERIOD foreign key checks that a child's range is covered by its parent's. It also added NOT ENFORCED for CHECK and foreign keys, which records the rule without checking it (Postgres 18 release notes).

Normalization in one example

Take order_lines(order_id, product_id, quantity, product_name, customer_email) keyed by (order_id, product_id). product_name depends on only part of the key (a second normal form violation) and customer_email depends on the order, not the line (third normal form). Rename a product and thousands of lines must change; miss one and the product has two names. Normalizing moves each fact next to its key: products(id, name), orders(id, customer_id), customers(id, email), order_lines(order_id, product_id, quantity). Copying facts back for read speed is the deliberate step covered in Denormalization.

Joins put it back together

Engines have three join algorithms:

Nested loop: for each outer row, probe the inner side, ideally by index. Best for a small outer side.
Hash join: hash the smaller input on the join key, then stream the larger one past it. Best for large equality joins.
Merge join: walk two inputs sorted on the key in lockstep. Best when indexes already supply the order.

NULL and three-valued logic

NULL means unknown, so comparisons with it yield UNKNOWN and WHERE drops the row. WHERE id NOT IN (SELECT manager_id FROM staff) returns nothing if any manager_id is null. Use NOT EXISTS.

The same shape elsewhere

Referential integrity is the multi-step consistency shape: deleting one thing must deal with everything that depends on it. Kubernetes objects carry ownerReferences, and deleting a Deployment cascades in the foreground (children first), in the background (a garbage collector follows), or orphans the children, which is SET NULL by another name.

Down the stack

Layer 1The contract

A result is a multiset of rows with no order unless you write ORDER BY. NOT NULL and CHECK are checked per row; UNIQUE and foreign keys per statement, or at commit if declared DEFERRABLE INITIALLY DEFERRED. A committed state never contains a dangling foreign key, a duplicate key or a failed CHECK; a violation aborts the statement (SQLSTATE 23503 for a foreign key, 23505 for unique), and inside a transaction the transaction must roll back. Cascading actions run inside the same statement, so they are atomic with it.

Layer 2The mechanism

Postgres implements foreign keys as internal constraint triggers. Inserting or updating a child row fires RI_FKey_check_ins or RI_FKey_check_upd, which runs roughly SELECT 1 FROM ONLY parent WHERE id = $1 FOR KEY SHARE. FOR KEY SHARE blocks deleting the parent or changing its key but not updating its other columns. Deleting a parent fires RI_FKey_cascade_del, RI_FKey_setnull_del or a no-action or restrict check, each of which queries the child table by the foreign key column.

The parent key must have a unique index, so the check is one B-tree probe. Postgres does not index the child column automatically, so each parent delete can scan the child table; InnoDB creates that index for you if none exists (MySQL docs). InnoDB's cascaded changes also do not fire triggers on the child table. UNIQUE is enforced by the unique index itself, and an insert that meets an uncommitted duplicate waits to see whether it commits.

A hash join's table is bounded by work_mem (4 MB by default) times hash_mem_multiplier (2.0 by default since Postgres 15) (Postgres docs). If the build side does not fit, Postgres splits both inputs into batches by hash, writes all but the first to temporary files, and joins batch by batch.

Layer 3The machine

A Postgres row lives in an 8 KB heap page, found through a 4-byte line pointer near the start of the page. Each tuple has a 23-byte header (Postgres docs), an optional null bitmap, then column data with each value aligned to its type's boundary. Column order therefore changes row size: (bool, bigint, bool, bigint) takes 32 bytes of data because each bigint must start on an 8-byte boundary, while (bigint, bigint, bool, bool) takes 18. With the header the tuples are 56 and 48 bytes; across 100 million rows that is about 800 MB of heap and cache. Values that push a row past about 2 KB are compressed or moved out of line by TOAST (Postgres docs).

Join memory is where the physical costs show. A hash join whose build side is 2 million rows of about 60 bytes needs roughly 120 MB plus hash overhead; with an 8 MB budget it splits into 16 or more batches and writes and rereads most of both inputs through temp files, turning a sub-second join into several seconds of disk I/O. An indexed nested loop costs a B-tree descent per outer row: a few cached page reads, or about 100 microseconds per page from NVMe.

Why it's built this way

Programs that navigate storage pointers break whenever storage changes, so the model links rows by value and hides the physical layout.
Hidden layout means the engine must decide how to execute queries, so a cost-based planner with statistics sits in the middle of every query.
Many applications and scripts write the same data, so integrity rules live in the database, where no writer can skip them.
A child insert must not race a parent delete, so the check takes a row lock on the parent; that lock is the weak FOR KEY SHARE so that ordinary parent updates are not blocked.
Memory is finite and inputs are not, so joins and sorts degrade gracefully by partitioning and spilling to disk rather than failing.

Diagram

sequenceDiagram
  participant App
  participant Exec as Executor
  participant P as "projects (parent)"
  participant T as "child tables"
  App->>Exec: DELETE FROM projects WHERE id = 7
  Exec->>P: mark row 7 deleted (xmax)
  Exec->>T: RI_FKey_cascade_del: DELETE WHERE project_id = 7
  T-->>Exec: 5,000 rows (index scan, or full scan if unindexed)
  Exec->>T: no-action check on invoices referencing project 7
  T-->>Exec: none left
  Exec-->>App: DELETE 1 (cascade done in same statement)

Worked example

A project-management SaaS has projects (2 million rows), tasks (60 million rows, 7 GB, project_id REFERENCES projects ON DELETE CASCADE) and comments (300 million rows, cascading from tasks, indexed on task_id). Nobody indexed tasks.project_id.

A tenant with 10,000 projects churns. DELETE FROM projects WHERE tenant_id = 99 fires the cascade trigger 10,000 times, each running DELETE FROM tasks WHERE project_id = $1 as a sequential scan of 7 GB. At 2 GB/s that is 3.5 seconds per project, about 10 hours, in one transaction that holds locks and pins its snapshot so VACUUM stalls.

With CREATE INDEX CONCURRENTLY ON tasks(project_id), each cascade is a B-tree descent to about 30 tasks (60 million / 2 million). The whole delete removes about 300,000 tasks and 1.5 million comments: perhaps a minute, still too long for one transaction on a busy primary.

The final design deletes 100 projects per transaction, pausing between batches to keep replication lag under a second. For the largest tenants, a soft delete flag makes the user-facing action one row update, and a purge job runs the cascade off-peak.

In the wild

Figma, 2024: keeping joins and foreign keys inside a shard. After its database stack grew almost 100x from 2020, Figma sharded RDS Postgres horizontally. Tables that share a shard key are grouped into "colos", so joins and transactions within one key keep working, and a Go proxy routes queries and runs limited scatter-gather for the rest. The first table took about 9 months and went live in September 2023 with about 10 seconds of partial unavailability (Figma).
Notion, 2021: sharding by the key every relation already carried. With VACUUM stalling and transaction ID wraparound looming on one Postgres, Notion split data by workspace ID into 480 logical shards on 32 physical databases, chosen because 480 has many divisors. Because every block belongs to exactly one workspace, related rows stay on one shard and most queries avoid cross-shard joins. Dual writes, a 3-day backfill and dark reads checked the copy before a cutover of about 5 minutes (Notion).
GitHub, 2016: schema changes without write-blocking locks. GitHub found trigger-based online migration tools added overhead to every write and fought for metadata locks on busy MySQL tables. Its gh-ost tool instead tails the binary log into a "ghost" table, throttles on replication lag, and postpones cut-over; it was proven by running no-op migrations on production replicas and comparing checksums (GitHub).

Trade-offs

Option	Strengths	Weaknesses	Choose when
Foreign keys in the database	Integrity guaranteed for every writer	Lock and index costs; impossible across shards	One database owns the related tables
References checked in application code	Works across services and shards	Races and bugs leave orphans; needs repair jobs	Data split across services or stores
`ON DELETE CASCADE`	One statement, atomic cleanup	Unbounded fan-out in one transaction	Small, bounded child sets
Soft delete plus async purge	Fast user action, purge paced off-peak	Every query must filter deleted rows	Large tenants, legal retention needs
Surrogate keys	Stable, compact, cheap joins	Need a separate `UNIQUE` on the natural key	Almost always
Natural keys	Readable, no extra lookup	Key changes cascade to every reference	Truly immutable identifiers such as ISO codes

Pitfalls in production

Unindexed foreign key columns. Parent deletes scan the child table. Index every referencing column.
Adding a constraint to a big table. ALTER TABLE ... ADD FOREIGN KEY scans the whole table while holding SHARE ROW EXCLUSIVE locks on both the child and the parent, blocking writes to both. Add it NOT VALID, then run VALIDATE CONSTRAINT, which takes only SHARE UPDATE EXCLUSIVE on the child and ROW SHARE on the parent. Since Postgres 18 the same trick works for NOT NULL (Postgres docs).
NOT IN with nullable columns. One null in the subquery empties the result. Use NOT EXISTS.
Relying on implicit order. Without ORDER BY, order changes with data size, parallelism or a new index, and pagination skips and repeats rows.
Cascades as a hidden fan-out. One delete can touch millions of rows in one transaction. Know your cascade graph and batch large deletes.

Leadership lens

Ask which invariants the schema enforces and which live only in application code; the latter are rules a backfill script or a second service can skip.
Foreign keys and joins work only within one database, so keep tables that reference each other on the same shard key.
Put "index your foreign keys" and "add constraints NOT VALID, then VALIDATE" on the migration review checklist.
Decide deletion policy per entity (cascade, restrict, soft delete with purge) as a product and compliance decision, not an ORM default.

Check yourself

Why can the planner reorder joins freely in a relational database but not in a pointer-navigating one?
Show answer
Relational operators take and return relations and links are values, so equivalent algebra expressions give the same result regardless of order. Pointer navigation fixes the access path in the program.
A DELETE on a parent table with 5,000 rows takes 20 minutes. What is the first thing you check?
Show answer
Whether each referencing column in child tables is indexed. Without an index every per-row foreign key action scans the whole child table.
Why does Postgres lock the parent row FOR KEY SHARE instead of FOR SHARE when checking a child insert?
Show answer
The check only needs the key to stay put. FOR KEY SHARE blocks deletes and key changes but lets other transactions update non-key columns of the parent.
Under what condition does NO ACTION succeed where RESTRICT fails?
Show answer
When the same statement, or with deferral the same transaction, also removes or repoints the referencing rows, because NO ACTION checks at the end rather than immediately.

Sources and further study

Primary

Selinger et al., Access Path Selection in a Relational Database Management System (SIGMOD 1979): the System R paper behind cost-based planning and join ordering.
RFC 9562: Universally Unique IDentifiers (2024): replaces RFC 4122 and defines time-ordered UUIDv7 for better index locality.

Systems docs

PostgreSQL: ALTER TABLE: the lock each subcommand takes, and NOT VALID with VALIDATE CONSTRAINT.
MySQL: FOREIGN KEY constraints: InnoDB's automatic child index, unsupported SET DEFAULT, and cascades that skip triggers.
PostgreSQL 18 release notes: temporal keys, NOT ENFORCED constraints, virtual generated columns and uuidv7().

Books

Designing Data-Intensive Applications (2nd ed.), Martin Kleppmann and Chris Riccomini, Ch 3 "Data Models and Query Languages": the relational model next to document and graph models, and why declarative queries won.
Database Internals, Alex Petrov, Ch 3 "File Formats": slotted pages, cell layout and the binary encoding behind a heap tuple.

Other curricula

donnemartin/system-design-primer: treats the RDBMS section as a scaling story (replication, federation, sharding, denormalization, SQL tuning) and says little about constraints or referential actions.
Azure Architecture Center: Understand data models: frames relational stores as schema-on-write with integrity and ACID, at the cost of sharding for horizontal scale.

Watch

#01 - Relational Model & Algebra (CMU Database Group): Andy Pavlo on Codd's model, keys and the algebra operators that planners rewrite.
11 - Join Algorithms (CMU Database Group): nested loop, sort-merge and hash joins with their I/O costs.
Primary Key vs Secondary Key (Hussein Nasser): how primary and secondary indexes differ in Postgres and MySQL storage.

Free resources

A Relational Model of Data for Large Shared Data Banks (E. F. Codd, 1970): the original paper; the first section on data independence is still the best argument for the model.
PostgreSQL: Constraints: precise semantics of keys, checks and referential actions, including NO ACTION versus RESTRICT.
Architecture of a Database System (Hellerstein, Stonebraker, Hamilton): how a relational engine is organized from process model to storage.
Use The Index, Luke: The Join Operation: how each join algorithm uses indexes, with execution plans.
PostgreSQL: TOAST: how large values are compressed and stored out of line.
Kubernetes: Garbage Collection: cascading deletion through owner references, the same problem outside a database.

Open in the interactive app: practice, quiz, mock interview →