To: Richard Huxton <dev@archonet.com>
cc: Tony Cebzanov <tonyceb@andrew.cmu.edu>, pgsql-sql@postgresql.org
Subject: Re: Avoiding cycles in a directed graph 
In-reply-to: <4B9FE752.4080709@archonet.com> 
References: <4B9FDFDE.5030005@andrew.cmu.edu> <4B9FE752.4080709@archonet.com>
Comments: In-reply-to Richard Huxton <dev@archonet.com>
	message dated "Tue, 16 Mar 2010 20:17:22 -0000"
Date: Tue, 16 Mar 2010 16:34:03 -0400
Message-ID: <14113.1268771643@sss.pgh.pa.us>
From: Tom Lane <tgl@sss.pgh.pa.us>

Richard Huxton <dev@archonet.com> writes:
> On 16/03/10 19:45, Tony Cebzanov wrote:
>> That's great to avoid looping forever on queries, but what about
>> preventing anyone from inserting edges that would create cycles in the
>> first place?  I reckon I'll need a trigger of some sort, but nothing
>> I've tried has enabled me to do the cycle check as part of the trigger
>> to avoid inserting an edge that would create a cycle.

> You've got the right idea.

> If you know that the table doesn't contain any cycles at the moment, 
> then all the trigger has to do is:
> 1. Check "parent" <> "child"
> 2. Build the set of parents of "parent".
> 3. Check "child" isn't in that set.
> 4. If there is a cycle, raise an error (which will abort the insert or 
> update)

The problem with this approach is that it's not safe against concurrent
insertions.  If concurrent transactions T1 and T2 each insert a row
that, taken together (and in combination with existing entries), create
a cycle, then neither of their triggers will see the other's row so
they'll both think they can commit.

The same kind of problem exists for unique and foreign key constraints,
both of which use low-level locking mechanisms to catch such cases.
There's no way that I can see to express the "no cycle" constraint as a
uniqueness constraint unfortunately.  You could solve limited forms of
it using the exclusion-constraint mechanism that's new in 9.0, but
AFAICS not the general case :-(

			regards, tom lane