How do you create a loop of foreign keys?

A foreign key is declared as follows:
create table A( a_id int not null primary key, x int ); create table B( b_id int not null primary key, a_id int references A, y int );

This DDL creates two tables, A and B, and a foreign key from B to A.

Is it possible to also create a FK from A to B?

And if it is possible, how can rows be added that point to one another? The whole point of a foreign key is to ensure referential integrity. If we have two rows, a in A, and b in B that point at each other, how did the rows get there? The problem is that inserting the first row would violate referential integrity and be rejected.

WARNING: This is a surprisingly tricky problem. It relies on some parts of SQL, and some concepts, that we won't get to for a few weeks. But it's a fun problem, so try to follow — I've added explanations as necessary. (Full disclosure: I didn't just know the answer, I had to do some research.)

Declaring a cycle of foreign keys

The DDL part is easy. The FK syntax we've been using so far, e.g. a_id int references A, is a convenience. This is illegal:
create table A( a_id int not null primary key, b_id int references B, x int ); create table B( b_id int not null primary key, a_id int references A, y int );

The problem is that references B will be rejected because table does not exist yet. (Remember, DDL statements are not declarations, they are executable code.)

There is a more verbose but more general syntax for foreign keys. We first create the tables, and then alter the table definitions, adding a foreign key:
create table A( a_id int not null primary key, b_id int, x int ); create table B( b_id int not null primary key, a_id int, y int ); alter table A add foreign key(b_id) references B; alter table B add foreign key(a_id) references A;

This works because both tables exist when the foreign keys are added. The first alter statement works as follows:

What about data?

OK, we have the tables. How do we add rows? For example, how would we add the row (1, 2) to A, and (2, 1) to B?

The obvious thing is to run these insert statements:
insert into A values(1, 2); insert into B values(2, 1);

The first statement fails, because the b_id value supplied, 2, refers to a row that doesn't exist, violating referential integrity:
ERROR: insert or update on table "a" violates foreign key constraint "a_b_id_fkey" DETAIL: Key (b_id)=(2) is not present in table "b".

Because the first statement failed, we don't have the row referenced by the second insert, so it fails too:
ERROR: insert or update on table "b" violates foreign key constraint "b_a_id_fkey" DETAIL: Key (a_id)=(1) is not present in table "a".

At the time of the first insert, there is no guarantee that the next insert will make things right, so there is no choice but to fail the insert. The update cannot be allowed, as some other user of the database could then observe the violation of referential integrity!

When he answered the question in class, Prof. Couch said that the fix is to put the two insert statements inside a transaction. What a transaction does is to guarantee that no changes made during the transaction are publicly visible until the transaction commits. In other words: let's allow the first insert. The insert is not public until the transaction commits, and I (the author of the code) will have a chance to make things right, by doing the second insert, before the commit. If we get to the commit and we still have a violation of referential integrity, OK, then it's time to complain and reject all of the transactions updates — none of them become visible to other users of the database.
begin; -- Begins a transaction insert into A values(1, 2); insert into B values(2, 1); commit; -- Commits the current transaction

Alas. Here is our output:
BEGIN ERROR: insert or update on table "a" violates foreign key constraint "a_b_id_fkey" DETAIL: Key (b_id)=(2) is not present in table "b". ERROR: current transaction is aborted, commands ignored until end of transaction block ROLLBACK

What went wrong? SQL requires FKs to be enforced at all times. This isn't unreasonable. It is only bizarre cases like cyclic FKs that get into trouble.

So what's the answer?

The problem can be solved. We're on the right track. The question now is how to "suspend" foreign key constraint checking until the end of the transaction.

Go read up on foreign keys in the Postgres docs, and discuss ideas on Piazza. We can do a 10 points for Gryffindor sort of thing, for the first person to post a script that creates the tables, the foreign keys, populates the tables, and prints the result.