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

知道世界尽头

描述
在我们的问题域中，我们正在研究一组连接在一起以形成图形的边。从给定的一个或多个节点开始，我们必须列出整个图中连接到给定的一个或多个节点的所有链接。我们必须从左到右，从上到下显示这些链接。
对于循环数量有限的图形，我们有一个针对此问题的有效查询。循环次数越多，执行时间就成倍增加。
我们需要在递归过程中限制对同一节点的访问，以获取有效的解决方案。
下面的示例仅包含一个循环，但是此循环已引起86个额外的和过时的行。
在类似的帖子中，提供了使用ROW和ANY运算符的postgresql解决方案，但是我找不到Oracle解决方案。
我们正在寻找解决方案的替代方案或将访问次数限制在同一边缘的方法。
任何帮助是极大的赞赏！
例子
边缘
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, 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$ 笔记
[ol]通过将union一组反向边添加到输入中，我将有向图预处理为一个无向图。这应该使递归遍历谓词更易于阅读。仅出于我的目的，以便于更轻松地读取和编写SQL。当然，您不必这样做。
我记得几年前在Oracle 11.2上尝试过类似的方法。我记得那是失败的，尽管我不记得为什么。在12.2上，它运行正常。也尝试一下11g。我没有一个。
由于除了遍历内部联接之外，每次迭代都还进行了反联接，因此，我真诚地怀疑这会提高性能。但是，它肯定解决了减少递归嵌套数量的问题。
正如您可能从我的评论中了解到的那样，您必须自己解决所需的排序。:-)
[/ol]
将重新访问的边限制为零
在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() 当调用的起始节点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
笔记
[ol]同样，我没有做出任何努力来保持您所请求的顺序，因为您说的并不那么重要。
这是对edge表的多次SQL往返（对于您的示例输入而言，恰好是5个）。与具有冗余边缘访问功能的纯SQL解决方案相比，这可能会或可能不会对性能造成更大的影响。正确测试更多解决方案，看看哪一种最适合您。
这段特定的代码将在12c及更高版本上运行。对于11g及更低版本，您必须在架构级别声明rec_output和arr_output类型。
[/ol]

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

知道世界尽头 LV1