# Query to find circular references

I have two tables

``````ID  Task
1   1
2   2
3   3
4   4

Col1  depend
2     3
2     4
3     1
4     2
``````

`ID` and `Col1` are related through FK constraint. I want to find out all circular references. Here `ID` and `Col1` is just for combining rows from 2 tables, e.g.:

``````Task 1 can start anytime.
Task 2 can start only after completion of 3, 4 etc

1 –
2 – 3, 4, 1, 2   -- for 2 there is circular dependency
3 – 1
4 – 2, 3, 4      -- also circular dependency
``````

Case 2:

``````Col1  depend
2     3
2     4
3     1
4     5
5     2

1   1
2   2
3   3
4   4
5   5

1
2 – 3, 4, 1, 5, 2     -- circular reference
3 – 1
4 – 5, 2, 3, 4        -- circular reference
5 – 2, 3, 4, 5        -- circular reference
``````

Circular references may be available at any recursion level. How to find such circular references?
We have tried a recursive query but we went in infinite loop. How to write recursive query for this?

• It's quite easy to prevent the infinite loop for a recursive query, but I have not found a way to actually mark a row as having a cycle (because the JOIN condition to prevent the loop will filter out the last element). – a_horse_with_no_name May 7 '14 at 13:52

``````WITH RECURSIVE search_graph(id, depends, depth, path, cycle) AS (
SELECT g.Col1, g.depends, 1,
ARRAY[g.Col1],
false
FROM deps g
UNION ALL
SELECT g.Col1, g.depends, sg.depth + 1,
path || g.Col1,
g.Col1 = ANY(path)
FROM deps g, search_graph sg
WHERE g.Col1 = sg.depends AND NOT cycle
)
SELECT distinct id FROM search_graph where cycle = true;
``````

results:

``````ID
4
2
``````

for the first example,

``````ID
4
2
5
``````

for the second

You can find the sql fiddle at http://sqlfiddle.com/#!15/87a96/2

Also building on the example in the manual:

``````WITH RECURSIVE graph AS (
SELECT col1 AS id
, ARRAY[depend, col1] AS path
, (depend = col1) AS cycle    -- first step could be circular
FROM   dep

UNION ALL
SELECT d.col1, d.depend || path, d.depend = ANY(path)
FROM   graph g
JOIN   dep   d ON d.col1 = g.path
WHERE  NOT g.cycle
)
SELECT DISTINCT id
FROM   graph
WHERE  cycle;
``````

Result

``````id
2
4
5
``````

SQL Fiddle.

This is a bit simpler and faster:

• No irrelevant columns.
• Needs one less iteration because it checks ahead.
• Identifies short-circuiting rows immediately. (It has not been ruled out that a row can link to itself.)

This one `prepends` the path with the respective new item, so we can use `path` instead of an additional column. To my knowledge, just as fast as appending elements.
Accessing the first element of an array should be almost as cheap as an extra column - which would make the row wider. Test and compare if performance is important:

``````WITH RECURSIVE graph AS (
SELECT col1 AS id, depend AS col1  -- simplify join condition
, ARRAY[col1, depend] AS path
, (col1 = depend) AS cycle    -- simplify if short-circuit impossible
FROM   dep

UNION ALL
SELECT d.col1, d.depend
, path || d.depend, d.depend = ANY(path)
FROM   graph g
JOIN   dep   d USING (col1)
WHERE  NOT g.cycle
)
SELECT DISTINCT id
FROM   graph
WHERE  cycle;
``````