Простой пример
Попробуйте более простой пример, чтобы люди могли обернуть головы концепциями и иметь практический пример, который вы можете скопировать и вставить в SQL Query Analizer:
Представьте таблицу Узлы с иерархией:
A
- B
- C
Мы можем начать тестирование в Query Analizer:
CREATE TABLE ##Nodes
(
NodeID varchar(50) PRIMARY KEY NOT NULL,
ParentNodeID varchar(50) NULL
)
INSERT INTO ##Nodes (NodeID, ParentNodeID) VALUES ('A', null)
INSERT INTO ##Nodes (NodeID, ParentNodeID) VALUES ('B', 'A')
INSERT INTO ##Nodes (NodeID, ParentNodeID) VALUES ('C', 'B')
Желаемый вывод:
ParentNodeID NodeID GenerationsRemoved
============ ====== ==================
NULL A 1
NULL B 2
NULL C 3
A B 1
A C 2
B C 1
Теперь предлагаемое выражение CTE с неправильным выводом:
WITH NodeChildren AS
(
--initialization
SELECT ParentNodeID, NodeID, 1 AS GenerationsRemoved
FROM ##Nodes
WHERE ParentNodeID IS NULL
UNION ALL
--recursive execution
SELECT P.ParentNodeID, N.NodeID, P.GenerationsRemoved + 1
FROM NodeChildren AS P
INNER JOIN ##Nodes AS N
ON P.NodeID = N.ParentNodeID
)
SELECT ParentNodeID, NodeID, GenerationsRemoved
FROM NodeChildren
Фактический выход:
ParentNodeID NodeID GenerationsRemoved
============ ====== ==================
NULL A 1
NULL B 2
NULL C 3
Примечание: Если SQL Server 2005 † CTE не может делать то, что я делал раньше в 2000 году, это прекрасно, и это ответ. И тот, кто дает "это невозможно", так как ответ выиграет щедрость. Но я подожду несколько дней, чтобы убедиться, что все согласны с тем, что это невозможно, до того, как я безоговорочно дам 250 репутации за невыполнение моей проблемы.
Уголок Нитпикерса
† не 2008
‡, не прибегая к UDF *, который уже имеет решение
*, если вы не видите способ улучшить производительность UDF в исходном вопросе
Оригинальный вопрос
У меня есть таблица узлов, каждая из которых имеет родительский элемент, который указывает на другой Node (или на null).
Для иллюстрации:
1 My Computer
2 Drive C
4 Users
5 Program Files
7 Windows
8 System32
3 Drive D
6 mp3
Мне нужна таблица, которая возвращает все отношения родитель-потомок и число поколений между ними
Для всех прямых родительских отношений:
ParentNodeID ChildNodeID GenerationsRemoved
============ =========== ===================
(null) 1 1
1 2 1
2 4 1
2 5 1
2 7 1
1 3 1
3 6 1
7 8 1
Но тогда отношения с бабушкой и дедушкой:
ParentNodeID ChildNodeID GenerationsRemoved
============ =========== ===================
(null) 2 2
(null) 3 2
1 4 2
1 5 2
1 7 2
1 6 2
2 8 2
И там великие прадедушки:
ParentNodeID ChildNodeID GenerationsRemoved
============ =========== ===================
(null) 4 3
(null) 5 3
(null) 7 3
(null) 6 3
1 8 3
Итак, я могу выяснить основную инициализацию CTE:
WITH (NodeChildren) AS
{
--initialization
SELECT ParentNodeID, NodeID AS ChildNodeID, 1 AS GenerationsRemoved
FROM Nodes
}
Теперь проблема - это рекурсивная часть. Очевидный ответ, конечно, не работает:
WITH (NodeChildren) AS
{
--initialization
SELECT ParentNodeID, ChildNodeID, 1 AS GenerationsRemoved
FROM Nodes
UNION ALL
--recursive execution
SELECT parents.ParentNodeID, children.NodeID, parents.Generations+1
FROM NodeChildren parents
INNER JOIN NodeParents children
ON parents.NodeID = children.ParentNodeID
}
Msg 253, Level 16, State 1, Line 1
Recursive member of a common table expression 'NodeChildren' has multiple recursive references.
Вся информация, необходимая для создания всего рекурсивного списка, присутствует в таблице inital CTE. Но если это не разрешено, я попробую:
WITH (NodeChildren) AS
{
--initialization
SELECT ParentNodeID, NodeID, 1 AS GenerationsRemoved
FROM Nodes
UNION ALL
--recursive execution
SELECT parents.ParentNodeID, Nodes.NodeID, parents.Generations+1
FROM NodeChildren parents
INNER JOIN Nodes
ON parents.NodeID = nodes.ParentNodeID
}
Но это терпит неудачу, потому что оно не только соединяется с рекурсивными элементами, но и рекурсивно добавляет одни и те же строки много раз:
Msg 530, Level 16, State 1, Line 1
The statement terminated. The maximum recursion 100 has been exhausted before statement completion.
В SQL Server 2000 я смоделировал CTE с помощью пользовательской функции (UDF):
CREATE FUNCTION [dbo].[fn_NodeChildren] ()
RETURNS @Result TABLE (
ParentNodeID int NULL,
ChildNodeID int NULL,
Generations int NOT NULL)
AS
/*This UDF returns all "ParentNode" - "Child Node" combinations
...even multiple levels separated
BEGIN
DECLARE @Generations int
SET @Generations = 1
--Insert into the Return table all "Self" entries
INSERT INTO @Result
SELECT ParentNodeID, NodeID, @Generations
FROM Nodes
WHILE @@rowcount > 0
BEGIN
SET @Generations = @Generations + 1
--Add to the Children table:
-- children of all nodes just added
-- (i.e. Where @Result.Generation = CurrentGeneration-1)
INSERT @Result
SELECT CurrentParents.ParentNodeID, Nodes.NodeID, @Generations
FROM Nodes
INNER JOIN @Result CurrentParents
ON Nodes.ParentNodeID = CurrentParents.ChildNodeID
WHERE CurrentParents.Generations = @Generations - 1
END
RETURN
END
И волшебство, чтобы удержать его от взрыва, было ограничение, где положение: WHERE CurrentParents.Generations - @Generations-1
Как вы мешаете рекурсивному CTE навсегда?
