many-to-many 테이블에서 재귀 쿼리

Question

Bs에서 As의 many-to-many 매핑 테이블에서 초기 조건이 f(A, B) -> bool이고,이 매핑 ​​테이블의 (A, B) 쌍이 만족한다고 말합니다.

문제는 쌍을 이루는 A가 조건을 만족하는 집합에 나타나거나 쌍의 B가 조건을 만족하는 집합에 나타나는 모든 쌍을 선택하는 것입니다. 그런 다음 뚜렷한 쌍이 더 이상 추가되지 않을 때까지 선택 집합을 계속 확장하면 결국 선택 항목에는 초기 조건을 만족하는 쌍으로 "걸을 수있는"모든 쌍이 포함됩니다.

예 :

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은 증가하는 집합에 포함됩니다) (A1, B3을 포함하므로) 반환 된 집합에 네 쌍을 모두 포함해야합니다. .

이 서버 측을 수행하는 올바른 방법은 무엇입니까? 클라이언트에서 중간 결과를 저장하고 여러 "증분"쿼리에서 재귀를 수행하는 것보다 서버에서 더 잘 수행하고 있습니까? 행 수가 매우 큰 경우 어떻게 대답이 변경됩니까?

(I는 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

을 당신이를 제공하는 세 번째 열을 추가하는 경우 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