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

描述

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

对于循环数量有限的图，我们有一个针对此问题的有效查询。循环次数越多，执行时间就会呈指数增长。

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

下面的示例仅包含一个循环，但该单个循环已导致 86 个额外的过时行。

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

我们正在寻找解决方案的替代方案或限制对相同边缘的访问次数的方法。

任何帮助是极大的赞赏！

Similar

使用递归查询像访问无向图一样访问有向图 https://stackoverflow.com/questions/8764701/visiting-a-directed-graph-as-if-it-were-an-undirected-one-using-a-recursive-quepostgresql中提供了解决方案。 我们需要使用Oracle11g。

Example

Edges

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

Input

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, FROM_ID, TO_ID
           ORDER BY ORDER_ID ) rank
       FROM chain C
       ORDER BY LVL, FROM_ID, 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, from_id, to_id, edge_desc, visited_edges) as (
    select 1, from_id, to_id, edge_desc,
        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
;

Notes

1. 我将有向图预处理为无向图union- 将一组反向边沿输入。这应该会使递归遍历谓词更容易阅读。仅仅是为了更轻松地读取和编写 SQL。当然，你不必这样做。
2. 我记得几年前在 Oracle 11.2 上尝试过类似的事情。我记得它失败了，尽管我不记得为什么。在12.2上，运行正常。也可以在 11g 上尝试一下；我没有可用的。
3. 由于每次迭代除了遍历内连接之外，还进行反连接，因此我真诚地怀疑这是否会提高性能。不过，它确实解决了减少递归嵌套数量的问题。
4. 您必须自己解决所需的顺序，正如您可能从我的评论中了解到的那样。 :-)

将重新访问的边缘限制为零

在 SQL 中，你不能。您提到的 PostgreSQL 解决方案确实可以做到这一点。但在 Oracle 中，您不能这样做。对于每个遍历连接，您必须测试所有其他遍历连接的行。这意味着某种聚合或分析......Oracle 禁止并抛出 ORA 异常。

PLSQL 来救援？

不过，您可以在 PL/SQL 中完成此操作。它应该有多少性能，取决于您想要花费多少内存从数据库预取边，以及您愿意从“当前”节点遍历图形的 SQL 往返次数，或者您是否愿意使用与常规的反连接相比，需要更多的内存来将访问的节点保留在奇特的按边索引集合中arr_output收藏l_visited_nodes。你有多种选择，明智地选择。

无论如何，对于大量使用 SQL 引擎的最简单场景，这可能是您正在寻找的代码......

create or replace
package pkg_so_recursive_traversal
is


type rec_output                     is record (
    from_id                             edge.from_id%type,
    to_id                               edge.to_id%type,
    lvl                                 integer
);
type arr_output                     is table of rec_output;


function traverse_a_graph
    ( i_from                        in arr_strings
    , i_is_directed                 in varchar2 default 'NO' )
    return arr_output
    pipelined;


end pkg_so_recursive_traversal;
/
create or replace
package body pkg_so_recursive_traversal
is


function traverse_a_graph
    ( i_from                        in arr_strings
    , i_is_directed                 in varchar2 )
    return arr_output
    pipelined
is
    l_next_edges                    arr_output;
    l_current_edges                 arr_output;
    l_visited_edges                 arr_output := arr_output();
    l_out                           rec_output;
    i                               pls_integer;
    l_is_directed                   varchar2(32) := case when i_is_directed = 'YES' then 'YES' else 'NO' end;
begin
    select E.from_id, E.to_id, 0
    bulk collect into l_next_edges
    from table(i_from) F
        join edge E
            on F.column_value in (E.from_id, case when l_is_directed = 'YES' then null else E.to_id end)
    where E.from_id != E.to_id;

    l_out.lvl := 0;

    loop
        dbms_output.put_line(l_next_edges.count());
        exit when l_next_edges.count() <= 0;
        l_out.lvl := l_out.lvl + 1;

        -- spool the edges to output
        i := l_next_edges.first();
        while i is not null loop
            l_out.from_id := l_next_edges(i).from_id;
            l_out.to_id := l_next_edges(i).to_id;
            pipe row(l_out);
            i := l_next_edges.next(i);
        end loop;

        l_current_edges := l_next_edges;
        l_visited_edges := l_visited_edges multiset union l_current_edges;

        -- find next edges
        select unique E.from_id, E.to_id, 0
        bulk collect into l_next_edges
        from table(l_current_edges) CE
            join edge E
                on CE.to_id in (E.from_id, case when l_is_directed = 'YES' then null else E.to_id end)
                or l_is_directed = 'NO' and CE.from_id in (E.from_id, E.to_id)
        where E.from_id != E.to_id
            and not exists (
                select 1
                from table(l_visited_edges) VE
                where VE.from_id = E.from_id
                    and VE.to_id = E.to_id
            );
    end loop;

    return;
end;


end pkg_so_recursive_traversal;

/

当调用起始节点时A并考虑该图是无向的......

select *
from table(pkg_so_recursive_traversal.traverse_a_graph(
        i_from => arr_strings('A'),
        i_is_directed => 'NO'
    ));

...它产生...

FROM_ID    TO_ID             LVL
---------- ---------- ----------
A          B                   1
C          A                   1
C          E                   2
B          D                   2
C          F                   2
E          B                   2
G          D                   3
H          F                   3
G          I                   4

Notes

1. 再说一次，我没有付出任何努力来保留您所要求的顺序，正如您所说的那样，这并不重要。
2. 这是执行多次（对于示例输入来说正好是 5 次）SQL 往返edge桌子。与具有冗余边缘访问的纯 SQL 解决方案相比，这可能会对性能产生更大的影响，也可能不会。正确测试更多解决方案，看看哪一种最适合您。
3. 这段特定的代码可以在 12c 及更高版本上运行。对于 11g 及以下，您必须声明rec_output and arr_output模式级别上的类型。