여러 부모 트리 (또는 Digraph) 구현 SQL Server 2005

StackOverflow https://stackoverflow.com/questions/855942

문제

SQL Server 2005에 다중 부모 트리 (또는 Digraph)를 구현해야합니다. 여러 기사를 읽었지만 대부분은 다음과 같은 독특한 뿌리를 가진 단일 부모의 나무를 사용합니다.

-My PC
   -Drive C
      -Documents and Settings
      -Program Files
         -Adobe
         -Microsoft
      -Folder X
   -Drive D
      -Folder Y
      -Folder Z

이것에서 모든 것이 루트 요소 (내 PC)에서 파생됩니다.

제 경우에는 아이가 다음과 같이 한 부모가 2 명 이상을 가질 수 있습니다.

G  A
 \ /
  B
 / \ 
X   C
  /  \
  D   E
  \ /
   F

그래서 다음 코드가 있습니다.

create table #ObjectRelations
(
    Id varchar(20),
    NextId varchar(20)
)

insert into #ObjectRelations values ('G', 'B')
insert into #ObjectRelations values ('A', 'B') 
insert into #ObjectRelations values ('B', 'C')
insert into #ObjectRelations values ('B', 'X')
insert into #ObjectRelations values ('C', 'E') 
insert into #ObjectRelations values ('C', 'D') 
insert into #ObjectRelations values ('E', 'F') 
insert into #ObjectRelations values ('D', 'F') 

declare @id varchar(20)
set @id = 'A';

WITH Objects (Id, NextId) AS
( -- This is the 'Anchor' or starting point of the recursive query
  SELECT rel.Id,
         rel.NextId
    FROM #ObjectRelations rel
   WHERE rel.Id = @id
   UNION ALL -- This is the recursive portion of the query
  SELECT rel.Id,
         rel.NextId
    FROM #ObjectRelations rel
   INNER JOIN Objects -- Note the reference to CTE table name (Recursive Join)
      ON rel.Id = Objects.NextId
)
SELECT  o.*
FROM    Objects o

drop table #ObjectRelations

다음 세트를 반환합니다.

Id                   NextId
-------------------- --------------------
A                    B
B                    C
B                    X
C                    E
C                    D
D                    F
E                    F

예상 결과 세트 :

Id                   NextId
-------------------- --------------------
G                    B
A                    B
B                    C
B                    X
C                    E
C                    D
D                    F
E                    F

g-> b 관계는 시작 객체를 요구하기 때문에 (시작부터 루트 객체를 모르기 때문에 나에게도 작동하지 않음)를 요구하고 시작점을 사용하면 무시할 것입니다. G-> B 관계.

따라서이 코드는 시작 객체를 요구하기 때문에 제 경우에는 작동하지 않습니다. 이는 단일 부모 트리에서 명백합니다 (항상 루트 객체입니다). 그러나 다중 부모 트리에서는 2 개 이상의 "루트"객체를 가질 수 있습니다 (예 : g와 a는 "루트"객체이며, 루트는 부모 (조상)가없는 객체입니다).

그래서 나는 여기에 붙어 있습니다 ... 시작 객체를 요구하지 않고 트리 전체를 재귀 적으로 가로 지르기 위해 쿼리를 수정해야합니다. (ID, NextID) 구현에서 가능한지 모르겠습니다 ... 어떤 종류의 입사 매트릭스, 인접 매트릭스 등을 사용하여 그래프처럼 저장해야 할 수도 있습니다 (참조 http://willets.org/sqlgraphs.html).

도움이 있습니까? 너희들은 어떻게 생각하세요? 시간 내 주셔서 대단히 감사합니다 =)

건배!

출처 :출처 1 출처 2 출처 3

도움이 되었습니까?

해결책

글쎄, 나는 마침내 다음 해결책을 생각해 냈습니다. 다층 나무와 자전거 디지프를 지원하는 방식입니다.

create table #ObjectRelations
(
    Id varchar(20),
    NextId varchar(20)
)

/* Cycle */
/*
insert into #ObjectRelations values ('A', 'B')
insert into #ObjectRelations values ('B', 'C') 
insert into #ObjectRelations values ('C', 'A')
*/

/* Multi root */

insert into #ObjectRelations values ('G', 'B')
insert into #ObjectRelations values ('A', 'B') 
insert into #ObjectRelations values ('B', 'C')
insert into #ObjectRelations values ('B', 'X')
insert into #ObjectRelations values ('C', 'E') 
insert into #ObjectRelations values ('C', 'D') 
insert into #ObjectRelations values ('E', 'F') 
insert into #ObjectRelations values ('D', 'F') 


declare @startIds table
(
    Id varchar(20) primary key
)

;WITH 
    Ids (Id) AS
    (
        SELECT  Id
        FROM    #ObjectRelations
    ),
    NextIds (Id) AS
    (
        SELECT  NextId
        FROM    #ObjectRelations
    )
INSERT INTO @startIds
/* This select will not return anything since there are not objects without predecessor, because it's a cyclic of course */
SELECT DISTINCT
    Ids.Id
FROM
    Ids
LEFT JOIN
    NextIds on Ids.Id = NextIds.Id
WHERE
    NextIds.Id IS NULL
UNION
/* So let's just pick anyone. (the way I will be getting the starting object for a cyclic doesn't matter for the regarding problem)*/
SELECT TOP 1 Id FROM Ids

;WITH Objects (Id, NextId, [Level], Way) AS
( -- This is the 'Anchor' or starting point of the recursive query
  SELECT rel.Id,
         rel.NextId,
         1,
         CAST(rel.Id as VARCHAR(MAX))
    FROM #ObjectRelations rel
   WHERE rel.Id IN (SELECT Id FROM @startIds)

   UNION ALL -- This is the recursive portion of the query

  SELECT rel.Id,
         rel.NextId,
         [Level] + 1,
         RecObjects.Way + ', ' + rel.Id
    FROM #ObjectRelations rel
   INNER JOIN Objects RecObjects -- Note the reference to CTE table name (Recursive Join)
      ON rel.Id = RecObjects.NextId
   WHERE RecObjects.Way NOT LIKE '%' + rel.Id + '%'

)
SELECT  DISTINCT 
        Id,
        NextId,
        [Level]
FROM    Objects
ORDER BY [Level]

drop table #ObjectRelations

누군가에게 유용 할 수 있습니다. 그것은 나를위한 것입니다 = P 감사합니다

다른 팁

모든 루트 객체를 시작 객체로 사용하려면 먼저 루트 객체 (및 잎)에 대한 정보를 포함하도록 데이터를 업데이트해야합니다. 다음 인서트를 추가해야합니다.

insert into #ObjectRelations values (NULL, 'G')
insert into #ObjectRelations values (NULL, 'A')
insert into #ObjectRelations values ('X', NULL)
insert into #ObjectRelations values ('F', NULL)

물론 루트 노드로 선택한 방식으로 앵커 쿼리를 작성할 수도 있습니다. Id 그것은 발생하지 않습니다 NextId, 그러나 이것은 더 쉽습니다.

다음으로 앵커 쿼리를 다음과 같이 수정하십시오.

SELECT rel.Id,
       rel.NextId
FROM #ObjectRelations rel
WHERE rel.Id IS NULL

이 쿼리를 실행하면 많은 복제가 발생하는 것을 알 수 있습니다. 많은 호가 여러 번 발생합니다. 이제 앵커 쿼리에서 두 가지 결과가 있기 때문에 트리가 두 번 횡단되기 때문입니다.

이것은 select 문을 이것으로 변경하여 고정 될 수 있습니다 (참고 DISTINCT):

SELECT DISTINCT o.*
FROM   Objects o

Ronald가 제안한 인서트를하고 싶지 않다면 이렇게 할 것입니다!. 

WITH CTE_MultiParent  (ID, ParentID) 
AS 
(
    SELECT ID, ParentID FROM #ObjectRelations
    WHERE ID NOT IN 
    (
        SELECT DISTINCT ParentID FROM #ObjectRelations
    )
    UNION ALL
    SELECT ObjR.ID, ObjR.ParentID FROM #ObjectRelations ObjR INNER JOIN CTE_MultiParent
    ON CTE_MultiParent.ParentID = ObjR.Id
)

SELECT DISTINCT * FROM CTE_MultiParent
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top