I'm using the following table to represent an acyclic directed graph:
CREATE TABLE edge(
id SERIAL PRIMARY KEY,
child INTEGER NOT NULL,
parent INTEGER,
UNIQUE (child, parent)
);
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:
WITH RECURSIVE search_graph(parent, child, id, depth, path, cycle)
AS (
SELECT e.parent, e.child, e.id, 1,
ARRAY[e.id],
false
FROM edge e
UNION ALL
SELECT e.parent, e.child, e.id, sg.depth + 1,
path || e.id,
e.id = ANY(path)
FROM edge e, search_graph sg
WHERE e.parent = sg.child AND NOT cycle
)
SELECT * FROM search_graph;
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. I tried having
the non-recursive SELECT use NEW.parent, NEW.child, etc. but that isn't
working. Is there any way to do this, or do I have to just insert the
edge, check if it cycles, and delete it if it does?
Thanks.
-Tony
--
Sent via pgsql-sql mailing list ([email protected])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-sql
