Strange deadlock in foreign key check

[Sophia Wright <sjw9010@xxxxxxxxx>]

I am seeing some odd locking behaviour when deleting a parent record (Postgres 9.4.4).

Setup:
create table pk_rel (id int primary key);
create table fk_rel (pk_id int references pk_rel (id), x text unique);
insert into pk_rel values (1), (2);
insert into fk_rel values (1, 'a');

This example works as I expected.

Session 1:
=>begin;
=>update fk_rel set pk_id = 2;

Session 2:
=>delete from pk_rel where id = 1;

[Fails with FK violation]

But the following case, I do not understand.

Session 1:
=>begin;
=>update fk_rel set x = 'b';

Session 2:
=>delete from pk_rel where id = 1;

[Blocks waiting for Session 1]

Session 1:
=>insert into fk_rel values (1, 'a');

[Blocks waiting for Session 2]

At this point, Session 1 fails with a deadlock, and Session fails with a FK violation.

So, why is this happening? Why doesn't Session 2 fail the FK check immediately, like in the first case? And why is it that updating fk_rel.x introduces a lock conflict, but updating fk_rel.pk_id does not?