Message-ID: <4B9FE752.4080709@archonet.com>
Date: Tue, 16 Mar 2010 20:17:22 +0000
From: Richard Huxton <dev@archonet.com>
User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US;
	rv:1.9.1.9pre) Gecko/20100217 Lightning/1.0b1 Shredder/3.0.3pre
MIME-Version: 1.0
To: Tony Cebzanov <tonyceb@andrew.cmu.edu>
CC: pgsql-sql@postgresql.org
Subject: Re: Avoiding cycles in a directed graph
References: <4B9FDFDE.5030005@andrew.cmu.edu>
In-Reply-To: <4B9FDFDE.5030005@andrew.cmu.edu>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

On 16/03/10 19:45, Tony Cebzanov wrote:
> I'm using the following table to represent an acyclic directed graph:
[snip]
> I see there is an example in the online docs for detecting cycles in
> recursive queries, and I've adapted the example query to the table above:
[snip]
> 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)

If you have a "before" trigger, then step 4 could return NULL rather 
than raise an error. That would just skip the insert.

Also, step #1 could be done with a CHECK constraint which would be 
checked before your trigger gets run.

-- 
   Richard Huxton
   Archonet Ltd