Re: Avoiding cycles in a directed graph

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