Insert into @tree (Name, Level) values (@NodeName, @Level);

-- Пока не доберёмся до корневого элемента иерархии...

WHILE (@ID <> @Parent)

BEGIN

SELECT @ID=ID, @Parent=Parent, @NodeName=Data

FROM T

WHERE ID=@Parent;

-- Наращиваем расстояние до предка

SET @Level=@Level+1;

-- Добавляем запись в возвращаемую таблицу

Insert into @tree (Name, Level) values

(@NodeName, @Level);

END

RETURN

END

При помощи этой функции получим всех предков, например, узла O:

select * from GetParents('O') ORDER BY Level DESC;

Результат выполнения этого запроса представлен на рис. 22.

Рис. 22. Использование функции нахождения всех предков некоторого узла для узла O

Теперь при помощи функции GetParents можно решить задачу о нахождении ближайшего общего предка для двух узлов. Пусть заданы узлы I и K. Их общий ближайший предок – узел B (см. рис. 8).

С помощью запросов

select [name] from GetParents('I');

и

select [name] from GetParents('K');

получим списки всех предков этих узлов (рис. 23).

Рис. 23 Все предки узлов I и K

Запрос

select * from GetParents('I') where

([name] in (select [name] from GetParents('K')));

даст список всех общих предков для узлов I и K (рис. 24).

Рис. 24. Список всех общих предков для узлов I и K

Из этого списка надо выбрать элемент с минимальным значением поля Level (рис. 25).

select MIN([level]) from GetParents('I') where

[name] in (select [name] from GetParents('K'));

Рис. 25. Получаем элемент с минимальным значением в поле Level

Окончательно получаем ближайшего общего предка для узлов I и K при помощи следующего предложения SQL (рис. 26):

select [name] from GetParents('I') where

([name] in (select [name] from GetParents('K'))

And ([level]=((

select MIN([level]) from GetParents('I') where

[name] in (select [name] from GetParents('K'))))));

Рис. 26. Получаем ближайшего общего предка для узлов I и K

Задача выбора всех потомков (или поддерева) для некоторого, наперёд заданного узла более сложная, так как, в отличие от предков, которые для каждого узла единственные на каждом уровне, у одного предка может быть несколько различных непосредственных потомков.

Для решения этой задачи можно использовать средства некоторого внешнего объемлющего языка уровня приложения или хранимые процедуры СУБД. Здесь может использоваться рекурсивный вызов, однако следует учесть, что существует ограничение на вложенность рекурсивных вызовов (например, не более 100 для MS SQL Server 2005 Express Edition), а дерево может быть больше, чем разрешённая глубина вложенности рекурсивных вызовов. Приведём пример рекурсивной функции, использующей курсор:

CREATE FUNCTION MyGetTree(@root varchar(1),

@order varchar(4096),

@level int)

RETURNS @tree TABLE

(

[name] varchar,

id int,

parent int,

[level] int,

[order] varchar(4096)

)

AS

Begin

-- ВНИМАНИЕ! В реальной функции необходимо

-- проверить законность входных параметров.

-- После каждой операции необходима проверка

-- наличия ошибок, отсутствующая в данном примере!

DECLARE @id int;

DECLARE @parent int;

DECLARE @data varchar(1);

IF @level=0

BEGIN

-- Если это корневой элемент

-- записываем в таблицу информацию о

-- заданном узле выбираемого поддерева.