6

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

ID  Task
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
4

I adapted the example at http://www.postgresql.org/docs/8.4/static/queries-with.html to your case:

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

| improve this answer | |
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[1]
   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[1] 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;
| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.