Как избежать повторного извлечения данных в рекурсивном запросе?

Рейтинг: 2Ответов: 2Опубликовано: 16.08.2023

Предположим, у меня есть граф, вершины которого пронумерованы. В таблице я храню ребра графа, т.е. номера вершин начала и конца ребра. Как рекурсивным запросом извлечь все вершины, свазанные с переданной вершиной?

Граф

Как это пытаюсь сделать я:

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 oracle
Источник: Stack Overflow на русском

Ответы

▲ 0Принят

Ответ, расположенный веше в целом работает, но в нем очень быстро возрастает сложность. Есть взять 11 вершин и каждую соединить с каждой, то в какой-то момент в оперативной памяти будут десятки миллионов строк. Вот мой запрос. Описанный граф он "проглатывает" за примерно 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, поэтому она подкрашена): пример

▲ 2

Если составлять цепочки из рёбер, то оракл остановится при повторении ребра, при этом он может проходить одну и ту же вершину несколько раз.
Чтобы снизить сложность, нужно отсекать цепочку при повторении вершины, а не ребра.
Для этого можно в список рёбер добавить вершины и собирать цепочки, чередуя вершины и рёбра.

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