Как эффективно найти минимальный связанный идентификатор после применения транзитивности

Question

У меня очень большая таблица с идентификаторами переменных в двух столбцах.Я хотел бы найти минимальный связанный идентификатор после применения транзитивности.Например, если ID1 = 1 и ID2 = 2 для одной записи и ID1 = 2 и ID2 = 3 для другой записи, я бы хотел, чтобы результаты в конечном итоге дали три записи, где первый столбец имеет идентификатор (1, 2 и3) и второй столбец имеет Min_ID (все равны 1, в приведенном выше примере).

Я определил, что самое большее есть 6 способов, которыми могут быть связаны идентификаторы, и я считаю, что ниже приведенпример минимального функционирования.

Есть ли более эффективный способ сделать это?

Источник

| ID1  | ID2   |
|------|-------|
| 1    | 1     |
| 2    | 2     |
| 1    | 1     |
| 1    | 2     |
| 2    | 11    |
| 11   | 13    |
| 13   | 99    |
| 99   | 1000  |
| 1000 | 97887 |
| 3    | 5     |
| 5    | 17    |
| 17   | 19    |
| 23   | 34    |

Результаты

| ID    | Min_ID |
|-------|--------|
| 1     | 1      |
| 2     | 1      |
| 3     | 3      |
| 5     | 3      |
| 11    | 1      |
| 13    | 1      |
| 17    | 3      |
| 19    | 3      |
| 23    | 23     |
| 34    | 23     |
| 99    | 1      |
| 1000  | 1      |
| 97887 | 1      |

Функционирование, хотя и потенциально неэффективный рабочий пример:

IF OBJECT_ID('tempdb..##IDs') IS NOT NULL DROP TABLE ##IDs
GO

CREATE TABLE ##IDs
(
    ID1 int
    ,ID2 int
);

INSERT INTO ##IDs (ID1, ID2)
VALUES
    (1, 1),
    (2, 2),
    (1, 1),
    (1, 2),
    (2, 11),
    (11, 13),
    (13, 99),
    (99, 1000),
    (1000, 97887),
    (3, 5),
    (5, 17),
    (17, 19),
    (23, 34)
;

WITH t1 AS
(
    SELECT
        ID1
        ,ID2
    FROM ##IDs

    UNION

    SELECT
        ID2
        ,ID1
    FROM ##IDs
),

t2 AS
(
    SELECT
    *
    FROM t1

    UNION

    SELECT
        a.ID1
        ,b.ID2
    FROM t1 a
    LEFT JOIN t1 b ON
        a.ID2 = b.ID1

    UNION

    SELECT
        b.ID2
        ,a.ID1
    FROM t1 a
    LEFT JOIN t1 b ON
        a.ID2 = b.ID1
),

t3 AS
(
    SELECT
    *
    FROM t2

    UNION

    SELECT
        a.ID1
        ,b.ID2
    FROM t2 a
    LEFT JOIN t2 b ON
        a.ID2 = b.ID1

    UNION

    SELECT
        b.ID2
        ,a.ID1
    FROM t2 a
    LEFT JOIN t2 b ON
        a.ID2 = b.ID1
),

t4 AS
(
    SELECT
    *
    FROM t3

    UNION

    SELECT
        a.ID1
        ,b.ID2
    FROM t3 a
    LEFT JOIN t3 b ON
        a.ID2 = b.ID1

    UNION

    SELECT
        b.ID2
        ,a.ID1
    FROM t3 a
    LEFT JOIN t3 b ON
        a.ID2 = b.ID1
)

SELECT
    ID1 AS [ID]
    ,MIN(ID2) Min_ID
FROM t4
GROUP BY
    ID1

Answer 1

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

IF OBJECT_ID('tempdb..##IDs') IS NOT NULL DROP TABLE ##IDs
GO

CREATE TABLE ##IDs
(
    ID1 int
    ,ID2 int
);

INSERT INTO ##IDs (ID1, ID2)
VALUES
    (1, 1),
    (2, 2),
    (1, 1),
    (1, 2),
    (2, 11),
    (11, 13),
    (13, 99),
    (99, 1000),
    (1000, 97887),
    (3, 5),
    (5, 17),
    (17, 19),
    (23, 34)
;

WITH t1 AS
(
    SELECT
        ID1
        ,ID2
    FROM ##IDs

    UNION

    SELECT
        ID2
        ,ID1
    FROM ##IDs

    UNION ALL  

    SELECT
        c.ID1
        ,t1.ID2
    FROM ##IDs c
    INNER JOIN t1 ON
        c.ID2 = t1.ID1
    WHERE
        c.ID1 <> c.ID2

    UNION ALL  

    SELECT
        t1.ID2
        ,c.ID1
    FROM ##IDs c
    INNER JOIN t1 ON
        c.ID2 = t1.ID1
    WHERE
        c.ID1 <> c.ID2
)

SELECT
    ID1 AS [ID]
    ,MIN(ID2) Min_ID
FROM t1
GROUP BY
    ID1
;