Способ «Маршрут обхода»

Согласно теории графов, для обхода дерева существует три способа: можно проходить узлы в префиксном, в инфиксном и в суффиксном порядке. Префиксный порядок обхода дерева рекурсивно определяется так: сначала корень дерева, потом узлы левого поддерева в префиксном порядке, наконец, узлы правого поддерева в префиксном порядке. Пример обхода в префиксном порядке приведён на рисунке ниже.

Хранение маршрута обхода дерева в префиксном порядке также встречается у Джо Селко [26], однако в книге способ носит не вполне соответствующее его сути название «вложенные множества» (nested sets).

Маршрут обхода дерева в префиксном порядке Каждый квадрат на рисунке обозначает узел

Рис. 33. Маршрут обхода дерева в префиксном порядке Каждый квадрат на рисунке обозначает узел, цифра в левом его углу является порядковым номером этапа маршрута при входе в узел, а цифра справа — номером при выходе, когда тем же способом пройдены все потомки.

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

Схема способа «Маршрут обхода»

Рис. 34. Схема способа «Маршрут обхода»

Табл. 10. Пример заполнения таблицы в способе «Маршрут обхода»

id_area

name

id_input

id_output

1

Санкт-Петербург

1

14

2

Московский район

2

7

3

МО Новоизмайловское

3

4

4

МО Кузнецовское

5

6

5

Невский район

8

11

6

МО Рыбацкое

9

10

7

Центральный район

12

13

Избыточность хранения делает необходимым пересчёт порядка обхода при добавлении новых или перемещении существующих узлов (удаление можно игнорировать). В соответствующем триггере для этого необходимо реализовать последовательный порядок обхода. Но, например, если добавляется элемент самого нижнего уровня, то приходится пересчитывать все номера «выше» или «правее», что может быть сравнимо с затратами на пересчёт маршрута по всему дереву.

Для минимизации последствий таких пересчётов, можно нумеровать входы и выходы из узлов с некоторым интервалом, например, 100 или 1000, что в значительной степени зависит от предварительных оценок количества хранимых узлов дерева. В этом случае вставка новых элементов будет происходить без полной перенумерации.

В запросе не вычисляется глубина узла. Добавление этой функции приведёт к введению выполняющегося для каждого элемента агрегирующего подзапроса (см. листинг 15).

SELECT al.id_area, al.id_input, al.name FROM areas al

INNER JOIN areas a2

ON al.id_input BETWEEN a2.id_input AND a2.id_output WHERE a2.id_area = 2 /* корень поддерева */

ORDER BY al.id_input

Табл. 11. Результат выборки поддерева (маршрут обхода)

id_area

id_input

name

2

2

Московский район

3

3

МО Новоизмайловское

4

5

МО Кузнецовское

Выборка предков

Выборка всех предков симметрична предыдущему запросу относительно BETWEEN. В запросе не вычисляется глубина узла.

SELECT al.id_area, al.id_input, al.name FROM areas al

INNER JOIN areas a2

ON a2.id_input BETWEEN al.id_input AND al.id_output WHERE a2.id_area = 4 /* узел */

ORDER BY al.id_input

Табл. 12. Результат выборки предков (маршрут обхода)

id_area

id_input

name

1

1

Санкт-Петербург

2

2

Московский район

4

5

МО Кузнецовское

Вхождение в поддерево

SELECT result = CASE

WHEN EXISTS(SELECT 1 FROM areas as al, areas as a2 WHERE al.id_area = 4 /* узел */

AND a2.id_area = 2 /* корень поддерева */ AND al.id_input BETWEEN a2.id_input AND a2.id_output)

THEN N'Входит'

ELSE N'He входит'

END

Подсчёт количества всех потомков узла

SELECT COUNT(1) AS qty FROM (SELECT al.id_area FROM areas al

INNER JOIN areas a2

ON al.id_input BETWEEN a2.id_input AND

a2.id_output

WHERE a2.id_area = 2 /* узел */

) t

Определение высоты узла

SELECT COUNT(1) AS level FROM (SELECT al.id_area FROM areas al

INNER JOIN areas a2

ON a2.id_input BETWEEN al.id_input AND

al.id_output

WHERE a2.id_area = 4 /* узел */

) t

Способ «Материализованные пути»

Суть способа заключается в хранении пути от вершины до данного узла в явном виде. Путь одновременно является и ключом. Наиболее близкая аналогия представления способа — знакомая всем нумерация частей, разделов и глав в книге.

Табл. 13. Пример заполнения таблицы areas (материализованные пути)

area_path

name

1

Санкт-Петербург

1.1

Московский район

1.1.1

МО Новоизмайловское

1.1.2

МО Кузнецовское

1.2

Невский район

1.2.1

МО Рыбацкое

1.3

Центральный район

Способ является наиболее наглядным с точки зрения кодификации элементов: каждый узел получает значение, которое пригодно для восприятия пользователем. Путь и его части несут смысловую нагрузку. Такие свойства используются в классификациях, предназначенных для широкого применения, например, в стандартизованных справочниках территорий (ОКАТО), отраслей экономики (ОКВЭД, NAICS), медицинских диагнозов (МКБ — международный классификатор болезней) и во многих других областях.

Схема способа «Материализованные пути»

