Древовидные структуры в SQL

sql.ru

По материалам статьи Joe Celko на intelligententerprise.com " Trees in SQL"

Обзор некоторых общих вопросов, касающихся древовидных структур и иерархии в SQL

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

CREATE TABLE Personnel
(emp CHAR(10) NOT NULL PRIMARY KEY,
boss CHAR(10) DEFAULT NULL REFERENCES Personnel(emp),
salary DECIMAL(6,2) NOT NULL DEFAULT 100.00);

Personnel emp	boss	salary
'Albert'	'NULL'	1,000.00
'Bert'	'Albert'	900.00
'Chuck'	'Albert'	900.00
'Donna'	'Chuck'	800.00
'Eddie'	'Chuck'	700.00
'Fred'	'Chuck'	600.00

Таблица 1. Список смежных вершин графа

Другим способом представления древовидной структуры являются вложенные множества. Поскольку SQL является языком, предназначеным для работы со множествами, то эта модель является более предпочтительной, чем стандартный пример списка смежных вершин графа, который более часто встречается в литературе. Давайте создадим тестовую таблицу Personnel, не обращая пока внимания на поля lft и rgt:

CREATE TABLE Personnel
(emp CHAR(10) NOT NULL PRIMARY KEY,
lft INTEGER NOT NULL UNIQUE CHECK (lft > 0),
rgt INTEGER NOT NULL UNIQUE CHECK (rgt > 1),
CONSTRAINT order_okay CHECK (lft < rgt) );

Эта проблема часто описывается в учебниках с помощью поля для Сотрудника (Personnel emp) и одного из его Начальников (Boss). Следующая таблица (Таблица 2) - за исключением полей lft и rgt - в теории графов называется список смежных вершин графа или пары вершин графа, смежные друг другу.

Personnel emp	ift	rgt
'Albert'	1	12
'Bert'	2	3
'Chuck'	4	11
'Donna'	5	6
'Eddie'	7	8
'Fred'	9	10

Таблица 2. Вложенные множества

Структура организации может быть представлена в виде направленного графа, как показано на рис.1

Albert (1, 12) ¦ -------------+--------------- ¦ ¦ ¦ ¦ Bert (2, 3) Chuck (4, 11) ¦ --------------------------------------------------------- ¦ ¦ ¦ ¦ ¦ ¦ Donna (5, 6) Eddie (7, 8) Fred (9, 10)

Таблица 1 является денормализованной по нескольким направлениям. Мы моделируем структуру персонала и организации в одной таблице. Ради экономии дискового пространства представим себе, что имя сотрудника является также названием его должности и что мы имеем еще одну таблицу, которая содержит информацию о сотрудниках и занимаемых ими должностях.

Еще одной проблемой, связанной с моделью "Список смежных вершин графа" является то, что поля Начальник (Boss) и Сотрудник (Personnel emp) содержат данные одинакового вида (имя сотрудника) и поэтому эти данные должны располагаться в одном и том же поле нормализованной таблицы. Для подтверждения того, что эти данные не нормализованы, предположим, что "Chuck" изменил свое имя на "Charles"; вы должны изменить его имя в обеих полях и в нескольких местах. По определению, в нормализованной таблице одна сущность должна встречаться лишь однажды и только в одном месте.

Последней проблемой является то, что "Список смежных вершин графа" не является подчиненной (субординационной) моделью. Полномочия передаются сверху вниз в иерархическом порядке, но если я уберу сотрудника по имени "Chuck", я разорву всю его подчиненность от сотрудника по имени "Albert". В некоторых случаях (например, для трубопроводов) это справедливо, но в нашем случае мы не предполагаем такой ситуации.

Чтобы изобразить древовидную структуру в виде вложенных множеств, заменим вершины графа овалами, где подчиненные овалы вложены один в другой. Основание дерева будет представлено самым большим овалом, который содержит все остальные овалы. Концевые вершины будут представлены самыми внутренними овалами, не содержащими внутри никаких других овалов, а вложенность будет показана иерархическими взаимоотношениями. Поля rgt и lft (я не использую зарезервированные слова RIGHT и LEFT) - это именно то, что показывает вложенность.

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

Эта модель натуральным образом показывает как увеличивается количество частей, потому что последняя сборка состоит из вложенных сборок, которые, в конечном итоге, состоят из отдельных частей.

Теперь мы видим, что поле Начальник (Boss) является избыточным и денормализованным, следовательно оно может быть удалено. Обратите также внимание на то, что древовидная структура может быть размещена в одной таблице, а вся информация о вершинах графа может быть помещена в другую таблицу. Вы можете связать обе таблицы между собой по номеру сотрудника.

Для преобразования графа в модель вложенных множеств вспомните о маленьком червячке, ползущем вдоль дерева. Червь начинает двигаться сверху - от основания - и обползает вокруг всего дерева. Когда он приходит к вершине, он присваивает значение стороне, которую он посещает и увеличивает значение счетчика на единицу. Каждая вершина получает два значения - одно для правой стороны и одно для левой. (Специалисты называют это модифицированным алгоритмом обхода вершин графа в прямом порядке.) И в заключение, удалим за ненадобностью поле "Personnel.Boss", которое представляло ребро графа.

