Реализация множественного родительского дерева (или орграфа) 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
В этом случае все происходит из корневого элемента (Мой компьютер).
В моем случае у ребенка может быть более 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
Который возвращает следующий НАБОР:
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-> B.
Итак, этот код не работает в моем случае, потому что он запрашивает начальный объект, который очевиден в дереве с ОДНИМ родителем (всегда будет корневым объектом).Но в дереве с несколькими родителями у вас может быть более 1 "корневого" объекта (как в примере, G и A являются "корневыми" объектами, где root - это объект, у которого нет родителя (ancestor)).
Так что я как бы застрял здесь...Мне нужно изменить запрос, чтобы НЕ запрашивать начальный объект и рекурсивно обходить все дерево.Я не знаю, возможно ли это с помощью реализации (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 на this (обратите внимание на 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