반복적인 CTE 방문 노드를 여러 번 방지
https://stackoverflow.com/questions/829514
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
다음과 같은 간단한 DAG를 고려해보세요.
1->2->3->4
그리고 이를 설명하는 테이블 #bar(저는 SQL Server 2005를 사용하고 있습니다):
parent_id child_id
1 2
2 3
3 4
//... other edges, not connected to the subgraph above
이제 첫 번째 가장자리와 마지막 가장자리를 선택하는 다른 임의의 기준이 있다고 상상해보십시오.1->2 및 3->4.나는 이것을 사용하여 내 그래프의 나머지 부분을 찾고 싶습니다.
다음과 같이 재귀적 CTE를 작성할 수 있습니다. MSDN):
with foo(parent_id,child_id) as (
// anchor member that happens to select first and last edges:
select parent_id,child_id from #bar where parent_id in (1,3)
union all
// recursive member:
select #bar.* from #bar
join foo on #bar.parent_id = foo.child_id
)
select parent_id,child_id from foo
그러나 이로 인해 가장자리 3->4가 두 번 선택됩니다.
parent_id child_id
1 2
3 4
2 3
3 4 // 2nd appearance!
쿼리가 이미 설명된 하위 그래프로 반복되는 것을 방지하려면 어떻게 해야 합니까?쿼리의 "재귀 멤버" 부분에서 다음을 참조할 수 있다면 이를 달성할 수 있습니다. 지금까지 재귀 CTE에 의해 검색된 모든 데이터 (이미 방문한 노드를 제외하고 재귀 멤버에 나타내는 조건자를 제공합니다).하지만 다음에서 반환된 데이터에 액세스할 수 있다고 생각합니다. 마지막 반복 재귀 멤버의 경우에만 해당됩니다.
이러한 반복이 많으면 확장이 잘 되지 않습니다.이러한 불필요한 추가 재귀를 방지할 수 있는 방법이 있습니까?
원하는 결과를 얻기 위해 문의 마지막 줄에 "select independent"를 사용할 수 있지만 이것이 적용된 것 같습니다. ~ 후에 모든 (반복되는) 재귀가 완료되었으므로 이것이 이상적인 솔루션이라고 생각하지 않습니다.
편집하다 - hainstech는 시작 세트에 명시적으로 있었던 반복 하향 경로를 제외하는 조건자를 추가하여 반복을 중지할 것을 제안합니다.재귀만 where foo.child_id not in (1,3).이는 간단하기 때문에 위의 경우에만 작동합니다. 모든 반복 섹션은 노드의 앵커 세트 내에서 시작됩니다.그렇지 않은 일반적인 경우는 해결되지 않습니다.예를 들어, 위 세트에 가장자리 1->4 및 4->5를 추가하는 것을 고려해보세요.Edge 4->5는 제안된 조건자를 사용하더라도 두 번 캡처됩니다.:(
해결책
그만큼 CTE재귀 적입니다.
당신의 CTE초기 조건이 여러 번있어 재귀 스택도 다르며 다른 스택에서 한 스택의 정보를 사용할 수있는 방법이 없습니다.
예에서 재귀 스택은 다음과 같이 진행됩니다.
(1) - first IN condition
(1, 2)
(1, 2, 3)
(1, 2, 3, 4)
(1, 2, 3) - no more children
(1, 2) - no more children
(1) - no more children, going to second IN condition
(3) - second condition
(3, 4)
(3) - no more children, returning
보시다시피, 이러한 재귀 스택은 교차하지 않습니다.
방문한 값을 임시 테이블에 기록 할 수 있습니다. JOIN 유혹 가능한 각 값 과이 값이 발견되면이 값을 따르지 않지만 SQL Server 이러한 것들을지지하지 않습니다.
그래서 당신은 그냥 사용합니다 SELECT DISTINCT.
다른 팁
이것이 내가 사용한 접근법입니다. 그것은 몇 가지 방법에 대해 테스트되었으며 가장 성능이 가장 적었습니다. Quassnoi가 제안한 온도 테이블 아이디어와 재귀에 대한 중복 경로를 제거하기 위해 별개의 왼쪽 조인과 왼쪽 조인의 사용을 결합합니다. 재귀 수준도 포함됩니다.
코드에 실패한 CTE 접근 방식을 남겨 두어 결과를 비교할 수 있습니다.
누군가가 더 나은 아이디어를 가지고 있다면, 나는 그것을 알고 싶습니다.
create table #bar (unique_id int identity(10,10), parent_id int, child_id int)
insert #bar (parent_id, child_id)
SELECT 1,2 UNION ALL
SELECT 2,3 UNION ALL
SELECT 3,4 UNION ALL
SELECT 2,5 UNION ALL
SELECT 2,5 UNION ALL
SELECT 5,6
SET NOCOUNT ON
;with foo(unique_id, parent_id,child_id, ord, lvl) as (
-- anchor member that happens to select first and last edges:
select unique_id, parent_id, child_id, row_number() over(order by unique_id), 0
from #bar where parent_id in (1,3)
union all
-- recursive member:
select b.unique_id, b.parent_id, b.child_id, row_number() over(order by b.unique_id), foo.lvl+1
from #bar b
join foo on b.parent_id = foo.child_id
)
select unique_id, parent_id,child_id, ord, lvl from foo
/***********************************
Manual Recursion
***********************************/
Declare @lvl as int
Declare @rows as int
DECLARE @foo as Table(
unique_id int,
parent_id int,
child_id int,
ord int,
lvl int)
--Get anchor condition
INSERT @foo (unique_id, parent_id, child_id, ord, lvl)
select unique_id, parent_id, child_id, row_number() over(order by unique_id), 0
from #bar where parent_id in (1,3)
set @rows=@@ROWCOUNT
set @lvl=0
--Do recursion
WHILE @rows > 0
BEGIN
set @lvl = @lvl + 1
INSERT @foo (unique_id, parent_id, child_id, ord, lvl)
SELECT DISTINCT b.unique_id, b.parent_id, b.child_id, row_number() over(order by b.unique_id), @lvl
FROM #bar b
inner join @foo f on b.parent_id = f.child_id
--might be multiple paths to this recursion so eliminate duplicates
left join @foo dup on dup.unique_id = b.unique_id
WHERE f.lvl = @lvl-1 and dup.child_id is null
set @rows=@@ROWCOUNT
END
SELECT * from @foo
DROP TABLE #bar
두 가장자리 중 어느 것이 나무의 더 깊은 수준에 있는지 아는가? 이 경우 가장자리를 만들 수 있기 때문입니다 3->4 앵커 멤버와 가장자리를 찾을 때까지 나무를 걷기 시작합니다. 1->2.
이 같은:
with foo(parent_id, child_id)
as
(
select parent_id, child_id
from #bar
where parent_id = 3
union all
select parent_id, child_id
from #bar b
inner join foo f on b.child_id = f.parent_id
where b.parent_id <> 1
)
select *
from foo
이것이 당신이하고 싶은 일입니까?
create table #bar (parent_id int, child_id int)
insert #bar values (1,2)
insert #bar values (2,3)
insert #bar values (3,4)
declare @start_node table (parent_id int)
insert @start_node values (1)
insert @start_node values (3)
;with foo(parent_id,child_id) as (
select
parent_id
,child_id
from #bar where parent_id in (select parent_id from @start_node)
union all
select
#bar.*
from #bar
join foo on #bar.parent_id = foo.child_id
where foo.child_id not in (select parent_id from @start_node)
)
select parent_id,child_id from foo
편집 - @bacar- Quasnoi가 제안한 온도 테이블 솔루션이라고 생각하지 않습니다. 나는 그들이 각 재귀 동안 기본적으로 전체 재귀 부재 함량을 복제하는 것을 제안하고 있으며, 재 처리를 방지하기 위해 조인으로 사용한다 (그리고 이것은 SS2K5에서는 지원되지 않음). 저의 접근 방식은 지원되며 원본에 대한 유일한 변경 사항은 재귀 멤버의 술어에서 시작 세트에서 명시 적으로 재귀 경로를 배제하는 것입니다. 테이블 변수 만 추가하여 한 위치에서 시작 parent_ids를 정의 할 수 있도록 원래 쿼리와 함께이 술어를 쉽게 사용할 수있었습니다.
where foo.child_id not in (1,3)
편집 - 전혀 작동하지 않습니다.삼각루트 추격을 멈추는 방법이다.OP가 원하는 것을 수행하지 않습니다.
또는 재귀 토큰으로 구분된 문자열을 사용할 수 있습니다.
저는 집에 노트북(SQL 서버 없음)을 사용하고 있으므로 이것이 완전히 옳지 않을 수도 있지만 여기에 있습니다.....
; WITH NodeNetwork AS (
-- Anchor Definition
SELECT
b.[parent_Id] AS [Parent_ID]
, b.[child_Id] AS [Child_ID]
, CAST(b.[Parent_Id] AS VARCHAR(MAX)) AS [NodePath]
FROM
#bar AS b
-- Recursive Definition
UNION ALL SELECT
b.[Parent_Id]
, b.[child_Id]
, CAST(nn.[NodePath] + '-' + CAST(b.[Parent_Id] AS VARCHAR(MAX)) AS VARCHAR(MAX))
FROM
NodeNetwork AS nn
JOIN #bar AS b ON b.[Parent_Id] = nn.[Child_ID]
WHERE
nn.[NodePath] NOT LIKE '%[-]' + CAST(b.[Parent_Id] AS VARCHAR(MAX)) + '%'
)
SELECT * FROM NodeNetwork
아니면 비슷합니다.죄송합니다. 늦어서 테스트할 수 없습니다.월요일 아침에 확인해보겠습니다.이에 대한 크레딧은 Peter Larsson(페소)에게 돌아가야 합니다.
아이디어는 여기에서 생성되었습니다.http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=115290
(나는 그래프에 대한 전문가가 아니라 조금만 탐색합니다)
뚜렷한 것은 각 행이 뚜렷하다는 것을 보장하지만 마지막 가장자리에서는 끝나지 않는 그래프 경로를 제거하지는 않습니다. 이 그래프를 가져 가십시오 :
insert into #bar (parent_id,child_id) values (1,2)
insert into #bar (parent_id,child_id) values (1,5)
insert into #bar (parent_id,child_id) values (2,3)
insert into #bar (parent_id,child_id) values (2,6)
insert into #bar (parent_id,child_id) values (6,4)
여기의 쿼리 결과에는 (1,5)가 포함되며, 이는 첫 번째 가장자리 (1,2)에서 마지막 가장자리 (6,4)까지 경로의 일부가 아닙니다.
(1,2)로 시작하는 경로 만 찾고 (6,4)로 끝나는 경로 만 찾을 수 있습니다.
with foo(parent_id, child_id, route) as (
select parent_id, child_id,
cast(cast(parent_id as varchar) +
cast(child_id as varchar) as varchar(128))
from #bar
union all
select #bar.parent_id, #bar.child_id,
cast(route + cast(#bar.child_id as varchar) as varchar(128))
from #bar
join foo on #bar.parent_id = foo.child_id
)
select * from foo where route like '12%64'
