Деревья в SQL

Деревья в SQL. Часть 3.

Давайте продолжим наше обсуждение модели вложенных множеств для деревьев в SQL. Я не собираюсь рассматривать любую из моих предидущих статей и буду предполагать, что Вы все еще имеете копию таблицы Personnel, которую я использовал для примеров (DBMS, март 1996, страница 24). Если Вы не имеете прошлых выпусков, Вы можете осчастливить моего издателя, приобретя их.

Меня спрашивают, почему я не показываю больше процедурного кода в примерах. Прямо сейчас, ANSI и ISO пробуют договориться о стандартном процедурном языке для триггеров и хранимых процедур называемом SQL/PSM. Однако, этот стандарт еще не утвержден, что означает, что я должен использовать или свой собственный псевдо-код или выбирать одного производителя. Я решил использовать пока Английские комментарии, но я буду начинать использовать SQL/PSM, когда он будет завершен.

Наиболее хитрая часть обработки деревьев в SQL это нахождение способа конвертировать модель матрицы смежности в модель вложенных множеств в пределах структуры чистого SQL. Было бы довольно просто загрузить таблицу матрицы смежности в программу, и затем использовать рекурсивную программу преобразование дерева из учебника колледжа, чтобы построить модель вложенных множеств.

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

Классический подход к решению проблемы состоит в том, чтобы брать самое простой случай проблемы, и смотреть, можете ли Вы применять его к более сложным случаям. Если дерево не имеет узлов, то преобразование просто - ничего не делать. Если дерево имеет один узел, то преобразование простое - устанавливают левое значение в 1 и правое значение в 2. Природа матрицы смежности такова, что Вы можете двигаться только по одному уровню одновременно, так что давайте посмотрим на дерево с двумя уровнями - корень и непосредственные потомки. Таблица модели смежности напоминала бы следующее:

	CREATE TABLE Personnel
	(emp CHAR(10) NOT NULL PRIMARY KEY,
	boss CHAR(10));

	Personnel

	emp	boss
	=================
	'Albert'	NULL
	'Bert'	'Albert'
	'Charles'	'Albert'
	'Diane'	'Albert'

Давайте поместим модель вложенных множеств в ее собственную рабочую таблицу:

	CREATE TABLE WorkingTree(
	emp CHAR (10),
	boss CHAR(10),
	lft INTEGER NOT NULL DEFAULT 0,
	rgt INTEGER NOT NULL DEFAULT 0);

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

	INSERT INTO WorkingTree
	--convert the root node
	SELECT P0.boss, P0.boss, 1,
	2 * (SELECT COUNT(*) + 1
		FROM Personnel AS P1
		WHERE P0.boss = P1.boss)
		FROM Personnel AS P0; 

Теперь, Вы должны добавить потомков в таблицу вложенных множеств. Первоначальный босс останется тот же самый. Порядок потомков - естественный порядок ключа; в данном случае emp char(10):

	INSERT INTO WorkingTree
	--convert the children
	SELECT DISTINCT P0.emp, P0.boss,
	2 * (SELECT COUNT(DISTINCT emp)
	FROM Personnel AS P1
	WHERE P1.emp <  P0.emp
	AND P0.boss IN (P1.emp, P1.boss)),
	2 * (SELECT COUNT(DISTINCT emp)
	FROM Personnel AS P1
	WHERE P1.emp <  P0.emp
	AND P0.boss IN (P1.boss, P1.emp)) + 1
	FROM Personnel AS P0; 
	

Фактически, Вы можете использовать эту процедуру, чтобы конвертировать модель матрицы смежности в лес деревьев, каждое из которых - модель вложенных множеств, идентифицированная ее корневым значением. Таким образом, генеалогическое дерево Альберта - набор строк, которые имеют Альберта как предка, генеалогическое дерево Берта - набор строк, которые имеют Берта как предка, и так далее. (Эта концепция иллюстрирована в рисунках 1 и 2.

Поскольку первоначальная таблица матрицы смежности повторяет нелистовые узлы, некорневые узлы, в столбцах emp и boss, таблица WorkingTree дублирует узлы как корень в одном дереве и как потомок в другом. Запрос также будет странно себя вести со значением NULL в столбце boss первоначальной таблицы матрицы смежности, так что Вы будете должны очистить таблицу WorkingTree следующим запросом:

	DELETE FROM WorkingTree
	WHERE boss IS NULL OR emp IS NULL; 

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

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

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

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 очень просто. Следующий запрос становится пустым, когда все боссы установлены в одно и тоже значение:

	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

1.

33K

26 октября 2007 года

ASheyin

0 / / 26.10.2007

26 октября 2007, 17:54:19

Второй листинг на второй странице надо писать так (тестил под mySQL 4.x):
SELECT P2.emp, COUNT(*) - 1 AS level
FROM Personnel AS P1, Personnel AS P2
WHERE P2.lft BETWEEN P1.lft AND P2.lft
AND P2.rgt BETWEEN P2.rgt AND P1.rgt
GROUP BY P2.emp
ORDER BY level;

2.

Аноним

15 марта 2006, 16:53:47

Недостатки
1) затруднено хранения множества деревьев, когда один потомок может иметь много предков
2) При изменении структуры меняется вся таблица.