递归 SQL 查询以查找所有匹配的标识符

Question

我有一个 table 具有以下结构

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

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

源和结果示例 tables:

Source table 基本上存储哪个 ID 与另一个 ID 匹配。从图中可以看出，1、2、3、4、5 是相同的。而6、7是相同的。我需要一个 SQL 查询来获得一个结果 table，其中包含 ID 之间的所有匹配项。

我在网站上找到了这个项目 - Recursive query in SQL Server 与我的任务类似，但结果不同。

我试图为我的任务编辑代码，但它不起作用。 "The statement terminated. The maximum recursion 100 has been exhausted before statement completion."

;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

这是一种通过暴力获取输出的方法，但可能不是 different/larger 数据集的最佳解决方案：

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;

Answer 2

这是一个具有挑战性的问题。您正在尝试从两个方向遍历图表。有两个关键思想：

添加 "reverse" 条边，因此图形的行为类似于有向图，但在两个方向上都有边。
保留已访问过的边的列表。在 SQL 服务器中，字符串是一种方法。

所以：

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

由于所有节点连接都是双向的 - 将反向关系添加到原始列表
从每个节点找到所有可能的路径；几乎是通常的递归，唯一的区别是 - 我们需要保留 root id1
避免循环 - 我们需要注意这一点，因为我们没有方向

来源：

;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

source table will contain about 100,000 records

没有什么可以帮助您的。任务很不愉快——找到所有可能的联系。差不多CROSS JOIN。最后连接更多。

Answer 4

看来我想出了与其他发帖人相似的答案。我的方法是插入现有的值对，然后插入每对的反向值。

展开值对列表后，您可以遍历 table 以找到所有对。

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

递归 SQL 查询以查找所有匹配的标识符

Recursive SQL query to find all matching identifiers

sql

sql-server

recursive-query

sql-server-2012