Foreign Keys

Accept REFERENCES <table> (<column>) on a column, check that it targets a key or unique column of the same type, and refuse any INSERT or UPDATE that gives the column a value no parent row has, with an index lookup in the parent and 01704.

Not run yet · 9 tests

Why this stage exists

Every join so far trusted the data: o.user_id = u.id assumed each order's user_id named a real user. Nothing guaranteed it. An order for user 99, who does not exist, joins to nobody and silently drops out of every report.

A foreign key makes the database guarantee it. user_id INT REFERENCES users (id) says that every user_id that is not NULL is the id of some row of users. orders is the child, users the parent, and users.id the target.

What the target must be

The target must identify one parent row: it is the parent's key, or the one column of a unique index. Referencing users.name, which two users may share, is 01705. The two columns must also have the same type, INT with INT or VARCHAR with VARCHAR, since 5 can never equal '5': 01706.

A table may reference itself. In employees (id INT PRIMARY KEY, manager_id INT REFERENCES employees (id)), the boss has manager_id NULL, everyone else names an existing employee, and a row may even name its own id.

The check is a lookup

On every INSERT, and on every UPDATE that assigns the column, the new value is looked up in the parent:

update orders set user_id = 2 where id = 10

Update (table=orders)

↑ 1 row

IndexScan (table=orders, key=10)

the foreign key check, for the new value 2

ran

IndexScan (table=users, key=2)

The update reads its one row and the check finds one user by key: rows_examined=2.

That is why the target must be indexed: a check is one descent of a B+Tree, never a scan of the parent. Through a unique index such as users.email, it is an index lookup, and counts in index_lookups.

NULL is always allowed and checks nothing. It means "no parent", like an order not yet assigned to anyone. So "every value exists as a key" is not quite the rule; "every value that is not NULL" is.

Checks are immediate: the statement that breaks the rule fails with 01704 and changes nothing, inside a transaction too, and the statements before it keep their work.

Note what is not created: an index on orders.user_id. The check goes the other way, child to parent. The next stage, deleting parents, shows what that missing index costs.

The algorithm in words

Declaring a foreign key

Check the target once, when the table is created.

1.Read REFERENCES <table> (<column>) as a column option.
2.The parent table exists, or is the table being created (00401).
3.The target column exists (00402), and is the parent's key or the one column of a unique index (01705).
4.The two columns have the same type, INT or VARCHAR (01706). Store the foreign key with the table in the catalog.

Enforcing it

One lookup per value.

1.After every other check of an INSERT, or for each row an UPDATE assigns the column, take the new value.
2.If it is NULL, there is nothing to check.
3.Otherwise look it up in the parent, by key or through the target's unique index, as a SELECT of target = value would.
4.If no row is found, the statement is 01704 and changes nothing.

Output contract for this stage

These are the exact lines the tests check. The full definition is on the output contract page, section 75.

Input	Output
`insert into orders (id, user_id, total) values (12, 99, 1);`	`[ERROR:01704] ...`
`create table a (id int primary key, u varchar(20) references users (name));`	`[ERROR:01705] ...`
`create table a (id int primary key, u varchar(20) references users (id));`	`[ERROR:01706] ...`
`update orders set user_id = 2 where id = 10;`	`Update statement executed successfully (1 rows)`, `[EXEC] rows_examined=2`
`catalog list`	`... (id INT PRIMARY KEY, user_id INT REFERENCES users(id), total INT)`
`ast create table orders (id int primary key, user_id int not null references users (id));`	`Columns: [id int PRIMARY KEY, user_id int NOT NULL REFERENCES users(id)]`
`tokenize references`	`[KEYWORD_REFERENCES - references]`

What you should see when done

shell

$droid --db fk.db
Welcome to droid!
>create table users (id int primary key, name varchar(20));
Create table statement executed successfully
>create table orders (id int primary key, user_id int references users (id));
Create table statement executed successfully
>insert into users (id, name) values (1, 'ada');
Insert statement executed successfully (1 rows)
>insert into orders (id, user_id) values (10, 1);
Insert statement executed successfully (1 rows)
>insert into orders (id, user_id) values (11, 99);
[ERROR:01704] no row of users has id 99
>insert into orders (id, user_id) values (12, NULL);
Insert statement executed successfully (1 rows)
>.exit
exiting.. good bye!

Common bugs in this stage

Checking NULL. It is always allowed.
Scanning the parent. Look the value up by key or unique index.
Checking before the other checks. 01704 comes last, after 00701 and 01605.
A self-reference that cannot name its own row. The check sees the row the statement is writing.
Forgetting the foreign key on reopen. It lives in the catalog with the table.

Language notes

The page above is the same for every language. These are the only language-specific hints.

C: a small array of foreign keys per table (column index, parent table id, target column index) loaded with the catalog.
C++: a std::vector<ForeignKey> in the table's schema object.
Rust: Vec<ForeignKey> in the schema, with the parent resolved to a table id at CREATE time.
Zig: an ArrayList(ForeignKey) in the table's catalog entry.

Loading starter code…

No run yet

9 tests wait for your first run

Run tests builds your code, drives the binary through every case for this stage, and shows expected and received output side by side here. Failing cases come first.