Рис. 35. Схема способа «Материализованные пути»

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

Однако запросы не всегда могут быть эффективно реализованы на уровне СУБД, так как, например, поиск подстроки, вызывает сканирование таблицы вместо поиска по ключу или его начальному фрагменту.

Выборка поддерева

В запросе не вычисляется глубина узла.

SELECT *

FROM areas

WHERE area_j?ath LIKE '1.1%' /* корень поддерева */

ORDER BY area_j?ath

Табл. 14. Результат выборки поддерева (материализованные пути)

area_path

name

1.1

Московский район

1.1.1

МО Новоизмайловское

1.1.2

МО Кузнецовское

В запросе не вычисляется глубина узла.

SELECT *

FROM areas

WHERE *1.2.1* /* узел */ LIKE area_path + *%'

ORDER BY area_j?ath

Табл. 15. Результат выборки предков (материализованные пути)

area_path

name

1

Санкт-Петербург

1.2

Невский район

1.2.1

МО Рыбацкое

Вхождение в поддерево

WITH

node (area_j?ath) AS (SELECT *1.2.1*), subtree(area_path) AS (SELECT *1.2*)

SELECT result = CASE

WHEN EXISTS(SELECT 1 FROM node, subtree

WHERE SUBSTRING (node. area_j?ath, 1,

LEN (subtree. area_j?ath) )

= subtree.area_path)

THEN N'Входит'

ELSE N'He входит'

END

Подсчёт количества всех потомков узла

SELECT COUNT(1) - 1 AS qty FROM areas

WHERE area_j?ath LIKE '1.1%' /* корень поддерева */

Определение высоты узла

SELECT COUNT(1) AS level FROM areas

WHERE '1.1.2' /* узел */ LIKE area_path + '%'

Критерии сравнения

В качестве критериев сравнения приведённых способов используются следующие показатели.

  • Сложность схемы базы данных. Определяется как количество достаточных для реализации таблиц, ссылок (связей) между ними и колонок, содержащих данные о структуре графа (матрице смежности).
  • Запросы на извлечение данных. Характеризуются количеством необходимых соединений. Наиболее сложным вариантом является рекурсивный запрос, в котором число соединений в цикле соответствует глубине иерархии. Например, выборка поддерева с 5 уровнями будет осуществляться в цикле из 5 итераций, результат каждой из которых соединяется с предыдущим.
  • Запросы на изменение данных. Запросы на изменение данных, такие, как вставка и удаление узлов, характеризуются необходимостью дополнительных операций со связанными узлами и обновлением избыточных данных.
  • Избыточность хранения данных и необходимость поддержки целостности. Характеризуется необходимостью дополнительного императивного кода (триггеров) помимо декларативной ссылочной целостности.

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

Табл. 16. Сравнительные характеристики рассмотренных способов

Списки

смежности

Подмноже

ства

Хранение маршрута обхода

Материализованные пути

Сложность схемы базы данных (количество)

Таблиц

1

2

1

1

Ссылок

1

2

0

0

Колонок

3

5

4

2

Списки

смежности

Подмноже

ства

Хранение маршрута обхода

Материализованные пути

Запросы на извлечение данных (число соединений)

Выборка поддерева, число соединений

H-N+1 (*)

2

2

1

Выборка пути от узла до корня (предков)

N (*)

2

2

1

Вхождение в поддерево

H-N+1 (*)

1

2

0 (сравнение значений двух строк)

Подсчёт количества всех потомков узла

H-N+1 (*)

1

2

1

Определение высоты узла

N (*)

1

2

1

Соответствие порядка следования узлов сортировке по ключу

нет

нет

нет

да

Запросы на изменение данных

Прямая вставка новых узлов для листа

да

нет

да, если есть свободный номер, иначе пересчёт диапазонов

да

Прямая вставка новых узлов для внутренней вершины

нет, изменение ссылки потомков

нет, перегруппировка подмножеств

нет, пересчёт диапазонов

нет, пересчёт номеров узлов

Прямое перемещение поддерева

да, изменение ссылки на предка

нет, перегруппировка подмножеств

нет, пересчёт диапазонов

нет, пересчёт номеров узлов

Списки

смежности

Подмноже

ства

Хранение маршрута обхода

Материализованные пути

Прямое удаление поддерева

нет, рекурсивное (каскадная DRI)

нет, перегруппировка подмножеств

да, заданием диапазона

да, заданием шаблона подстроки

Избыточность хранения

нет

да

да

да

оценка избыточности хранения дерева из N вершин

N

не хуже ((N-1)/2)*N

2-N

не хуже ((N-1)/2)*N

Ограничения высоты дерева

нет

нет

нет

да

Императивная поддержка целостности

нужна

нужна

нужна

нужна

Обозначения в таблице: (*) - рекурсивный запрос, Н - высота дерева, N - текущий уровень.

Следует понимать, что в приведённых решениях нет «плохих» или «хороших» способов: проектировщик может сделать свой выбор оптимального решения исходя из условий конкретной задачи на основании предлагаемого множества критериев. Благодаря своей интуитивности, наиболее часто встречается на практике реализация списка смежности, однако необходимость рекурсивных запросов является узким местом, несомненно влияющим на производительность ваших приложений.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >