多父树（或有向图）实现sql server 2005

Question

我需要在 SQL Server 2005 上实现多父树（或有向图）。 我读过几篇文章，但大多数都使用具有独特根的单亲树，如下所示。

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

在这个例子中，一切都源自根元素（我的电脑）。

在我的例子中，一个孩子可以有超过 1 个父母，如下所示：

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

---

返回以下 SET

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

： 预期结果 SET：

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

请注意，关系 G->B 缺失，因为它要求一个起始对象（这对我也不起作用，因为我从一开始就不知道根对象）并使用 A 作为起始点将忽略 G->B 关系。

因此，这段代码在我的情况下不起作用，因为它要求一个起始对象，这在单父树中很明显（将始终是根对象）。 但在多父树中，您可以有超过 1 个“根”对象（如示例中，G 和 A 是“根”对象，其中根是没有父级（祖先）的对象）。

所以我有点卡在这里......我需要修改查询以不要求起始对象并递归遍历整个树。 我不知道 (Id, NextId) 实现是否可能......可能我需要使用某种关联矩阵、邻接矩阵或其他什么来将它存储为图形（请参阅 http://willets.org/sqlgraphs.html）。

有什么帮助吗？ 你们觉得怎么样？ 非常感谢您抽出宝贵的时间=）

干杯！

资料来源： 来源 1 来源 2 来源 3

Answer 1

好吧，我最终想出了以下解决方案。
这是我发现支持多根树和循环有向图的方式。

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
谢谢

Answer 2

如果要使用所有根对象作为起始对象，则应首先更新数据以包含有关根对象（和叶子）的信息。 您应该添加以下插入：

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

当然，您也可以以这样的方式编写锚查询：选择具有不作为 NextId< 出现的 Id 的记录作为根节点。 /code>，但这更容易。

接下来，将锚点查询修改为如下所示：

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

如果运行此查询，您会发现有很多重复项，很多弧出现多次。 这是因为您现在从锚点查询中获得了两个结果，因此树被遍历了两次。

可以通过将 select 语句更改为以下内容来解决此问题（请注意 DISTINCT）：

SELECT DISTINCT o.*
FROM   Objects o

Answer 3

如果你不想做罗纳德建议的插入，这样做就可以了！

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