Oracle SQL中的定向图使用递归查询仅访问每个节点一次

在我们的问题域中,我们正在研究一组连接在一起形成图形的边.
从给定节点(或节点)开始,我们必须列出整个图中连接到给定节点(或节点)的所有链接.
我们必须从左到右,从上到下显示这些链接.

对于具有有限循环次数的图形,我们对此问题有一个有效的查询.较多的循环会以指数方式增加执行时间.

我们需要在递归期间限制对同一节点的访问以获得有效的解决方案.

下面的示例只包含一个循环,但是这个循环已经导致了86个额外的和过时的行.

在类似的帖子中,使用ROW和ANY运算符为postgresql提供了解决方案,但我找不到Oracle解决方案.

我们正在寻找替代解决方案或限制访问相同边缘的方式.

任何帮助是极大的赞赏！

类似

Visiting a directed graph as if it were an undirected one,using a recursive query在postgresql中提供了一个解决方案.
我们需要使用Oracle11g.

例

边缘

A-B,B-D,C-A,C-E,C-F,H-F,E-B,G-D,G-I

图形

A
  /   
C - E - B - D
         /
H - F   G - I

DDL和DML

CREATE TABLE EDGE (
  FROM_ID VARCHAR(10),TO_ID   VARCHAR(10)
);

INSERT INTO EDGE VALUES ('A','B');
INSERT INTO EDGE VALUES ('E','B');
INSERT INTO EDGE VALUES ('C','E');
INSERT INTO EDGE VALUES ('C','A');
INSERT INTO EDGE VALUES ('C','F');
INSERT INTO EDGE VALUES ('B','D');
INSERT INTO EDGE VALUES ('G','D');
INSERT INTO EDGE VALUES ('H','F');
INSERT INTO EDGE VALUES ('G','I');

输入

nodes: 'A'

要求的输出

C   A
C   E
C   F
H   F
A   B
E   B
B   D
G   D
G   I

现行解决方案

我们当前的解决方案正是我们所需要的,但如上所述,每个额外的循环都会以指数方式增加执行时间.

SELECT
  c.LVL,c.FROM_ID,c.TO_ID,CASE
  WHEN lag(C.TO_ID)
       OVER (
         PARTITION BY C.LVL
         ORDER BY C.LVL,C.TO_ID ) = C.TO_ID
    THEN C.LVL || '-' || C.TO_ID
  WHEN lead(C.TO_ID)
       OVER (
         PARTITION BY C.LVL
         ORDER BY C.LVL,C.TO_ID ) = C.TO_ID
    THEN C.LVL || '-' || C.TO_ID
  ELSE C.LVL || '-' || C.FROM_ID
  END GROUP_ID
FROM (
       WITH chain(LVL,FROM_ID,TO_ID ) AS (
         SELECT
           1            LVL,root.FROM_ID FROM_ID,root.TO_ID   TO_ID
         FROM EDGE root
         WHERE root.TO_ID IN (:nodes)
               OR (root.FROM_ID IN (:nodes) AND NOT EXISTS(
             SELECT *
             FROM EDGE
             WHERE TO_ID IN (:nodes)
         ))
         UNION ALL
         SELECT
           LVL +
           CASE
           WHEN previous.TO_ID = the_next.FROM_ID
             THEN 1
           WHEN previous.TO_ID = the_next.TO_ID
             THEN 0
           WHEN previous.FROM_ID = the_next.FROM_ID
             THEN 0
           ELSE -1
           END              LVL,the_next.FROM_ID FROM_ID,the_next.TO_ID   TO_ID
         FROM EDGE the_next
           JOIN chain previous ON previous.TO_ID = the_next.FROM_ID
                                  OR the_next.TO_ID = previous.FROM_ID
                                  OR (previous.TO_ID = the_next.TO_ID AND previous.FROM_ID <> the_next.FROM_ID)
                                  OR (previous.TO_ID <> the_next.TO_ID AND previous.FROM_ID = the_next.FROM_ID)
       )
         SEARCH BREADTH FIRST BY FROM_ID SET ORDER_ID
         CYCLE FROM_ID,TO_ID SET CYCLE TO 1 DEFAULT 0
       SELECT
         C.*,row_number()
         OVER (
           PARTITION BY LVL,TO_ID
           ORDER BY ORDER_ID ) rank
       FROM chain C
       ORDER BY LVL,TO_ID
     ) C
WHERE C.rank = 1;

解决方法

您必须拥有一个方便的模式级标量集合：

create or replace type arr_strings is table of varchar2(64);

然后,您可以在每次迭代中收集到该集合的访问边：

with nondirected$as (
    select from_id,to_id,from_id||'-'||to_id as edge_desc
    from edge
    where from_id != to_id
    union all
    select to_id,from_id,from_id||'-'||to_id as edge_desc
    from edge
    where (to_id,from_id) not in (
            select from_id,to_id
            from edge
        )
),graph$(lvl,edge_desc,visited_edges) as (
    select 1,arr_strings(edge_desc)
    from nondirected$R
    where from_id in (&nodes)
    --
    union all
    --
    select
        lvl+1,Y.from_id,Y.to_id,Y.edge_desc,X.visited_edges multiset union arr_strings(Y.edge_desc)
    from graph$X
        join nondirected$Y
            on Y.from_id = X.to_id
    where not exists (
            select 1
            from table(X.visited_edges) Z
            where Y.edge_desc = Z.column_value
        )
)
search breadth first by edge_desc set order_id
    cycle edge_desc set is_cycle to 1 default 0,ranked_graph$as (
    select C.*,row_number() over (partition by edge_desc order by lvl,order_id) as rank$
    from graph$C
--    where is_cycle = 0
)
select *
from ranked_graph$
--where rank$<= 1
order by lvl,order_id
;

笔记

>我通过将一组反向边结合到输入,将有向图预处理为非定向图.这应该使递归遍历谓词更容易阅读.仅仅为了我更容易阅读SQL的写作目的.当然,你不必这样做.
>我记得几年前在Oracle 11.2上尝试这样的事情.我记得它失败了,虽然我不记得为什么.在12.2,它运行正常.也试试11g吧;我没有可用的.
>由于每次迭代都会执行,除了遍历内连接外,还有反连接,我真诚地怀疑这将是更高效的.但是,它肯定解决了降低递归嵌套数量的问题.
>您必须自己解决所需的顺序,正如您可能从我的评论中理解的那样.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!