Re: Avoiding cycles in a directed graph

Richard Huxton <dev(at)archonet(dot)com> writes:
> On 16/03/10 21:09, Tom Lane wrote:
>> If you don't expect this to be common, maybe you could fix the
>> concurrency issue by taking a table-wide lock that locks out
>> other writers.

> Surely SELECT FOR UPDATE on the parents would be sufficient? If there's
> no overlap between (currently non-cyclic) graphs being altered then
> there can't be any conflict.

Um, what if the cycle is being formed from whole cloth? For instance
T1 inserts an edge A->B while T2 is inserting B->A. There are no
pre-existing rows to lock, but there will still be a cycle after they
both commit.

Also it seems pretty deadlock-prone if there are multiple existing rows
to try to lock. Perhaps you could work around the risk by locking those
rows one at a time in an application-defined ordering ... but I'm afraid
the performance would be poor, unless the connected graphs are always
very small.

On the whole I think Tony's better off with a KISS approach, ie just
lock the whole table against other writers.

regards, tom lane