Foreign Keys

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:

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.

Output contract for this stage

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

What you should see when done

$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.