Это дает нам некоторые предсказуемые результаты, которые мы можем использовать при построении запросов. Основание всегда можно представить в виде:
(left = 1, right = 2 * (SELECT COUNT(*) FROM TreeTable));
для вершин всегда справедливо (left + 1 = right); условие BETWEEN определяет поддерево и т.д. Ниже представлены некоторые базовые запросы, которые могут быть вам полезны:

1. Найти сотрудника и всех его начальников, независимо от глубины вложения.

SELECT P2.* FROM Personnel AS P1, Personnel AS P2 WHERE P1.lft BETWEEN P2.lft AND P2.rgt AND P1.emp = :myemployee;

2. Найти сотрудника и всех его подчиненных. (Этот запрос симметричен первому.)

SELECT P1.* -- (В оригинале опечатка: SELECT P2.*) FROM Personnel AS P1, Personnel AS P2 WHERE P1.lft BETWEEN P2.lft AND P2.rgt AND P2.emp = :myemployee;

3. Добавьте GROUP BY и обобщенные функции к этим базовым запросам и вы получите иерархические отчеты. Например, суммарный лимит заработной платы, которой распоряжается каждый сотрудник:

SELECT P2.emp, SUM(S1.salary) FROM Personnel AS P1, Personnel AS P2, Salaries AS S1 WHERE P1.lft BETWEEN P2.lft AND P2.rgt AND P1.emp = S1.emp GROUP BY P2.emp;

4. Найти уровень (глубину вложения) каждой вершины, что дает возможность распечатать древовидную структуру как листинг с отступами.

SELECT COUNT(P2.emp) AS indentation, P1.emp FROM Personnel AS P1, Personnel AS P2 WHERE P1.lft BETWEEN P2.lft AND P2.rgt GROUP BY P1.emp ORDER BY P1.emp; -- (В оригинале опечатка: ORDER BY P1.lft)

5. Модель вложенных множеств содержит неявный порядок смежных вершин, которого нет в модели "Список смежных вершин графа". Добавление новой вершины как смежной крайней правой:

BEGIN DECLARE right_most_sibling INTEGER; SET right_most_sibling = (SELECT rgt FROM Personnel WHERE emp = :your_boss); UPDATE Personnel SET lft = CASE WHEN lft > right_most_sibling THEN lft + 2 ELSE lft END, rgt = CASE WHEN rgt >= right_most_sibling THEN rgt + 2 ELSE rgt END WHERE rgt >= right_most_sibling; INSERT INTO Personnel (emp, lft, rgt) VALUES ('New Guy', right_most_sibling, (right_most_sibling + 1)) END;

6. Для преобразования модели "Список смежных вершин графа" в модель вложенных множеств можно использовать a push down stack алгоритм. Предположим, что мы имеем следующую таблицу:

-- Древовидная структура содержащая модель "Список смежных вершин графа" CREATE TABLE Tree (emp CHAR(10) NOT NULL, boss CHAR(10)); INSERT INTO Tree SELECT emp, boss FROM Personnel; -- Stack starts empty, will holds the nested set model -- Изначально стек пустой, он будет содержать модель вложенных множеств CREATE TABLE Stack (stack_top INTEGER NOT NULL, emp CHAR(10) NOT NULL, lft INTEGER, rgt INTEGER); BEGIN ATOMIC DECLARE counter INTEGER; DECLARE max_counter INTEGER; DECLARE current_top INTEGER; SET counter = 2; SET max_counter = 2 * (SELECT COUNT(*) FROM Tree); SET current_top = 1; INSERT INTO Stack SELECT 1, emp, 1, NULL FROM Tree WHERE boss IS NULL; DELETE FROM Tree WHERE boss IS NULL; WHILE counter <= (max_counter - 2) LOOP IF EXISTS (SELECT * FROM Stack AS S1, Tree AS T1 WHERE S1.emp = T1.boss AND S1.stack_top = current_top) THEN BEGIN -- push when top has subordinates, set lft value -- вершина имеет подчиненные вершины, заносим новое значение lft в стек INSERT INTO Stack SELECT (current_top + 1), MIN(T1.emp), counter, NULL FROM Stack AS S1, Tree AS T1 WHERE S1.emp = T1.boss AND S1.stack_top = current_top; DELETE FROM Tree WHERE emp = (SELECT emp FROM Stack WHERE stack_top = current_top + 1); SET counter = counter + 1; SET current_top = current_top + 1; END ELSE BEGIN -- pop the stack and set rgt value -- выталкиваем значение из стека и определяем значение rgt UPDATE Stack SET rgt = counter, stack_top = -stack_top -- pops the stack WHERE stack_top = current_top SET counter = counter + 1; SET current_top = current_top - 1; END IF; END LOOP; END;

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