Рекурсивный запрос SQL для поиска всех совпадающих идентификаторов

Question

У меня есть таблица со следующей структурой

CREATE TABLE Source
(
     [ID1] INT, 
     [ID2] INT
);

INSERT INTO Source ([ID1], [ID2]) 
VALUES (1, 2), (2, 3), (4, 5),
       (2, 5), (6, 7)

Пример таблиц источника и результата:

Исходная таблица в основномхранит, какой идентификатор совпадает с каким другим идентификатором.Из диаграммы видно, что 1, 2, 3, 4, 5 идентичны.И 6, 7 идентичны.Мне нужен SQL-запрос для получения таблицы результатов со всеми совпадениями между идентификаторами.

Я нашел этот элемент на сайте - Рекурсивный запрос в SQL Server похож на мою задачу, но с другимрезультат.

Я пытался отредактировать код для моей задачи, но он не работает.«Оператор завершен. Максимальная рекурсия 100 была исчерпана до завершения оператора.»

;WITH CTE
AS
(
    SELECT DISTINCT
        M1.ID1,
        M1.ID1 as ID2
    FROM Source M1
        LEFT JOIN Source M2
            ON M1.ID1 = M2.ID2
    WHERE M2.ID2 IS NULL
    UNION ALL
    SELECT
        C.ID2,
        M.ID1
    FROM CTE C
        JOIN Source M
            ON C.ID1 = M.ID1
)
SELECT * FROM CTE ORDER BY ID1

Большое спасибо за помощь!

Answer 1

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

Развернув список пар значений, вы можете пересечь таблицу, чтобы найти все пары.

CREATE TABLE #Source
    ([ID1] int, [ID2] int);

INSERT INTO #Source 
(
    [ID1]
    ,[ID2]
) 
VALUES   
(1, 2)
,(2, 3)
,(4, 5)
,(2, 5)
,(6, 7)

INSERT INTO #Source 
(
    [ID1]
    ,[ID2]
) 
SELECT 
    [ID2]
    ,[ID1] 
FROM #Source

;WITH expanded AS
(
    SELECT DISTINCT 
        ID1 = s1.ID1
        ,ID2 = s1.ID2
    FROM #Source s1
    LEFT JOIN #Source s2 ON s1.ID2 = s2.ID1

    UNION

    SELECT DISTINCT 
        ID1 = s1.ID1
        ,ID2 = s2.ID2
    FROM #Source s1
    LEFT JOIN #Source s2 ON s1.ID2 = s2.ID1
    WHERE s1.ID1 <> s2.ID2

)
,recur AS
(
    SELECT DISTINCT 
        e1.ID1
        ,e1.ID2
    FROM expanded e1
    LEFT JOIN expanded e2 ON e1.ID2 = e2.ID1
    WHERE e1.ID1 <> e1.ID2

    UNION ALL

    SELECT DISTINCT 
        e1.ID1
        ,e2.ID2
    FROM expanded e1
    INNER JOIN expanded e2 ON e1.ID2 = e2.ID1
    WHERE e1.ID1 <> e2.ID2
)
SELECT DISTINCT 
    ID1, ID2 
FROM recur
ORDER BY ID1, ID2

DROP TABLE #Source 

Answer 2

Это сложный вопрос.Вы пытаетесь пройти через график в двух направлениях.Есть две ключевые идеи:

• Добавить «обратные» ребра, чтобы график вел себя как орграф, но с ребрами в обоих направлениях.
• Сохраните список ребер, которые были посещены,В SQL Server строки представляют собой один метод.

Итак:

with s as (
      select id1, id2 from source
      union  -- on purpose
      select id2, id1 from source
     ),
     cte as (
      select s.id1, s.id2, ',' + cast(s.id1 as varchar(max)) + ',' + cast(s.id2 as varchar(max)) + ',' as ids
      from s
      union all
      select cte.id1, s.id2, ids + cast(s.id2 as varchar(max)) + ','
      from cte join
           s
           on cte.id2 = s.id1
      where cte.ids not like '%,' + cast(s.id2 as varchar(max)) + ',%'
     )
select *
from cte
order by 1, 2;

Вот это db <> fiddle .

Answer 3

1. Поскольку все соединения узлов являются двунаправленными - добавьте обратные отношения в исходный список
2. Найдите все возможные пути от каждого узла;почти обычная рекурсия, единственное отличие - нам нужно сохранить root id1
3. Избегать циклов - мы должны знать об этом, потому что у нас нет направлений

source:

;with src as(
  select id1, id2 from source
  union 
  -- reversed connections
  select id2, id1 from source
), rec as (
  select id1, id2, CAST(CONCAT('/', src.id1, '/', src.id2, '/') as varchar(8000)) path
  from src

  union all

  -- keep the root id1 from the start of each path
  select rec.id1, src.id2, CAST(CONCAT(rec.path, src.id2, '/') as varchar(8000))
  from rec
  -- usual recursion
  inner join src on src.id1 = rec.id2
  -- avoid cycles
  where rec.path not like CONCAT('%/', src.id2, '/%')
)
select id1, id2, path 
from rec
order by 1, 2

вывод

| id1 | id2 |      path |
|-----|-----|-----------|
|   1 |   2 |     /1/2/ |
|   1 |   3 |   /1/2/3/ |
|   1 |   4 | /1/2/5/4/ |
|   1 |   5 |   /1/2/5/ |
|   2 |   1 |     /2/1/ |
|   2 |   3 |     /2/3/ |
|   2 |   4 |   /2/5/4/ |
|   2 |   5 |     /2/5/ |
|   3 |   1 |   /3/2/1/ |
|   3 |   2 |     /3/2/ |
|   3 |   4 | /3/2/5/4/ |
|   3 |   5 |   /3/2/5/ |
|   4 |   1 | /4/5/2/1/ |
|   4 |   2 |   /4/5/2/ |
|   4 |   3 | /4/5/2/3/ |
|   4 |   5 |     /4/5/ |
|   5 |   1 |   /5/2/1/ |
|   5 |   2 |     /5/2/ |
|   5 |   3 |   /5/2/3/ |
|   5 |   4 |     /5/4/ |
|   6 |   7 |     /6/7/ |
|   7 |   6 |     /7/6/ |

http://sqlfiddle.com/#!18/76114/13

исходная таблица будет содержать около 100 000 записей

Естьничего, что может помочь вам в этом.Задача неприятная - найти все возможные связи.Почти CROSS JOIN.С еще большим количеством соединений в конце.

Answer 4

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

select sub1.rnk as ID1
,sub2.rnk as ID2
from
(
select a.*
,rank() over (partition by 1 order by id1, id2) as RNK
from source a
) sub1
cross join
(
select a.*
,rank() over (partition by 1 order by id1, id2) as RNK
from source a
) sub2
where sub1.rnk <> sub2.rnk
union all
select id1 as ID1
,id2 as ID2
from source
where id1 = 6
union all
select id2 as ID1
,id1 as ID2
from source
where id1 = 6;