Message-ID: <4B9FEEE8.1060404@andrew.cmu.edu>
Date: Tue, 16 Mar 2010 16:49:44 -0400
From: Tony Cebzanov <tonyceb@andrew.cmu.edu>
User-Agent: Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10.5; en-US;
	rv:1.9.1.8) Gecko/20100227 Thunderbird/3.0.3 Mnenhy/0.7.6.0
MIME-Version: 1.0
To: Tom Lane <tgl@sss.pgh.pa.us>
CC: Richard Huxton <dev@archonet.com>, pgsql-sql@postgresql.org
Subject: Re: Avoiding cycles in a directed graph
References: <4B9FDFDE.5030005@andrew.cmu.edu> <4B9FE752.4080709@archonet.com>
	<14113.1268771643@sss.pgh.pa.us>
In-Reply-To: <14113.1268771643@sss.pgh.pa.us>
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit

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;