From: Tony Cebzanov <tonyceb@andrew.cmu.edu>
To: Tom Lane <tgl@sss.pgh.pa.us>
Cc: Richard Huxton <dev@archonet.com>
Cc: pgsql-sql@postgresql.org
Subject: Re: Avoiding cycles in a directed graph
Date: Tue, 16 Mar 2010 16:49:44 -0400
Message-ID: <4B9FEEE8.1060404@andrew.cmu.edu> (raw)
In-Reply-To: <14113.1268771643@sss.pgh.pa.us>
References: <4B9FDFDE.5030005@andrew.cmu.edu>
<4B9FE752.4080709@archonet.com>
<14113.1268771643@sss.pgh.pa.us>
On 3/16/10 4:34 PM, Tom Lane wrote:
> 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 :-(
Are you saying there's no way to avoid cycles at all, or just no way to
do it using uniqueness constraints?
I'm okay with running the big, fat WITH RECURSIVE query in my insert
trigger if I have to -- it won't be great for performance, but I don't
expect this to be a frequent operation, so I'll accept the performance
hit if it works.
Unfortunately I can't even get that working. Here's the (not at all
functional) trigger I've got right now, which only detects the cycle
*after* it's been inserted, which is of no help at all. Any way I can
modify this to do the right thing?
CREATE OR REPLACE FUNCTION check_edge_cycle() RETURNS trigger AS $$
DECLARE
cycles INTEGER;
BEGIN
WITH RECURSIVE search_graph(parent, child, id, depth, path, cycle) AS (
SELECT NEW.parent, NEW.child, NEW.id, 1,
ARRAY[NEW.id], false
UNION ALL
SELECT g.parent, g.child, g.id, sg.depth + 1,
path || g.id,
g.id = ANY(path)
FROM catalog_edge g, search_graph sg
WHERE g.parent = sg.child AND NOT cycle
)
SELECT INTO cycles COUNT(*) FROM search_graph WHERE cycle=true;
RAISE NOTICE 'cycles: %', cycles;
IF cycles > 0 THEN
RAISE EXCEPTION 'cycle';
END IF;
RETURN NEW;
END
$$ LANGUAGE plpgsql;
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: tonyceb@andrew.cmu.edu, tgl@sss.pgh.pa.us, dev@archonet.com
Subject: Re: Avoiding cycles in a directed graph
In-Reply-To: <4B9FEEE8.1060404@andrew.cmu.edu>
* 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