How to avoid recursive endless cycle? (postgreSQL)

Question

I have to come up with another question, which costs me already hours, and I am not able to solve it. I need to write a recursive Query in PostgreSQL (for univercity). I have a relation called "basedOn" where machines are basedOn other (older) versions like:

CREATE TABLE BasedON(
    fromID integer,
    fromSize numeric,
    toID integer,
    toSize numeric,
...
);

I need know to find all transitive versions which base on others (like if A bases on B, and B on C, A bases on C) using a recursive Query. My Problem now is, that I have to solve this also for Cycles like "A bases on B, B on C, and C on A", where my query loops infinite. Thats what my query looks like now:

WITH RECURSIVE tmp(fromID, fromSize, toID, toSize,c) AS (
                    SELECT fromID, fromSize, toID, toSize, 0 FROM BasedOn
                    WHERE toID= 0 AND toSize= 2.0 --start
                UNION 
                    SELECT b.fromID, b.fromSize,  t.toID,t.toSIze, c+1 AS steps
                    FROM BasedOn b JOIN tmp t ON
                                         t.fromID= b.toID AND t.fromSize= b.toSize
 )SELECT * FROM tmp;

"c" is just use to "count" the recursive steps. It works thine for non-cyclic data. But if I insert an cycle into the data it loops infinite. Has anyone a tip, how to avoid this? Thanks in advance, Lukas

SampleData:

INSERT INTO BasedOn VALUES 
                (7000, 1.28, 7003, 2.52),
                (7003, 2.52, 7006, 0.98), --cycle
                (7006, 0.98, 7009, 4.18),
                (7006, 0.98, 7003, 2.52), --cycle
                (7009, 4.18, 7015, 1.33),
                (7009, 4.18, 0, 2.00);

Expected output:

fromID, fromSize, toID, toSize,stepcount
7009    4.18    0   2.00    0
7006    0.98    0   2.00    1
7003    2.52    0   2.00    2
7000    1.28    0   2.00    3

Please provide sample data and desired results. A db fiddle of some sort would be helpful. — Gordon Linoff
– Gordon Linoff, Commented Dec 22, 2019 at 15:31
Use an array to record the steps taken. Check the array before recursing — wildplasser
– wildplasser, Commented Dec 22, 2019 at 15:32
Thanks for the tips, gonna try! I added some insert and expected output data. If i delete the cycle, I get exactly what I want. But with cycle I run into infinity. — iiiiiiiiiiiiiiiiiiii
– iiiiiiiiiiiiiiiiiiii, Commented Dec 22, 2019 at 15:41
Similar to @wildplasser's answer, I've used a VARCHAR to concatenate all "walked" nodes (separated by commas). Then I just check (using POSITION()) I've not already walked the node I want to go to. — The Impaler
– The Impaler, Commented Dec 22, 2019 at 16:22

The Impaler · Accepted Answer · 2019-12-22 16:53:04Z

I made the exercise using ARRAY just for the fun (?).

Anyway, here's the query:

with recursive
s as (
  select
    *, tosize as converted_size, 0 as step_count,
    array[-1]::int[] as walked, 1 as len from basedon 
  where toid = 0 and tosize = 2.0 -- starting node
  union all
  select b.*, s.converted_size, step_count + 1,
    walked || b.fromid, array_length(walked, 1) + 1
  from s
  join basedon b on b.toid = s.fromid and b.tosize = s.fromsize 
                and not (b.fromid = any(walked))
)
select * from s;

Result:

fromid  fromsize  toid  tosize  converted_size  step_count  walked        len
------  --------  ----  ------  --------------  ----------  ------------  ---
7009    4.18         0     2    2               0           <UnknownType  1  
7006    0.98      7009  4.18    2               1           <UnknownType  2  
7003    2.52      7006  0.98    2               2           <UnknownType  3  
7000    1.28      7003  2.52    2               3           <UnknownType  4

Here's the data script I used:

create table basedon (
  fromid integer,
  fromsize numeric,
  toid integer,
  tosize numeric
);

insert into basedon (fromid, fromsize, toid, tosize) values 
  (7000, 1.28, 7003, 2.52),
  (7003, 2.52, 7006, 0.98), --cycle
  (7006, 0.98, 7009, 4.18),
  (7006, 0.98, 7003, 2.52), --cycle
  (7009, 4.18, 7015, 1.33),
  (7009, 4.18, 0, 2.00);

wildplasser · Accepted Answer · 2019-12-22 16:55:53Z

There you go:

\i tmp.sql

CREATE TABLE based_on(
    from_id integer
    , from_size numeric
    , to_id integer
    , to_size numeric
);

INSERT INTO based_on VALUES
                (7000, 1.28, 7003, 2.52),
                (7003, 2.52, 7006, 0.98), --cycle
                (7006, 0.98, 7009, 4.18),
                (7006, 0.98, 7003, 2.52), --cycle
                (7009, 4.18, 7015, 1.33),
                (7009, 4.18, 0, 2.00);

-- I need know to find all transitive versions which base on others (like if A bases on B, and B on C, A bases on C) using a recursive Query. My Problem now is, that I have to solve this also for Cycles like "A bases on B, B on C, and C on A", where my query loops infinite. Thats what my query looks like now:

WITH RECURSIVE tmp(from_id, from_size, to_id, to_size,c,path) AS (
        SELECT from_id, from_size, to_id, to_size
                , 0
                , array[from_id] AS path
        FROM based_on
        WHERE to_id= 0 AND to_size= 2.0 --start
        UNION
        SELECT b.from_id, b.from_size
                ,  t.to_id,t.to_size
        , c+1 AS steps
        , t.path || b.from_id
        FROM based_on b
        JOIN tmp t ON t.from_id= b.to_id -- AND t.from_size= b.to_size
                AND NOT b.from_id = ANY(t.path)
        )
SELECT * FROM tmp;

Result:

DROP SCHEMA
CREATE SCHEMA
SET
CREATE TABLE
INSERT 0 6
 from_id | from_size | to_id | to_size | c |         path          
---------+-----------+-------+---------+---+-----------------------
    7009 |      4.18 |     0 |    2.00 | 0 | {7009}
    7006 |      0.98 |     0 |    2.00 | 1 | {7009,7006}
    7003 |      2.52 |     0 |    2.00 | 2 | {7009,7006,7003}
    7000 |      1.28 |     0 |    2.00 | 3 | {7009,7006,7003,7000}
(4 rows)

BTW: I think, you would probably want to add the path lengths.

Collectives™ on Stack Overflow

How to avoid recursive endless cycle? (postgreSQL)

2 Answers 2

Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related