Вложенное множество (модель) (Flk'yuuky buk'yvmfk (bk;yl,))

Модель вложенного множества (англ. Nested set model) — это способ представления вложенных множеств (известных как деревья или иерархии) в реляционных базах данных.

Причины

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

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

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

• поддержка выделенного иерархического типа данных, такого как установка иерархического запроса SQL;
• расширение реляционного языка с помощью манипуляции иерархической структуры, такой как, вложенная реляционная алгебра;
• расширение реляционного языка с помощью транзитивного замыкания такого как SQL-оператор CONNECT, это позволяет использовать отношение родитель-потомок, но выполнение остается дорогостоящим;
• запросы могут быть выражены на языке, который поддерживает итерации и обернут вокруг реляционных операций, таких как PL/SQL, T-SQL или язык программирования общего назначения.

Когда эти решения недоступны или неосуществимы, необходимо использовать другой подход.

Методика

Модель вложенного множества состоит в том, чтобы пронумеровать узлы в соответствии с обходом дерева, который дважды посещает каждый узел. При обоих посещениях назначаются номера в порядке посещения. Обход оставляет два числа для каждого узла, которые хранятся в виде двух атрибутов. Запрос становится недорогим: принадлежность к иерархии можно проверить, сравнив эти числа. Обновление узла требует перенумерации дерева и поэтому является дорогостоящим. Улучшения, в которых вместо целых чисел используются рациональные числа, помогут избежать перенумерации и поэтому узлы обновляются быстрее, хоть и намного сложнее.

Пример

В каталоге магазина одежда может быть классифицирована в соответствии с иерархией, приведённой слева:

Диаграмма Эйлера категорий одежды

Нумерация, назначаемая обходом дерева

Результат нумерации узлов

№ п/п	Узел	Левый	Правый
1	Одежда	1	22
2	Мужская	2	9
3	Женская	10	21
4	Костюмы	3	8
5	Брюки	4	5
6	Куртки	6	7
7	Платья	11	16
8	Юбки	17	18
9	Блузки	19	20
10	Вечерние платья	12	13
11	Сарафаны	14	15

Категория «Одежда», занимающая самое высокое положение в иерархии, охватывает все подчиненные категории. Поэтому узлу задаются левый и правый ключ со значениями 1 и 22, причем последнее значение (22) является удвоенной величиной от общего числа представленных узлов (категорий). Следующий иерархический уровень содержит в себе «Мужской» и «Женский» уровни, которые должны быть учтены предыдущим уровнем. Узлу каждого уровня присваиваются значения левого и правого ключей в соответствии с количеством содержащихся в нём подуровней, как показано в данных таблицы.

Производительность

Можно ожидать, что запросы, использующие вложенное множество, будут быстрее, чем запросы, использующие хранимую процедуру для обхода списка смежности, и поэтому являются более быстрым вариантом для баз данных, в которых отсутствуют встроенные рекурсивные конструкции запросов, таких как MySQL. Однако, можно ожидать, что рекурсивные SQL-запросы будут выполняться сопоставимо для запросов «найти ближайших потомков» и гораздо быстрее для других запросов поиска в глубину, а также являются более быстрым вариантом для баз данных, которые их предоставляют, таких как PostgreSQL, Oracle и Microsoft SQL Server.

Недостатки

Случай использования динамически-бесконечной иерархии дерева баз данных встречается редко. Модель вложенного множества уместна там, где элемент дерева и один или два атрибута являются единственными данными. Модель будет плохим выбором, когда для элементов дерева существуют более сложные реляционные данные. Чтобы учесть произвольную начальную глубину для категории «Транспортные средства» и дочернего элемента «Автомобили» с дочерним элементом «Мерседес», должна быть установлена связь таблицы с помощью внешнего ключа, если только таблица дерева изначально не нормализована. Атрибуты вновь созданного элемента дерева не могут использовать все атрибуты совместно с родительским, дочерним или даже сестринским элементом. Если внешний ключ таблицы установлен для таблицы атрибутов «Растения», то целостность данных дочернего атрибута «Деревья» и его дочернего «Дуба» не предоставляется. Следовательно, в каждом случае для всех атрибутов элемента, вставленного в дерево, должен быть создан внешний ключ таблицы, кроме самых тривиальных вариантов использования.

