Деревья в SQL
Страница 6. Объединение деревьев

Объединение деревьев 

Чтобы заставить эти деревья сливаться в одно заключительное дерево, Вы нуждаетесь в способе прикрепить подчиненное дерево к его предку. На процедурном языке, Вы могли выполнить это программой, которая будет делать следующие шаги:

1. Найти размер подчиненного дерева.
2. Найти место, куда подчиненное дерево вставляется в дерево-предок.
3. Раздвинуть дерево-предок в точке вставки.
4. Вставить подчиненное дерево в точку вставки.

На непроцедурном языке, Вы исполнили бы эти шаги вместе, используя логику всех перечисленных пунктов. Вы начинаете этот процесс, задавая вопросы и отмечая факты:

Q)Как выбирать дерево-предок и его подчиненное дерево в лесу?
A)Ищем одиночное ключевое значение, которое является потомком в дерево-предке и корнем подчиненного дерева;

Q)Как определить на сколько необходимо раздвинуть дерево-предок?
A)Это размер подчиненного дерева, равный (2 * (select count(*) from Подчиненое)).

Q)Как определить точку вставки?
A)Это - строка в таблице предка, где значение emp равно значению boss в подчиненной таблице. Вы хотите поместить подчиненное дерево левее левого значения этого общего узла. Небольшие алгебраические вычисления дают Вам число, добавляемое ко всем левым и правым значениям справа от точки вставки.

Самый простой способ это объяснить- при помощи таблицы отношений, показанной в табл. 1.

Вы готовы к написанию процедуры, объединяющей два дерева:

CREATE PROCEDURE TreeMerge(superior NOT NULL, subordinate NOT NULL)
BEGIN
DECLARE size INTEGER NOT NULL;
DECLARE insert_point INTEGER NOT NULL;
SET size = 2 * (SELECT COUNT(*) FROM WorkingTree WHERE emp = subordinate);
SET insert_point = (
SELECT MIN(lft) 
FROM WorkingTree
WHERE emp = subordinate AND boss = superior) - 1;

UPDATE WorkingTree
SET boss = CASE WHEN boss = subordinate
THEN CASE WHEN emp = subordinate
THEN NULL
ELSE superior END
ELSE boss END,

lft = CASE WHEN (boss = superior AND lft > size)
THEN lft + size
ELSE CASE WHEN boss = subordinate AND emp <> subordinate
THEN lft + insert_point
ELSE lft END
END,

rgt = CASE WHEN (boss = superior AND rgt > size)
THEN rgt + size
ELSE CASE WHEN boss = subordinate AND emp <> subordinate
THEN rgt + insert_point
ELSE rgt END
END

WHERE boss IN (superior, subordinate);

--Удаляем избыточные копии корня подчиненного дерева
DELETE FROM WorkingTree WHERE boss IS NULL OR emp IS NULL;
 
 END;

Обнаружить пары внешних и подчиненных деревьев в таблице WorkingTree очень просто. Следующий запрос становится пустым, когда все боссы установлены в одно и тоже значение:

CREATE VIEW AllPairs (superior, subordinate)
AS
SELECT W1.boss, W1.emp
FROM WorkingTree AS W1
WHERE EXISTS( SELECT * FROM WorkingTree AS W2 WHERE W2.boss = W1.emp)
AND W1.boss <> W1.emp; 

Но Вы хотели бы получить только одну пару, которую Вы передатите в только что разработанную процедуру. Чтобы переместить одну пару, берем крайнюю левую пару из прошлого запроса:

CREATE VIEW LeftmostPairs(superior, subordinate) 
AS
SELECT DISTINCT superior, 
(SELECT MIN(subordinate)
FROM AllPairs AS A2
WHERE A1.superior = A2.superior)
FROM AllPairs AS A1
WHERE superior = (SELECT MIN(superior) FROM AllPairs); 

Теперь все, что Вам осталось сделать - поместить этот запрос в ранее разработанную процедуру - и у вас будет процедура, которая сольет вместе лес деревьев слева направо. Используя цикл WHILE, контролируюший наличие значений в LeftmostPairs делайте вызовы процедуры. Это единственная процедуральная структура во всей хранимой процедуре.

Таблица 1

C1	row in superior	y	y	y	y	n	y	n
C2	row in subord	n	n	n	n	y	y	n
C3	lft > cut	n	n	y	y	-	-	-
C4	rgt > cut	n	y	n	y	-	-	-

A1	Ошибка			1			1
A2	lft := lft + size				1
A3	rgt := rgt + size		1		2
A4	lft := lft	1	2					1
A5	rgt := rgt	2						2
A6	lft := lft + cut					1
A7	rgt := rgt + cut					2

Joe Celko