Re: Avoiding cycles in a directed graph

Richard Huxton <dev@archonet.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