Re: Avoiding cycles in a directed graph

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;