来自多对多的递归查询 table

Question

在 As 到 Bs 的多对多映射 table 中，假设有一个初始条件 f(A, B) -> bool，该映射中的一些 (A, B) 对 table满足。

问题是 select 所有对，其中对中的 A 出现在满足条件的集合中，或者对中的 B 出现在满足条件的集合中。然后继续以这种方式扩展 select 集，直到不再添加不同的对为止，因此在最后，selection 包含您可以从中“走到”满足初始条件的对的所有对条件。

示例：

A_id    B_id
------------
 A1      B1
 A1      B3
 A2      B1
 A2      B2

假设 (A2, B1) 和 (A2, B2) 满足 f，而 (A1, B1) 和 (A1, B3) 不满足。不过，我需要返回的集合包含所有四对，因为 B1 出现在满足 f 的集合中（所以我们包括 (A1, B1)）并且 A1 现在出现在增长的集合中（所以我们包括 (A1 , B3)).

在服务器端执行此操作的正确方法是什么？在服务器上执行此操作是否比在客户端存储一些中间结果并在多个 "incremental" 查询中执行递归更好？当行数很大时，答案如何变化？

（我需要在 SQL 服务器中执行此操作，但这不是问题所必需的。）

伪查询语言的示例解决方案：

declare @results table(A_id, B_id)

-- initial set, satisfying the condition
insert into @results -- adds (A2, B1) and (A2, B2)
select A_id, B_id from mapping m where f(A_id, B_id) == true

-- first round of recursion
insert into @results
select m.A_id, r.B_id from mapping m -- adds (A1, B1)
join @results r on r.B_id = m.B_id
insert into @results
select r.A_id, m.B_id from mapping m
join @results r on r.A_id = m.B_id

-- second round of recursion
insert into @results
select m.A_id, r.B_id from mapping m
join @results r on r.B_id = m.B_id
insert into @results
select r.A_id, m.B_id from mapping m -- adds (A1, B3)
join @results r on r.A_id = m.B_id

Answer 1

如果在 table 中添加第三列给出 f 值，则可以使用此查询。

with CTE as 
(
    Select A_ID as Node, Path = CAST(a_id as nvarchar(max))
    from Link
    where f = 1

    UNION

    Select B_ID as Node, Path = CAST(B_ID as nvarchar(max))
    from Link
    where f = 1

    UNION ALL

    Select L.B_ID, CTE.Path + '-' + L.B_ID
    from CTE inner join Link L ON CTE.node = L.A_ID
    where CTE.path not like '%' + L.B_ID +'%'

    UNION ALL

    Select L.A_ID, CTE.Path + '-' + L.A_ID
    from CTE inner join Link L ON CTE.node = L.B_ID
    where CTE.path not like '%' + L.A_ID +'%'
)
select distinct Node from CTE

来自多对多的递归查询 table

Recursive query from a many-to-many table

sql

recursion

many-to-many