Деревья в SQL.
Falk0ner, вс, 06/07/2008 - 15:34.
Чтобы заставить эти деревья сливаться в одно заключительное дерево, Вы нуждаетесь в способе прикрепить подчиненное дерево к его предку. На процедурном языке, Вы могли выполнить это программой, которая будет делать следующие шаги: 1.Найти размер подчиненного дерева. 1.Найти место, куда подчиненное дерево вставляется в дерево-предок. 1.Раздвинуть дерево-предок в точке вставки. 1.Вставить подчиненное дерево в точку вставки. На непроцедурном языке, Вы исполнили бы эти шаги вместе, используя логику всех перечисленных пунктов. Вы начинаете этот процесс, задавая вопросы и отмечая факты:Q)Как выбирать дерево-предок и его подчиненное дерево в лесу?A)Ищем одиночное ключевое значение, которое является потомком в дерево-предке и корнем подчиненного дерева;Q)Как определить на сколько необходимо раздвинуть дерево-предок?A)Это размер подчиненного дерева, равный (2 * (select count(*) from Подчиненое)). Q)Как определить точку вставки?A)Это - строка в таблице предка, где значение emp равно значению boss в подчиненной таблице. Вы хотите поместить подчиненное дерево левее левого значения этого общего узла. Небольшие алгебраические вычисления дают Вам число, добавляемое ко всем левым и правым значениям справа от точки вставки. Самый простой способ это объяснить- при помощи таблицы отношений, показанной в табл. 1. ПРИМЕЧАНИЕ ПЕРЕВОДЧИКА: Я не знаю, что он имел в виду насчет самого простого способа объяснения, но ни черта не понял в этой таблице :)))) Если вам все понятно, то объясните мне, pls, письмом :))) Вы готовы к написанию процедуры, объединяющей два дерева:
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 очень просто. Следующий запрос становится пустым, когда все боссы установлены в одно и тоже значение:
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;
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;
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);
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 CelkoDBMS Online - May 1996Translated by SDM
Отправить комментарий