Как сгруппировать/перечислить все узлы неориентированного графа с помощью teradata sql

У меня есть данные для многих дифф. набор неориентированных графов в таблице (например, отношения смежных списков, один узел соединен со всеми узлами), и мне нужно сгруппировать все отдельные неориентированные графы.

Например: все узлы конкретных неориентированных графов будут в группе, и имя группы будет мин. узла.

sel d.adj_node, min(d.adj_node) Over (Partition By a.node) as grp
table a 
left join table b
on a.adj_node=b.node
left join table c
on b.adj_node=c.node
​left join table d
​on c.adj_node=d.node​;

Теперь я выполняю самообъединение 4,5 раза, а затем поверх этого запроса делаю его разбиение, чтобы получить желаемый результат. Но выполнение самосоединения 4 5 раз создает проблемы с производительностью.

Итак, вам нужен рекурсивный sql, хранимая процедура или какая-то другая логика, чтобы сделать то же самое для всех уровней. Входные данные и необходимые выходные данные будут выглядеть следующим образом: ссылка Ждем некоторых предложений.

Input Table

node    adj_node
1       2
2       1
2       3
2       5
2       6
2       7
3       2
3       4
4       3
4       5
4       6
4       7
5       2
5       4
6       2
6       4
6       8
7       2
7       4
8       6
1       1
2       2
3       3
4       4
5       5
6       6
7       7
8       8
10      11
11      10
11      13
11      14
12      13
12      14
13      11
13      12
13      14
14      11
14      12
14      13
10      10
11      11
12      12
13      13
14      14


Output
node    grp
1       1
2       1
3       1
4       1
5       1
6       1
7       1
8       1
10      10
11      10
12      10
13      10
14      10

sql stored-procedures teradata recursive-query undirected-graph
person ITIB    schedule 18.02.2016    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Я только что вспомнил, что делал что-то подобное, прежде чем использовать обновления для временной таблицы.

Лучшим способом реализовать это будет хранимая процедура с циклом в ней:

CREATE VOLATILE TABLE vt_tab AS
 (
   SELECT DISTINCT NODE , adj_node, NODE AS grp
   FROM tab AS t1
   WHERE adj_node <> NODE
 ) WITH DATA
ON COMMIT PRESERVE ROWS
;

-- REPEAT this update UNTIL activity_count = 0
UPDATE vt_tab FROM
 ( 
  SELECT t2.NODE, MIN(t1.grp) AS mingrp
  FROM vt_tab AS t1 JOIN vt_tab AS t2
  ON t1.adj_node = t2.NODE
  AND t1.grp < t2.grp
  GROUP BY t2.NODE
 ) x
SET grp = mingrp
WHERE vt_tab.NODE = x.NODE
;

--get the final result
SEL DISTINCT NODE,grp
FROM vt_tab
ORDER BY 1
;

Рекурсия может быть возможна, но есть высокая вероятность того, что она взорвет вашу катушку, потому что вам нужны повторные соединения m:n, и только окончательный выбор позволяет уменьшить количество строк результата.

person dnoeth    schedule 18.02.2016
comment
@Biti - Тогда вам нужно пометить его как ответ, установив галочку слева от этого ответа. - person Pரதீப்; 20.02.2016
comment
@dnoeth - у меня логика/код работает нормально, но мне сложно понять логику внутри обновления. Можете ли вы кратко объяснить алгоритм, который используется в обновлении? - person ITIB; 23.02.2016
comment
@Biti: Просто запустите часть SELECT, и вы увидите, что это имитирует рекурсию, объединяет два уровня в иерархии, находит наименьшее значение grp для каждого узла и назначает его всем строкам - person dnoeth; 23.02.2016

arrow_upward
0
arrow_downward

Решение с рекурсивным CTE:

with cte as
(
    select node as node, node as grp
    from Tabl_1
    Union all
    select C.node, T.adj_node
    from CTE C inner join Tabl_1 T on C.grp = T.node
    where T.adj_node < C.grp
)

select node, MIN(grp) as grp 
from cte
group by node
order by node

== РЕДАКТИРОВАТЬ 1 == Вот новая версия, отражающая вашу точку зрения.

with cte as
(
    select node as node, node as grp, ',' + CAST(node as varchar(max)) + '-' + CAST(node as varchar(max)) + ',' as pair
    from Tabl_1
    Union all
    select C.node, T.adj_node, C.pair + CAST(C.node as varchar(max)) + '-' + CAST(T.adj_node as varchar(max)) + ','
    from CTE C inner join Tabl_1 T on C.grp = T.node
    where C.pair not like '%,' + CAST(C.node as varchar(max)) + '-' + CAST(T.adj_node as varchar(max)) + ',%'
)

select node, MIN(grp) as grp 
from cte
group by node
order by node
person Polux2    schedule 18.02.2016
comment
Спасибо за предложение. Он работает нормально, но у меня есть один набор неориентированного графа, где он создает две группы вместо одной, используя вашу логику. Я не могу понять, почему он создает 2 группы. Не могли бы вы рассказать мне о проблеме. Пожалуйста, найдите входные данные и графическую диаграмму. ссылка - person ITIB; 19.02.2016
comment
@Biti Я изменил свой сценарий в Edit 1, чтобы учесть ваше замечание. - person Polux2; 20.02.2016