Detect cycles using sql

Question

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?

Answer 1

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

Fiddle

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):

1. Run the first SELECT, selecting all entries from table t and placing them in a temporary table named working.
2. Then run the second 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.
3. Now run the second SELECT again and again, as long as entries are added to the working table.
4. A cycle is detected when one of the entries visits a child that it has visited before (t.parent = ANY(already_visited)) in this case cycle_detected is set to true and no more children are added to the entry.