I want to detect potential cycles in a hierarchy. I have three tables, each have one parent, and one child column:
Table1 contains some nodes (in column child) and their parents (in column parent); Table2 contains all the parents of Table1 (in column child) and their parents (in column parent), and so on.
For example if A is a child of B, and B is a child of C and C is a child of A, then I have a cycle.
Is it possible to detect the cycles using sql commands?
Here's a solution that works with arbitrary depth.
Store all your relationships in one table:
Table t
Parent | Child
------ | -----
B | A
C | B
A | C
E | D
F | E
Then you can use this WITH RECURSIVE query to find cycles:
WITH RECURSIVE working(parent, last_visited, already_visited, cycle_detected) AS (
SELECT parent, child, ARRAY[parent], false FROM t
UNION ALL
SELECT t.parent, t.child, already_visited || t.parent, t.parent = ANY(already_visited)
FROM t
JOIN working ON working.last_visited = t.parent
WHERE NOT cycle_detected
)
SELECT parent, already_visited FROM working WHERE cycle_detected
It will give you the parents that are part of a cycle, and also the cycle they are in:
A | A,C,B,A
B | B,A,C,B
C | C,B,A,C
It works like this (because that is what the keyword RECURSIVE instructs Postgres to do):
SELECT, selecting all entries from table t and placing them in a temporary table named working.SELECT, joining the working table with table t to find the children of each entry. Those children are added to the array of already seen children.SELECT again and again, as long as entries are added to the working table.t.parent = ANY(already_visited)) in this case cycle_detected is set to true and no more children are added to the entry.
CYCLE clause which simplify the processThe way you have structured your tables right now, the following SQL should work:
SELECT * FROM Table1
INNER JOIN Table2 on Table1.child = Table2.parent
INNER JOIN Table3 on Table2.child = Table3.parent
WHERE Table1.parent = Table3.child;
There are very strange references between tables in your task. Yet it is my approach to check existing loop.
Example for table1:
CREATE OR REPLACE FUNCTION fn_table1_check() RETURNS trigger
LANGUAGE plpgsql
AS $$
DECLARE
BEGIN
PERFORM 1 FROM table2
JOIN table3 ON table3.parent=table2.child
WHERE table2.parent=NEW.child AND table3.child=NEW.parent
LIMIT 1;
IF FOUND THEN
RAISE EXCEPTION 'Found recursive loop!';
END IF;
RETURN NEW;
END;
$$;
CREATE TRIGGER tg_table1_check BEFORE INSERT OR UPDATE ON table1 FOR EACH ROW EXECUTE PROCEDURE fn_table1_check();
create tablestatements), some sample data and the expected output based on that data. Formatted text please, no screen shots