多家长树(或有向图)实现SQL Server 2005中
-
21-08-2019 - |
题
我需要实现多与父母树(或有向图)到SQL Server 2005中。 我读过几篇文章,但大多使用的是单父树木像下面的一个唯一的根。
-My PC
-Drive C
-Documents and Settings
-Program Files
-Adobe
-Microsoft
-Folder X
-Drive D
-Folder Y
-Folder Z
在这其中,一切从一个根元素(我的PC)派生的。
在我的情况下,儿童可以具有多于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
预期的结果集:
Id NextId
-------------------- --------------------
G B
A B
B C
B X
C E
C D
D F
E F
此外,该关系G-> B丢失,因为它要求一个起点对象(不工作对我来说也是,因为我不知道,从一开始的根对象),以及A作为开始点将会忽略G->乙关系。
因此,此代码不会在我的情况下,因为它要求的起始对象,这是在单父树明显工作(将始终是根对象)。但在多父树,可以有多于1“根”的物品(如在该示例中,G和A的“根”的对象,其中,根是一个对象不具有父(祖先))。
所以我在这儿种stucked ...我需要修改查询并没有要求起始对象和递归遍历整个树。 我不知道这是可能与(ID,NextId)实现......可能是我需要使用某种关联矩阵,邻接矩阵或什么的,将其存储像图(见的 http://willets.org/sqlgraphs.html )。
任何帮助?你们觉得怎么样? 非常感谢您的宝贵时间=)
干杯!
解决方案
好了,我终于想出了以下解决方案。 这是我发现的,支持多根树,也有向图骑自行车的方式。
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
如果你不想做的罗纳德·建议插入,这会做!
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