Ytukyg

I have the following table which lists related nodes:

;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

How can I assign unique IDS (GUID or integer GroupID) to each group, So, 1 and 2 will be on the same group, 3, 4, 5 on a different group, 6 is alone in it's group and so is 7, and 8 and 9 are one more group?

My answer so far seems very cumbersome:

;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

But it provides the correct answer:

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

Adding a unique number for each group is not hard but it does require a few steps.

The first step would be to select unique values for the groups - so for instance the group with (1, 2) and (2, 1) will contain only a single record - (1, 2).

The next step is to get rid of the records that creates multiple paths for the same relationship - in this case - (3, 4), (4, 5), (3, 5) - means that 5 is the related to both 3 and 4, but for the recursive cte to work, we only need a single relationship path - so either (3, 4), (4, 5) or (3, 4), (3, 5) but not both.

The next step is to create a recursive cte based on these unique values, so that each group can get it's unique number.

After that, you can select from the original cte joined to the recursive cte and get the unique group numbers:

;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

Results:

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

This is a graph-walking problem and you would seem to need recursive CTEs. The logic looks like this:

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;

Here is a db<>fiddle.