Деревья в SQL - Объединение деревьев

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

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

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