Деревья в 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

C1row in superioryyyynyn
C2row in subordnnnnyyn
C3lft > cutnnyy---
C4rgt > cutnyny---


A1Ошибка  1  1 
A2lft := lft + size   1   
A3rgt := rgt + size 1 2   
A4lft := lft12    1
A5rgt := rgt2     2
A6lft := lft + cut    1  
A7rgt := rgt + cut    2  

Joe Celko

 
Следующая статья »