Группировка «групп» с общим элементом - PullRequest
Новая
       45

Группировка «групп» с общим элементом

1 голос
/ 01 марта 2020

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

group_id | value
---------+-------
1        | A
1        | B
2        | C
2        | D
2        | A
3        | E
3        | C
4        | G
4        | H

То, что я хочу получить, - это уникальный номер для каждой группы, которая каким-либо образом связана ... как это:

Группа 1 и 2 имеют общий элемент A, Группа 1 и 3 имеют общий элемент C>, так что это фактически одна большая группа. 

master_id | group_id | value
----------+----------+--------
1         | 1        | A
1         | 1        | B
1         | 2        | C
1         | 2        | D
1         | 2        | A
1         | 3        | E
1         | 3        | C
2         | 4        | G
2         | 4        | H

Как я могу получить это master_id

Ответы [ 2 ]

3 голосов
/ 02 марта 2020

Вычисление мастер-группы - это проблема хождения по графику, которая подразумевает рекурсивное CTE. Я хотел бы подойти к этому следующим образом:

  • Создание ребер между группами на основе значений.
  • Обход ребер без посещения предыдущих групп.

тогда расчет основной группы является минимумом посещенных групп для каждой группы.

В SQL это выглядит так: 

with edges as (
      select distinct t1.group_id as group_id_1, t2.group_id as group_id_2
      from t t1  join
           t t2
           on t1.value = t2.value
     ),
     cte as (
      select e.group_id_1, e.group_id_2, convert(varchar(max), concat(',', group_id_1, ',', group_id_2)) as visited, 1 as lev
      from edges e
      union all
      select cte.group_id_1, e.group_id_2, 
             concat(visited, e.group_id_2, ','), lev + 1
      from cte join
           edges e
           on e.group_id_1 = cte.group_id_2
      where cte.visited not like concat('%,', e.group_id_2, ',%') and lev < 5
     )
select group_id_1, dense_rank() over (order by min(group_id_2)) as master_group
from cte
group by group_id_1;

Здесь - это дб <> скрипку.

1 голос
/ 02 марта 2020

Sql сервер пример : 

WITH GetConnected AS (
  SELECT DISTINCT g1.group_id sourceGroup, g2.group_id connectedGroup
  FROM @groups g1
  LEFT JOIN @groups g2
    ON g1.value = g2.value
  UNION ALL
  SELECT g1.group_id sourceGroup, g3.connectedGroup connectedGroup
  FROM @groups g1
  INNER JOIN @groups g2
    ON g1.value = g2.value
    AND g1.group_id < g2.group_id
  INNER JOIN GetConnected g3
    ON g3.sourceGroup = g2.group_id
    AND g3.connectedGroup > g2.group_id
), GetGroups AS (
  SELECT MIN(sourceGroup) sourceGroup, connectedGroup, DENSE_RANK() OVER (ORDER BY MIN(sourceGroup)) rk
  FROM GetConnected
  GROUP BY connectedGroup)

SELECT gg.rk master_id, g.group_id, g.value
FROM GetGroups gg
INNER JOIN @groups g
  ON gg.connectedGroup = g.group_id
ORDER BY gg.rk, gg.connectedGroup, g.value

Если учесть postgre, у меня есть пример кода : 

WITH RECURSIVE GetConnected AS (
  SELECT DISTINCT g1.group_id sourceGroup, g2.group_id connectedGroup
  FROM groups g1
  LEFT JOIN groups g2
    ON g1.value = g2.value
  UNION
  SELECT g1.group_id sourceGroup, g3.connectedGroup connectedGroup
  FROM groups g1
  LEFT JOIN groups g2
    ON g1.value = g2.value
  INNER JOIN GetConnected g3
    ON g3.sourceGroup = g2.group_id
), GetGroups AS (
  SELECT MIN(sourceGroup) sourceGroup, connectedGroup, DENSE_RANK() OVER (ORDER BY MIN(sourceGroup)) rk
  FROM GetConnected
  GROUP BY connectedGroup)

SELECT gg.rk master_id, g.group_id, g.value
FROM GetGroups gg
INNER JOIN groups g
  ON gg.connectedGroup = g.group_id
ORDER BY gg.rk, gg.connectedGroup, g.value
...