From: Richard Huxton <dev@archonet.com>
To: Tony Cebzanov <tonyceb@andrew.cmu.edu>
Cc: pgsql-sql@postgresql.org
Subject: Re: Avoiding cycles in a directed graph
Date: Tue, 16 Mar 2010 20:17:22 +0000
Message-ID: <4B9FE752.4080709@archonet.com> (raw)
In-Reply-To: <4B9FDFDE.5030005@andrew.cmu.edu>
References: <4B9FDFDE.5030005@andrew.cmu.edu>
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
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-sql@postgresql.org
Cc: dev@archonet.com, tonyceb@andrew.cmu.edu
Subject: Re: Avoiding cycles in a directed graph
In-Reply-To: <4B9FE752.4080709@archonet.com>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox