Как сгруппировать узлы с отношениями в SQL

Question

У меня есть следующая таблица, в которой перечислены связанные узлы:

;WITH CTE AS
( SELECT *
  FROM (VALUES (1,2)
              ,(2,1)
              ,(3,4)
              ,(3,5)
              ,(4,3)
              ,(4,5)
              ,(5,3)
              ,(5,4)
              ,(6,NULL)
              ,(7,NULL)
              ,(8,9)
              ,(9,8)
        ) AS ValuesTable(ID,RelatedID)
)
SELECT *
FROM CTE

Как я могу назначить уникальный IDS (GUID или целочисленный GroupID) для каждой группы, поэтому 1 и 2 будут в одной группе,3, 4, 5 в другой группе, 6 в своей группе один, и 7 тоже, а 8 и 9 - еще одна группа?

Мой ответ пока кажется очень громоздким:

;WITH CTE AS
( SELECT *
  FROM (VALUES (1,2)
              ,(2,1)
              ,(3,4)
              ,(3,5)
              ,(4,3)
              ,(4,5)
              ,(5,3)
              ,(5,4)
              ,(6,NULL)
              ,(7,NULL)
              ,(8,9)
              ,(9,8)
        ) AS ValuesTable(ID,RelatedID)
)
SELECT DENSE_RANK() OVER(ORDER BY CA.IDList) AS GroupID,
       ID,
       RelatedID
FROM CTE
CROSS APPLY (SELECT STUFF((SELECT ',' + CONVERT(NVARCHAR(255), ID)
             FROM CTE AS CTEInner
             WHERE CTEInner.ID = CTE.ID
                OR CTEInner.ID = CTE.RelatedID
                OR CTEInner.RelatedID = CTE.RelatedID
                OR CTEInner.RelatedID = CTE.ID
             FOR XML PATH(''),TYPE).value('(./text())[1]','NVARCHAR(MAX)'),1,1,'') AS IDList) AS CA

Но он дает правильный ответ:

GroupID ID  RelatedID
1   1   2
1   2   1
2   3   4
2   3   5
2   4   3
2   4   5
2   5   3
2   5   4
3   6   NULL
4   7   NULL
5   8   9
5   9   8

Answer 1

Это проблема с ходьбой по графику, и вам могут понадобиться рекурсивные CTE.Логика выглядит следующим образом:

WITH t AS (
      SELECT *
      FROM (VALUES (1,2)
              ,(2,1)
              ,(3,4)
              ,(3,5)
              ,(4,3)
              ,(4,5)
              ,(5,3)
              ,(5,4)
              ,(6,NULL)
              ,(7,NULL)
              ,(8,9)
              ,(9,8)
        ) AS ValuesTable(ID,RelatedID)
    ),
         cte as (
          select distinct id, id as relatedId, ',' + convert(varchar(max), id) + ','  as relatedIds
          from t
          union all
          select cte.id, t.relatedId,  cte.relatedIds + convert(varchar(max), t.relatedId) + ','
          from cte join
               t
               on cte.relatedId = t.id
          where cte.relatedId is not null and
                cte.relatedIds not like '%,' + convert(varchar(max), t.relatedId) + ',%'
         )
SELECT id, min(relatedId) as grp,
       dense_rank() over (order by min(relatedId)) as grp_number
FROM cte
GROUP BY id;

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

Answer 2

Добавление уникального номера для каждой группы не сложно, но требует нескольких шагов.

Первым шагом будет выбор уникальных значений для групп - например, группа с (1, 2) и(2, 1) будет содержать только одну запись - (1, 2).

Следующий шаг - избавиться от записей, создающих несколько путей для одной и той же связи - в данном случае - (3, 4), (4, 5), (3, 5) - означает, что 5 относится как к 3, так и к 4, но для работы рекурсивного cte нам нужен только один путь отношений - так что либо (3, 4), (4, 5), либо (3, 4), (3, 5), но не оба.

Следующим шагом является создание рекурсивного cte на основе этих уникальных значений, чтобы каждая группа могла получить свой уникальный номер.

После этого вы можете выбрать исходный cte, присоединенный к рекурсивному cte, и получить уникальныйномера групп:

;WITH CTE AS
( SELECT *
  FROM (VALUES (1,2)
              ,(2,1)
              ,(3,4)
              ,(3,5)
              ,(4,3)
              ,(4,5)
              ,(5,3)
              ,(5,4)
              ,(6,NULL)
              ,(7,NULL)
              ,(8,9)
              ,(9,8)
        ) AS ValuesTable(ID,RelatedID)
)
, PreUniqueValues AS
(
    SELECT  MIN(ID) AS ID, 
            MAX(RelatedID) As RelatedID
    FROM CTE AS B
    GROUP BY (ID + ISNULL(RelatedID, 0)) + (ID * ISNULL(RelatedID, 0))
)
, UniqueValues AS
(
    SELECT ID, MIN(RelatedID) As RelatedID
    FROM PreUniqueValues 
    GROUP BY ID
)
, Recursive AS
(
    SELECT ID, RelatedId, DENSE_RANK() OVER(ORDER BY ID) As GroupID
    FROM UniqueValues AS T0
    WHERE NOT EXISTS
    (
        SELECT 1
        FROM UniqueValues AS T1
        WHERE T1.ID = T0.RelatedID
    )
    UNION ALL
    SELECT UV.ID, UV.RelatedID, GroupID
    FROM UniqueValues As UV
    JOIN Recursive As Re 
        ON UV.ID = Re.RelatedId
)

SELECT CTE.ID, CTE.RelatedID, GroupID
FROM CTE
JOIN Recursive 
    ON CTE.ID = Recursive.ID OR CTE.ID = ISNULL(Recursive.RelatedID, 0)
ORDER BY ID

Результаты:

ID  RelatedID   GroupID
1   2           1
2   1           1
4   3           2
4   5           2
5   3           2
5   4           2
6   NULL        3
7   NULL        4
8   9           5
9   8           5