多父树(或有向图)实现 sql server 2005 [英] Multiple parents tree (or digraph) implementation sql server 2005

问题描述

我需要在 SQL Server 2005 上实现一个多父树(或有向图).我读过几篇文章，但其中大部分都使用具有唯一根的单亲树，如下所示.

I need to implement a multi-parented tree (or digraph) onto SQL Server 2005. I've read several articles, but most of them uses single-parented trees with a unique root like the following one.

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

在这一个中，一切都来自一个根元素(我的电脑).

In this one, everything derives from a root element (My PC).

在我的例子中，一个孩子可以有多个父母，如下所示:

In my case, a child could have more than 1 parent, like the following:

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:

---

Which returns the following SET:

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 缺失，因为它要求一个起始对象(这对我也不起作用，因为我从一开始就不知道根对象)并使用 A 作为开始point 将忽略 G->B 关系.

Note that the relation G->B is missing, because it asks for an starting object (which doesn't work for me also, because I don't know the root object from the start) and using A as the start point will ignore the G->B relationship.

因此，此代码在我的情况下不起作用，因为它要求一个起始对象，这在单父树中很明显(将始终是根对象).但是在多父树中，您可能有 1 个以上的根"对象(就像在示例中一样，G 和 A 是根"对象，其中根是一个没有父(祖先)的对象).

So, this code doesn't work in my case because it asks for a starting object, which is obvious in a SINGLE-parent tree (will always be the root object). But in multi-parent tree, you could have more than 1 "root" object (like in the example, G and A are the "root" objects, where root is an object which doesn't have a parent (ancestor)).

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

So I'm kind of stucked in here... I need to modify the query to NOT ask for a starting object and recursively traverse the entire tree. I don't know if that's possible with the (Id, NextId) implementation... may be I need to store it like a graph using some kind of Incidence matrix, adjacency matrix or whatever (see http://willets.org/sqlgraphs.html).

有什么帮助吗?你们觉得怎么样?非常感谢您的时间=)

Any help? What do you think guys? Thank you very much for your time =)

干杯！

来源:来源 1来源 2来源 3

推荐答案

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

Well, I finally came up with the following solution. It's the way I found to support multi-root trees and also cycling digraphs.

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

Could be useful for somebody. It is for me =P Thanks

这篇关于多父树(或有向图)实现 sql server 2005的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！