主页 / 问题 / 1536237
Accepted
Виталий Яндулов
Asked:2023-08-16 23:42:58 +0000 UTC2023-08-16 23:42:58 +0000 UTC

如何避免在递归查询中重新获取数据？

  • 772

假设我有一个图，其顶点已编号。在表中，我存储图的边，即 边的起点和终点的顶点编号。如何递归提取与给定顶点相关的所有顶点？

图形

我如何尝试做到这一点：

WITH vals AS (
  SELECT 1 A, 2 B FROM DUAL UNION ALL
  SELECT 1 A, 5 B FROM DUAL UNION ALL
  SELECT 1 A, 6 B FROM DUAL UNION ALL
  SELECT 2 A, 3 B FROM DUAL UNION ALL
  SELECT 2 A, 6 B FROM DUAL UNION ALL
  SELECT 3 A, 4 B FROM DUAL UNION ALL
  SELECT 4 A, 1 B FROM DUAL UNION ALL
  SELECT 6 A, 7 B FROM DUAL UNION ALL
  SELECT 2 A, 7 B FROM DUAL UNION ALL
  SELECT 8 A, 9 B FROM DUAL )
SELECT LEVEL, A, B FROM VALS
 START WITH A = 1 -- предположим, ищем связанные с этой вершиной рёбра
CONNECT BY NOCYCLE PRIOR B = A
ORDER BY LEVEL, A;

我能得到什么：

LEVEL, A, B
1,1,5
1,1,2
1,1,6 -- Первый вход вершины 6
2,2,7
2,2,6 -- Второй вход вошедшей вершины 6
2,2,3
2,6,7 -- Первое упоминание ребра
3,3,4
3,6,7 -- Второе упоминание ребра
4,4,1
5,1,5
5,1,6
6,6,7 -- Третье упоминание ребра

但由于某种原因，5、1、2 没有重复。

我想得到什么：

和/或相关顶点的列表

VERTEX_NAME
1
2
3
4
5
6
7

和/或不重复提及已包含的顶点的边列表

LEVEL, A, B
1,1,5
1,1,2
1,1,6
2,2,7
2,2,3
3,3,4
sql

2 个回答

  1. 如果你制作边链，那么当边重复时，预言机就会停止，但它可以多次经过同一个顶点。
    为了降低复杂性，您需要在重复顶点时切断链，而不是边。
    为此，您可以将顶点添加到边列表中并收集链，交替顶点和边。

    with vals as (...)
select distinct 
    a
from 
(   -- если оба числа не null - это ребро
    select a, b from vals where a <> b
    union 
    -- если второе число null - это вершина
    select a, null from vals 
    union 
    select b, null from vals
)
start with 
    a = 1 and b is null -- начинаем с вершины (1, null)
connect by nocycle 
    -- к вершине (prior a, null) цепляем ребро (a, b)
    prior b is null and b is not null and prior a in (a, b)
    or 
    -- к ребру (prior a, prior b) цепляем вершину (a, null)
    prior b is not null and b is null and a in (prior a, prior b)
order by a
    • 2
  2. Best Answer

    上面的答案通常是有效的，但它的复杂性增加得很快。如果您采用 11 个顶点并将每个顶点连接起来，那么在某个时刻，RAM 中将有数千万行。这是我的要求。它在大约1.5秒内“吞掉”了所描述的图（对于这样的图，我什至10分钟都没有等待上面算法的实现）。

    WITH
    vals AS (SELECT t_a.a
                  , t_b.b
               FROM (SELECT level AS a FROM dual CONNECT BY level <= 11) t_a
               CROSS JOIN (SELECT level AS b FROM dual CONNECT BY level <= 11) t_b)
  , snowflakes
      AS (SELECT ',' || listagg(decode(vertices.a, edges.b, edges.a, edges.a, edges.b), ',')
                                WITHIN GROUP ( ORDER BY decode(vertices.a, edges.b, edges.a, edges.a, edges.b)) ||
                 ',' AS gr
               , vertices.a AS core
            FROM (SELECT DISTINCT least(a, b) AS a, greatest(a, b) AS b FROM vals) edges
            JOIN (SELECT a FROM vals UNION SELECT b FROM vals) vertices ON vertices.a = edges.a OR vertices.a = edges.b
           GROUP BY vertices.a)
  , burning_graph (gr, core_str, lvl)
      AS (SELECT s.gr
               , to_char(s.core) AS core_str
               , 1 AS lvl
            FROM snowflakes s
           WHERE core = 3 -- !! Вот тут выбираем с какой вершины начать поиск
           UNION ALL
          SELECT ',' ||
                 (SELECT listagg(value, ',') WITHIN GROUP (ORDER BY to_number(value)) AS sorted_result
                    FROM (SELECT regexp_substr(combined_str, '[^,]+', 1, level) AS value
                            FROM (SELECT listagg(value, ',') WITHIN GROUP (ORDER BY to_number(value)) AS combined_str
                                    FROM (SELECT regexp_substr(r.gr || s.gr, '[^,]+', 1, level) AS value
                                            FROM dual
                                         CONNECT BY level <= length(r.gr || s.gr) - length(replace(r.gr || s.gr, ',')) + 1)
                                   WHERE value IS NOT NULL)
                         CONNECT BY level <= length(combined_str) - length(replace(combined_str, ',')) + 1
                           MINUS
                          SELECT regexp_substr(r.core_str || ',' || to_char(s.core), '[^,]+', 1,level) AS value
                            FROM dual
                         CONNECT BY level <= length(r.core_str || ',' || to_char(s.core)) -
                                             length(replace(r.core_str || ',' || to_char(s.core), ',')) +
                                             1)
                   WHERE value IS NOT NULL) || ',' AS gr
               , r.core_str || ',' || to_char(s.core) AS core_str
               , r.lvl + 1 AS lvl
            FROM burning_graph r
            JOIN snowflakes s ON r.gr LIKE ',' || s.core || ',%')
  , subgraph_result AS (SELECT to_number(regexp_substr(b.core_str, '[^,]+', 1, level)) AS vertex_num
                          FROM (select core_str from burning_graph WHERE lvl = (SELECT max(lvl) FROM burning_graph)) b
                       CONNECT BY level <= length(b.core_str) - length(replace(b.core_str, ',')) + 1)
  SELECT * FROM subgraph_result ORDER BY vertex_num;

    当然，您可以尝试使用更复杂的图，以确保算法不仅仅拉出所有顶点：

    WITH
  vals AS (SELECT 1 AS a, 2 AS b FROM dual UNION ALL
           SELECT 2 AS a, 5 AS b FROM dual UNION ALL
           SELECT 3 AS a, 5 AS b FROM dual UNION ALL
           SELECT 6 AS a, 5 AS b FROM dual UNION ALL
           SELECT 3 AS a, 4 AS b FROM dual UNION ALL
           SELECT 7 AS a, 8 AS b FROM dual)

    这就是它的样子（上次我从顶点 2 开始，所以它是有色的）： 例子

    • 0

相关问题