Multi-Table Support & Foreign Keys

Building a Database Engine: Transactions & Concurrency

Chapter 7 · Multi-Table Support & Foreign Keys

Course 1's own Database class could already hold more than one table — that was never the missing piece. What's missing is any guarantee about how those tables relate to each other: nothing stops an orders row from pointing at a customer_id that doesn't exist anywhere in customers. This chapter builds a real foreign key constraint — checked on every insert, using the exact same B-tree index machinery Course 1 already built for a completely different reason.

A Real Catalog, and a Real Constraint

class ForeignKey:
    def __init__(self, column, ref_table, ref_column):
        self.column = column; self.ref_table = ref_table; self.ref_column = ref_column

class Catalog:
    def insert(self, table_name, values):
        schema, table = self.tables[table_name]
        column_names = [n for n, t in schema.columns]
        for fk in self.foreign_keys.get(table_name, []):
            idx = column_names.index(fk.column)
            fk_value = values[idx]
            if not self._value_exists(fk.ref_table, fk.ref_column, fk_value):
                raise ForeignKeyViolation(
                    f"{fk.column}={fk_value!r} does not exist in {fk.ref_table}.{fk.ref_column}"
                )
        location = table.insert(values)     # only reached if every FK check passed
        # ... update indexes for this table, unchanged from Course 1 Chapter 9 ...
        return location
    

Finding 1: A Real Foreign Key, Verified Both Ways

Verified directly — a valid insert succeeds, an invalid one is rejected and never touches disk

An order referencing customer id=1 (a real, existing customer) inserts normally. An order referencing customer id=999 (which doesn't exist) raises ForeignKeyViolation — and a real scan of the orders table afterward confirms it: only the valid order is present. The rejected insert never reached table.insert() at all.

Finding 2: Reusing Course 1's Own Index Makes This Fast

Checking whether a value exists in another table means either scanning it in full, or — if an index already exists on the referenced column — a real btree_search() call.

Verified directly — a real, measured 180× speedup

200 foreign-key-checked inserts against a 3,000-row customers table, always referencing the last row (the worst case for a scan): 0.617s with no index. The identical test with an index on customers.id: 0.003s — ≈180× faster. A foreign key check is nothing more than a repeated existence lookup — exactly the operation Course 1's own Storage & Query Fundamentals Chapters 5–6 built a B-tree index to make fast.

Finding 3: A Real Bug — Referencing a Table That Doesn't Exist Yet

The first, most natural version of create_table() just stores whatever foreign keys it's given, with no check that the referenced table actually exists.

Verified directly — a confusing, unhelpful crash on the FIRST insert

Creating orders with a foreign key to customers — before customers has ever been created — succeeds with no complaint at all. The real failure only shows up later, on the very first insert into orders, as a raw KeyError: 'customers' — a confusing error with no indication of what actually went wrong or when the real mistake happened.

The fix — validate the reference immediately, at CREATE TABLE time

create_table() now checks every foreign key's own ref_table against the catalog's existing tables (allowing ref_table == name for a genuine self-reference) before registering anything. The identical mistake now raises a clear SchemaError — "foreign key references unknown table 'customers' — it must be created first" — at the exact moment it's made, and orders is never left half-registered in the catalog.

Finding 4: A Real, Working Multi-Table System

Verified directly — three customers, three valid orders, three real rejections

Three real customers, three valid orders referencing them, and three deliberately invalid customer_id values — all three rejected, none reaching the heap file. A manual join (matching each order's own customer_id against the customers table) never has to handle a dangling reference, because the foreign key constraint guarantees none can exist.

A Genuine Structural Discovery: Self-Reference Under Check-Before-Insert

Building an exercise around a self-referencing table (an employees row whose own manager_id points at another row in the same table) surfaced something worth explaining honestly rather than working around quietly.

Verified directly — a row can never reference its own not-yet-inserted id

Inserting a row whose manager_id equals its own not-yet-assigned id — for instance, a CEO row that reports to itself — is always rejected, no matter which row number it is. This isn't a bug specific to self-reference: the foreign key check always runs before table.insert(), so the row genuinely doesn't exist yet at the moment its own value is checked against itself. Any row whose foreign key equals its own id is structurally impossible under this ordering.

Reordering to insert first and validate second — physically writing the row, then checking, then rolling it back if invalid — resolves this cleanly, reusing Chapter 4's own real Transaction and TransactionalHeapFile completely unmodified:

def insert_allow_self_reference(cat, table_name, values):
    schema, real_table = cat.tables[table_name]
    txn = Transaction()                                          # Chapter 4, unmodified
    thf = TransactionalHeapFile(real_table.heap_file, txn, table_name)
    location = HeapTable(thf, schema).insert(values)             # physically written first

    for fk in cat.foreign_keys.get(table_name, []):
        fk_value = values[[n for n, t in schema.columns].index(fk.column)]
        if not cat._value_exists(fk.ref_table, fk.ref_column, fk_value):
            txn.rollback({table_name: real_table.heap_file})     # undo the physical write
            raise ForeignKeyViolation(...)
    txn.commit()
    return location
    

Verified directly — self-reference now genuinely works, and true violations still don't

A CEO row with manager_id pointing at its own id now inserts successfully — by the time the check runs, the row is already physically present, so it can find itself. A genuinely invalid row (referencing a manager who doesn't exist at all) is still correctly rejected, and Chapter 4's own rollback() cleanly removes the physical write it made moments earlier — the invalid row never appears in a final scan.

Where This Connects

This chapter's finding	What it connects to
Index-backed FK checks, 180× faster	Building a Database Engine: Storage & Query Fundamentals Chapters 5–6, 9 (Course 1) — the B-tree index and query planner reused here for a genuinely new purpose
Insert-then-validate-then-rollback for self-reference	Chapter 4 (this course) — real, unmodified reuse of `Transaction`/`TransactionalHeapFile`, in a context that chapter never anticipated
Referencing a not-yet-created table	An honest, deliberate ordering constraint this engine now enforces — parent tables must exist before a child table can reference them, matching real SQL practice

Hands-On Exercises

Exercise 1

Create a table with no foreign_keys argument at all, insert a few rows into it, and confirm both that the inserts succeed exactly as they would in Course 1's own plain HeapTable, and that catalog.foreign_keys[table_name] is an empty list rather than None or missing entirely.

📄 View solution

Exercise 2

Build the self-referencing employees example from this chapter yourself: confirm a row referencing its own not-yet-inserted id is rejected under the normal insert() path, then use insert_allow_self_reference() to successfully insert it, followed by a second, genuinely invalid row that should be rolled back.

📄 View solution

Exercise 3

Build an index on a referenced column before any data exists in that table (on a genuinely empty table), then insert real rows into both tables afterward. Confirm the index stays accurate as rows are added, and that a foreign-key check against it still correctly catches an invalid reference.

📄 View solution

Chapter 7 Quick Reference

ForeignKey(column, ref_table, ref_column): checked on every insert, before the row is written
Verified Finding 1: a valid insert succeeds; an invalid one is rejected and never reaches the heap file
Verified Finding 2: routing the check through an existing B-tree index is ≈180× faster than a full scan
Verified Finding 3: a foreign key to a not-yet-created table crashed confusingly on first insert — fixed with immediate validation at CREATE TABLE time
Genuine discovery: a row can never reference its own not-yet-inserted id under check-before-insert — resolved by inserting first and rolling back on failure, reusing Chapter 4's own real transaction machinery
Next chapter: Joins — nested-loop and hash join, replacing this chapter's manual dictionary-based join with real join algorithms