Некоторое время назад я написал ответ на вопрос Как найти все связные подграфы неориентированного графа .Он был написан для SQL Server, но Oracle поддерживает стандартные рекурсивные запросы, поэтому было легко преобразовать его в Oracle.Он может быть написан более эффективно с использованием конструкций, специфичных для Oracle.
Пример данных
create table link_tbl as (
select 'AY' as linkid, 'A' as from_node, 'Y' as to_node from dual union all
select 'AB', 'A', 'B' from dual union all
select 'CA', 'C', 'A' from dual union all
select 'GE', 'G', 'E' from dual union all
select 'CB', 'C', 'B' from dual union all
select 'EF', 'E', 'F' from dual union all
select 'NM', 'N', 'M' from dual
);
Запрос
WITH
CTE_Nodes
AS
(
SELECT from_node AS Node
FROM link_tbl
UNION
SELECT to_node AS Node
FROM link_tbl
)
,CTE_Pairs
AS
(
SELECT from_node AS Node1, to_node AS Node2
FROM link_tbl
WHERE from_node <> to_node
UNION
SELECT to_node AS Node1, from_node AS Node2
FROM link_tbl
WHERE from_node <> to_node
)
,CTE_Recursive (AnchorNode, Node1, Node2, NodePath, Lvl)
AS
(
SELECT
CAST(CTE_Nodes.Node AS varchar(2000)) AS AnchorNode
, Node1
, Node2
, CAST(',' || Node1 || ',' || Node2 || ',' AS varchar(2000)) AS NodePath
, 1 AS Lvl
FROM
CTE_Pairs
INNER JOIN CTE_Nodes ON CTE_Nodes.Node = CTE_Pairs.Node1
UNION ALL
SELECT
CTE_Recursive.AnchorNode
, CTE_Pairs.Node1
, CTE_Pairs.Node2
, CAST(CTE_Recursive.NodePath || CTE_Pairs.Node2 || ',' AS varchar(2000)) AS NodePath
, CTE_Recursive.Lvl + 1 AS Lvl
FROM
CTE_Pairs
INNER JOIN CTE_Recursive ON CTE_Recursive.Node2 = CTE_Pairs.Node1
WHERE
CTE_Recursive.NodePath NOT LIKE CAST('%,' || CTE_Pairs.Node2 || ',%' AS varchar(2000))
)
,CTE_RecursionResult
AS
(
SELECT AnchorNode, Node1, Node2
FROM CTE_Recursive
)
,CTE_CleanResult
AS
(
SELECT AnchorNode, Node1 AS Node
FROM CTE_RecursionResult
UNION
SELECT AnchorNode, Node2 AS Node
FROM CTE_RecursionResult
)
SELECT
CTE_Nodes.Node
,LISTAGG(CTE_CleanResult.Node, ',') WITHIN GROUP (ORDER BY CTE_CleanResult.Node) AS GroupMembers
,DENSE_RANK() OVER (ORDER BY LISTAGG(CTE_CleanResult.Node, ',') WITHIN GROUP (ORDER BY CTE_CleanResult.Node)) AS GroupID
FROM
CTE_Nodes
INNER JOIN CTE_CleanResult ON CTE_CleanResult.AnchorNode = CTE_Nodes.Node
GROUP BY
CTE_Nodes.Node
ORDER BY
GroupID
,CTE_Nodes.Node
;
Результат
+------+--------------+---------+
| NODE | GROUPMEMBERS | GROUPID |
+------+--------------+---------+
| A | A,B,C,Y | 1 |
| B | A,B,C,Y | 1 |
| C | A,B,C,Y | 1 |
| Y | A,B,C,Y | 1 |
| E | E,F,G | 2 |
| F | E,F,G | 2 |
| G | E,F,G | 2 |
| M | M,N | 3 |
| N | M,N | 3 |
+------+--------------+---------+
https://dbfiddle.uk/?rdbms=oracle_11.2&fiddle=e61cf73824e7718a4686430ccd7398e7
Как это работает
CTE_Nodes
CTE_Nodes дает список всех узлов, которые отображаются в столбцах from_node и to_node.Поскольку они могут появляться в любом порядке, мы UNION оба столбца вместе.UNION также удаляет все дубликаты.
+------+
| NODE |
+------+
| A |
| B |
| C |
| E |
| F |
| G |
| M |
| N |
| Y |
+------+
CTE_Pairs
CTE_Pairs дает список всех ребер графика в обоих направлениях.Опять же, UNION используется для удаления любых дубликатов.
+-------+-------+
| NODE1 | NODE2 |
+-------+-------+
| A | B |
| A | C |
| A | Y |
| B | A |
| B | C |
| C | A |
| C | B |
| E | F |
| E | G |
| F | E |
| G | E |
| M | N |
| N | M |
| Y | A |
+-------+-------+
CTE_Recursive
CTE_Recursive - это основная часть запроса, которая рекурсивно пересекаетграфик, начиная с каждого уникального узла.Эти начальные строки создаются первой частью UNION ALL.Вторая часть UNION ALL рекурсивно присоединяется к себе, связывая Node2 с Node1.Поскольку мы предварительно сделали CTE_Pairs со всеми ребрами, написанными в обоих направлениях, мы всегда можем связать только Node2 с Node1, и мы получим все пути на графике.В то же время запрос создает NodePath - строку узлов, разделенных запятыми, которые были пройдены до сих пор.Он используется в фильтре WHERE:
CTE_Recursive.NodePath NOT LIKE CAST('%,' || CTE_Pairs.Node2 || ',%' AS varchar(2000))
Как только мы сталкиваемся с узлом, который был включен в путь ранее, рекурсия прекращается, когда список подключенных узлов исчерпан.AnchorNode является начальным узлом для рекурсии, он будет использоваться позже для группировки результатов.Lvl на самом деле не используется, я включил его для лучшего понимания происходящего.
+------------+-------+-------+-----------+-----+
| ANCHORNODE | NODE1 | NODE2 | NODEPATH | LVL |
+------------+-------+-------+-----------+-----+
| A | A | Y | ,A,Y, | 1 |
| A | A | C | ,A,C, | 1 |
| A | A | B | ,A,B, | 1 |
| B | B | C | ,B,C, | 1 |
| B | B | A | ,B,A, | 1 |
| C | C | B | ,C,B, | 1 |
| C | C | A | ,C,A, | 1 |
| E | E | G | ,E,G, | 1 |
| E | E | F | ,E,F, | 1 |
| F | F | E | ,F,E, | 1 |
| G | G | E | ,G,E, | 1 |
| M | M | N | ,M,N, | 1 |
| N | N | M | ,N,M, | 1 |
| Y | Y | A | ,Y,A, | 1 |
| Y | A | B | ,Y,A,B, | 2 |
| C | A | B | ,C,A,B, | 2 |
| Y | A | C | ,Y,A,C, | 2 |
| B | A | C | ,B,A,C, | 2 |
| C | A | Y | ,C,A,Y, | 2 |
| B | A | Y | ,B,A,Y, | 2 |
| C | B | A | ,C,B,A, | 2 |
| A | B | C | ,A,B,C, | 2 |
| B | C | A | ,B,C,A, | 2 |
| A | C | B | ,A,C,B, | 2 |
| G | E | F | ,G,E,F, | 2 |
| F | E | G | ,F,E,G, | 2 |
| B | A | Y | ,B,C,A,Y, | 3 |
| C | A | Y | ,C,B,A,Y, | 3 |
| Y | B | C | ,Y,A,B,C, | 3 |
| Y | C | B | ,Y,A,C,B, | 3 |
+------------+-------+-------+-----------+-----+
CTE_CleanResult
CTE_CleanResult оставляет только актуальныечасти из CTE_Recursive и снова объединяет Node1 и Node2, используя UNION.
+------------+------+
| ANCHORNODE | NODE |
+------------+------+
| A | A |
| A | B |
| A | C |
| A | Y |
| B | A |
| B | B |
| B | C |
| B | Y |
| C | A |
| C | B |
| C | C |
| C | Y |
| E | E |
| E | F |
| E | G |
| F | E |
| F | F |
| F | G |
| G | E |
| G | F |
| G | G |
| M | M |
| M | N |
| N | M |
| N | N |
| Y | A |
| Y | B |
| Y | C |
| Y | Y |
+------------+------+
Окончательный выбор
Теперь нам нужно построитьстрока разделенных запятыми значений Node для каждого AnchorNode.LISTAGG делает это.DENSE_RANK() вычисляет GroupID числа для каждого AnchorNode.
Эффективность
У вас довольно большие таблицы, поэтому вы пытаетесь найти все группы сразу в одном запросе вышеможет быть весьма неэффективным.
Один из способов сделать его более эффективным - не использовать один запрос для всего набора данных.Не пытайтесь найти все подсети / группы одновременно.Ограничьте начальную точку одним узлом.Добавьте WHERE CTE_Nodes.Node = 'some node' к первой части CTE_Recursive.Запрос найдет все узлы одной подсети.Удалите эти найденные узлы из большой таблицы, выберите другой начальный узел, повторяйте в цикле, пока большая таблица не станет пустой.Если вы материализуете CTE_Nodes и CTE_Pairs как временные таблицы с индексами, это также может помочь.
Я никогда не работал с Oracle и не знаю его синтаксиса для процедурного кода, поэтому я напишув псевдокоде ниже.
Подготовка временных таблиц
CREATE TABLE Nodes AS
(
SELECT from_node AS Node
FROM link_tbl
UNION
SELECT to_node AS Node
FROM link_tbl
);
CREATE INDEX IX_Node ON Nodes (Node);
CREATE TABLE Pairs AS
(
SELECT from_node AS Node1, to_node AS Node2
FROM link_tbl
WHERE from_node <> to_node
UNION
SELECT to_node AS Node1, from_node AS Node2
FROM link_tbl
WHERE from_node <> to_node
);
CREATE INDEX IX_Node1 ON Pairs (Node1);
CREATE INDEX IX_Node2 ON Pairs (Node2);
CREATE TABLE Subgraph AS
(
SELECT Node FROM Nodes WHERE 1=0
);
CREATE TABLE Result
(
GroupID int NOT NULL,
Node varchar(10) NOT NULL
);
SET :GroupID = 0;
Основной цикл начинается
Выберите один Node из Nodes.Подойдет любая строка.Сохраните Node в переменную.Опять же, я не знаю правильный синтаксис Oracle для него.
SELECT :N = Node FROM Nodes WHERE rownum=1;
Если Nodes пуст, остановите цикл.
SET :GroupID = :GroupID + 1;
Запустите рекурсивный запрос, начиная рекурсию содин конкретный Node, выбранный выше.
INSERT INTO Subgraph (Node)
WITH
CTE_Recursive (AnchorNode, Node1, Node2, NodePath, Lvl)
AS
(
SELECT
CAST(Nodes.Node AS varchar(2000)) AS AnchorNode
, Node1
, Node2
, CAST(',' || Node1 || ',' || Node2 || ',' AS varchar(2000)) AS NodePath
, 1 AS Lvl
FROM
Pairs
INNER JOIN Nodes ON Nodes.Node = Pairs.Node1
WHERE
Nodes.Node = :N -- 'A'
-- use variable here, don't know what the syntax is
UNION ALL
SELECT
CTE_Recursive.AnchorNode
, Pairs.Node1
, Pairs.Node2
, CAST(CTE_Recursive.NodePath || Pairs.Node2 || ',' AS varchar(2000)) AS NodePath
, CTE_Recursive.Lvl + 1 AS Lvl
FROM
Pairs
INNER JOIN CTE_Recursive ON CTE_Recursive.Node2 = Pairs.Node1
WHERE
CTE_Recursive.NodePath NOT LIKE CAST('%,' || Pairs.Node2 || ',%' AS varchar(2000))
)
,CTE_Result
AS
(
SELECT Node1 AS Node
FROM CTE_Recursive
UNION
SELECT Node2 AS Node
FROM CTE_Recursive
)
SELECT Node FROM CTE_Result
;
Этот запрос вернет все узлы, которые связаны с данным начальным узлом, то есть те, которые образуют подграф.Сохраните его набор результатов в временную таблицу Subgraph.
Добавьте результат в итоговую таблицу Result и назначьте идентификатор найденному подграфу.
INSERT INTO Result (GroupID, Node)
SELECT :GroupID, Node
FROM Subgraph;
Удалите обработанные узлы из Nodes и Pairs.
DELETE FROM Nodes
WHERE Node IN (SELECT Node FROM Subgraph)
;
DELETE FROM Pairs
WHERE
Node1 IN (SELECT Node FROM Subgraph)
OR
Node2 IN (SELECT Node FROM Subgraph)
;
Очистить таблицу Subgraph
DELETE FROM Subgraph;
Вернуться к началу цикла.
В конце Result таблица будет иметь все узлы с соответствующим идентификатором подграфа.
На самом деле, вы можете еще больше упростить это.Вам не нужен стол Nodes, достаточно Pairs.