Деревья в SQL - Обработка деревьев

Written on . Posted in Язык запросов SQL

ОГЛАВЛЕНИЕ

Страница 5 из 6

Обработка деревьев 

Наиболее хитрая часть обработки деревьев в 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;

базы данных форум