时间戳

首页 > 解决方案 > 如何避免递归无限循环？(postgreSQL)

sql - 如何避免递归无限循环？(postgreSQL)

问题描述

我必须提出另一个问题，这已经花费了我几个小时，而且我无法解决它。我需要在 PostgreSQL 中编写一个递归查询（用于大学）。我有一个名为“basedOn”的关系，其中机器基于其他（旧）版本，例如：

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

我需要知道使用递归查询找到所有基于其他版本的传递版本（例如，如果 A 基于 B，B 基于 C，A 基于 C）。我现在的问题是，我还必须为循环解决这个问题，比如“A 基于 B，B 基于 C，C 基于 A”，我的查询循环无限。这就是我的查询现在的样子：

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”只是用来“计数”递归步骤。它适用于非循环数据。但是，如果我在数据中插入一个循环，它会无限循环。有没有人提示，如何避免这种情况？在此先感谢，卢卡斯

样本数据：

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

预期输出：

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

标签： sqlpostgresql

解决方案

你去：

\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;

结果：

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)

推荐阅读