循环的递归CTE停止条件 [英] Recursive CTE stop condition for loops

问题描述

问题在于 loop 部分。

我想要是否有循环，然后选择最短的路径。
这基本上意味着忽略循环，因为递归是宽度优先。

下面的例子显示了返回的数据：

问题是注释掉了创建循环的 INSERT 语句。
显然，查询不会结束。

我需要的是返回与没有循环相同的数据。

p>

  DROP TABLE IF EXISTS edges; 
 
 CREATE TABLE边缘（
 src整数，
 dst整数，
数据整数
）; 
 
插入边缘VALUES（1，2，1）; 
插入边缘VALUES（2,3,1）; 
 --INSERT INTO边缘VALUES（3，2，1）; - 这个入口创建一个循环
 INSERT INTO边缘值（1,4,1）; 
插入边缘VALUES（4，5，1）; 
插入边缘VALUES（5，2，1）; 
 
插入边缘值（1，4，2）; 
插入边缘VALUES（4，5，2）; 
插入边缘VALUES（4，6，2）; 
 
 
带有RECURSIVE路径AS（
  - 为了简单起见，假设节点1是开始
  - 我们将有两个起始节点用于数据= 1和2 
 SELECT DISTINCT 
 src作为节点
，数据作为数据
，0作为深度
，src :: text作为路径
 FROM边数
 WHERE 
 src = 1 
 
 UNION ALL 
 
 SELECT DISTINCT 
 edges.dst 
，edges.data 
，深度+ 1 
，paths.path ||' - >'|| edges.dst :: text 
 FROM paths 
加入边缘边缘.rc = paths.node AND edges.data =路径.data 
  - 并消除循环？
）
 
 SELECT * FROM paths; 
  

返回：

  node |数据|深度|路径
 ------ + ------ + ------- + --------------- 
 1 | 1 | 0 | 1 
 1 | 2 | 0 | 1 
 2 | 1 | 1 | 1-> 2 
 4 | 1 | 1 | 1-> 4 
 4 | 2 | 1 | 1-> 4 
 3 | 1 | 2 | 1-> 2-> 3 
 5 | 2 | 2 | 1-> 4-> 5 
 6 | 2 | 2 | 1-> 4-> 6 
 5 | 1 | 2 | 1-> 4-> 5 
 2 | 1 | 3 | 1-> 4-> 5-> 2 
 3 | 1 | 4 | 1-> 4-> 5-> 2-> 3 
（11行）
  

） - 为了简单起见，假设节点1是开始的
- 我们'将有两个起始节点data = 1和2
SELECT DISTINCT
src作为节点
，数据作为数据
，0作为深度
，src :: text as路径
，''as edgeAdded
FROM边缘
WHERE
src = 1

UNION ALL

SELECT DISTINCT
edges.dst
，edges.data
，depth + 1
，paths.path ||' - >'|| edges.dst :: text
，edges .src :: text ||' - >'|| edges.dst :: text
FROM paths
加入边缘边缘.rc = paths.node AND edges.data = paths.data
AND NOT paths.path LIKE'％'|| edges.dst :: text ||'％'
- AND消除循环？
）
SELECT * FROM paths;

这里使用条件 AND NOT paths.path LIKE'％'|| edges.dst :: text || '％'我们正在避免会导致循环的后沿。

http://www.sqlfiddle.com/#!12/086ee/1

I need to iterate a graph with loops using the recursive CTE.

The problem is the loop part.

I want if there are loops, then the shortest path to be selected. This basically means ignoring the loops because the recursion is "width first".

The example below shows the returned data:

The problem is the commented out INSERT statement that creates a loop. With it uncommented, obviously, the query will never finish.

What I need is to return the same data as it would be without the loop.

DROP TABLE IF EXISTS edges;

CREATE TABLE edges(
  src integer,
  dst integer,
  data integer
);

INSERT INTO edges VALUES (1, 2, 1);
INSERT INTO edges VALUES (2, 3, 1);
--INSERT INTO edges VALUES (3, 2, 1);  -- This entry creates a loop
INSERT INTO edges VALUES (1, 4, 1);
INSERT INTO edges VALUES (4, 5, 1);
INSERT INTO edges VALUES (5, 2, 1);

INSERT INTO edges VALUES (1, 4, 2);
INSERT INTO edges VALUES (4, 5, 2);
INSERT INTO edges VALUES (4, 6, 2);


WITH RECURSIVE paths AS (
  -- For simplicity assume node 1 is the start
  -- we'll have two starting nodes for data = 1 and 2
  SELECT DISTINCT
    src           as node
    , data        as data
    , 0           as depth
    , src::text   as path
  FROM edges
  WHERE
    src = 1

  UNION ALL

  SELECT DISTINCT
    edges.dst
    , edges.data
    , depth + 1
    , paths.path || '->' || edges.dst::text
  FROM paths
    JOIN edges ON edges.src = paths.node AND edges.data = paths.data
    -- AND eliminate loops?
)

SELECT * FROM paths;

Returning:

 node | data | depth |     path      
------+------+-------+---------------
    1 |    1 |     0 | 1
    1 |    2 |     0 | 1
    2 |    1 |     1 | 1->2
    4 |    1 |     1 | 1->4
    4 |    2 |     1 | 1->4
    3 |    1 |     2 | 1->2->3
    5 |    2 |     2 | 1->4->5
    6 |    2 |     2 | 1->4->6
    5 |    1 |     2 | 1->4->5
    2 |    1 |     3 | 1->4->5->2
    3 |    1 |     4 | 1->4->5->2->3
(11 rows)

解决方案

WITH RECURSIVE paths AS (
    -- For simplicity assume node 1 is the start
    -- we'll have two starting nodes for data = 1 and 2
    SELECT DISTINCT
        src           as node
        , data        as data
        , 0           as depth
        , src::text   as path
        , ''          as edgeAdded   
    FROM edges
    WHERE
        src = 1

    UNION ALL

    SELECT DISTINCT
        edges.dst
        , edges.data
        , depth + 1
        , paths.path || '->' || edges.dst::text
        , edges.src::text || '->' || edges.dst::text
    FROM paths
    JOIN edges ON edges.src = paths.node AND edges.data = paths.data
    AND NOT paths.path LIKE '%' || edges.dst::text || '%' 
        -- AND eliminate loops?
)
SELECT * FROM paths;

Here with the condition AND NOT paths.path LIKE '%' || edges.dst::text || '%' we are avoiding back edges which would lead to a loop.
http://www.sqlfiddle.com/#!12/086ee/1

这篇关于循环的递归CTE停止条件的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！