From: Tom Lane <tgl@sss.pgh.pa.us>
To: Richard Huxton <dev@archonet.com>
Cc: Tony Cebzanov <tonyceb@andrew.cmu.edu>
Cc: pgsql-sql@postgresql.org
Subject: Re: Avoiding cycles in a directed graph
Date: Tue, 16 Mar 2010 16:34:03 -0400
Message-ID: <14113.1268771643@sss.pgh.pa.us> (raw)
In-Reply-To: <4B9FE752.4080709@archonet.com>
References: <4B9FDFDE.5030005@andrew.cmu.edu>
<4B9FE752.4080709@archonet.com>
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
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: tgl@sss.pgh.pa.us, dev@archonet.com, tonyceb@andrew.cmu.edu
Subject: Re: Avoiding cycles in a directed graph
In-Reply-To: <14113.1268771643@sss.pgh.pa.us>
* 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