Если предполагается, что дерево не будет часто меняться, то при первоначальном проектировании системы можно создать правильно нормализованную иерархию таблиц, что приведет к более простым и переносимым SQL-операторам, особенно тем, которые не требуют для изменений в дереве произвольного количества времени выполнения, программно созданных или удаленных таблиц. Для более сложных систем иерархия может быть разработана с помощью реляционных моделей, а не неявной числовой древовидной структуры. Глубина — это просто ещё один атрибут, а не основа для всей архитектуры БД. Как сказано в SQL Antipatterns:

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

Модель не допускает наличие нескольких родительских категорий. Например, «Дуб» может быть дочерним по отношению к «Типу дерева», но также и к «Типу древесины». Для этого необходимо установить дополнительную маркировку или таксономию, что снова приведет к проектировании более сложной структуры, чем простая фиксированная модель.

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

Модель вложенных интервалов не испытывает такой проблемы, но является более сложной для реализации и не так широко известна. Она по-прежнему страдает от проблемы внешних ключей таблицы. Модель вложенных интервалов хранит положение узлов в виде рациональных чисел, выраженных как коэффициенты (n/d).

Варианты

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

SELECT Child.Node, Child.Left, Child.Right
FROM Tree as Parent, Tree as Child
WHERE
    Child.Left BETWEEN Parent.Left AND Parent.Right
    AND NOT EXISTS (    -- Нет промежуточного узла
        SELECT *
        FROM Tree as Mid
        WHERE Mid.Left BETWEEN Parent.Left AND Parent.Right
            AND Child.Left BETWEEN Mid.Left AND Mid.Right
            AND Mid.Node NOT IN (Parent.Node, Child.Node)
    )
    AND Parent.Left = 1  -- Учитывается левый индекс родительского узла

Или, что эквивалентно:

SELECT DISTINCT Child.Node, Child.Left, Child.Right
FROM Tree as Child, Tree as Parent 
WHERE Parent.Left < Child.Left AND Parent.Right > Child.Right  -- Объединение дочерних узлов с предками
GROUP BY Child.Node, Child.Left, Child.Right
HAVING max(Parent.Left) = 1  -- Подмножество тех, у кого данный родительский узел является ближайшим предком

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

Получившееся представление

Узел	Левый	Правый	Глубина
Одежда	1	22	0
Мужская	2	9	1
Женская	10	21	1
Костюмы	3	8	2
Брюки	4	5	3
Куртки	6	7	3
Платья	11	16	2
Юбки	17	18	2
Блузки	19	20	2
Вечерние платья	12	13	3
Сарафаны	14	15	3

В этой модели поиск дочерних элементов, заданных родительским узлом, может быть выполнен с помощью следующего SQL-запроса:

SELECT Child.Node, Child.Left, Child.Right
FROM Tree as Child, Tree as Parent
WHERE
	Child.Depth = Parent.Depth + 1
	AND Child.Left > Parent.Left
	AND Child.Right < Parent.Right
	AND Parent.Left = 1  -- Учитывается левый индекс родительского узла

См. также

• Дерево
• Обход дерева
• Список смежности

Литература

• Joe Celko. Trees and Hierarchies in SQL for Smarties, 2nd Edition (англ.). — San Francisco: Morgan Kaufmann, 2012. — 296 p. — ISBN 0123877334.
• Bill Karwin. SQL Antipatterns (англ.). — Dallas: The Pragmatic Bookshelf, 2010. — 328 p. — ISBN 978-1-93435-655-5.
• Vadim Tropashko. Nested Intervals Tree Encoding in SQL (англ.) // SIGMOD : журнал. — 2005. — 2 June (vol. 1, no. 34).

Ссылки

• Daniel Khan, Lukas Linemayr. PHP PEAR Implementation for Nested Sets (англ.) (25 апреля 2010). Дата обращения: 19 мая 2020.
• Transform any Adjacency List to Nested Sets using MySQL stored procedures (англ.) (21 февраля 2016). Дата обращения: 19 мая 2020.
• PreviousNext. PHP Doctrine DBAL implementation for Nested Sets (англ.). GitHub (2017). Дата обращения: 19 мая 2020.
• vincentcau. Nested Set example in R (англ.). GitHub (2017). Дата обращения: 19 мая 2020.