Более простой пример
Давайте попробуем более простой пример, чтобы люди могли обдумать концепцию, и приведем практический пример, который вы можете скопировать и вставить в 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 репутации за нерешенность моей проблемы.
Уголок Nitpickers
† не 2008
‡ без обращения к UDF *, решение которого уже есть
*, если вы не видите способа улучшить производительность UDF в исходном вопросе
Оригинальный вопрос
У меня есть таблица узлов, у каждого из которых есть родитель, который указывает на другой узел (или на ноль).
Для иллюстрации:
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.
Вся информация, необходимая для генерации полного рекурсивного списка, содержится в исходной таблице 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
И волшебство, чтобы удержать его от взрыва, было ограничивающим предложением где:
ГДЕ CurrentParents.Generations - @ Generations-1
Как предотвратить рекурсивный CTE навсегда?