Вложенное множество (модель)
Модель вложенного множества (англ. Nested set model) — это способ представления вложенных множеств[англ.] (известных как деревья или иерархии) в реляционных базах данных.
Причины
[править | править код]Стандартная реляционная алгебра и реляционное исчисление, а также операции SQL, основанные на них, не могут напрямую выразить все желаемые операции над иерархиями. Вложенная модель множества является решением этой проблемы.
Альтернативным решением является выражение иерархии как отношения родитель-потомок. Селко назвал это списком смежности. Если иерархия может иметь произвольную глубину, то список смежности не допускает выражения операций, как сравнение содержимого иерархий двух элементов или определение того, находится ли элемент где-то в подиерархии другого элемента. Когда иерархия имеет фиксированную или ограниченную глубину, операции возможны, но дорогостоящие, из-за необходимости выполнения на каждом уровне одного реляционного соединения. Это часто называют проблемой спецификации материалов[1].
Иерархии могут быть легко выражены путем переключения на графовую базу данных. В качестве альтернативы, существует несколько решений для реляционной модели, которые доступны в качестве обходного пути в некоторых системах управления реляционными базами данных:
- поддержка выделенного иерархического типа данных, такого как установка иерархического запроса SQL;
- расширение реляционного языка с помощью манипуляции иерархической структуры, такой как, вложенная реляционная алгебра;
- расширение реляционного языка с помощью транзитивного замыкания такого как SQL-оператор CONNECT, это позволяет использовать отношение родитель-потомок, но выполнение остается дорогостоящим;
- запросы могут быть выражены на языке, который поддерживает итерации и обернут вокруг реляционных операций, таких как PL/SQL, T-SQL или язык программирования общего назначения.
Когда эти решения недоступны или неосуществимы, необходимо использовать другой подход.
Методика
[править | править код]Модель вложенного множества состоит в том, чтобы пронумеровать узлы в соответствии с обходом дерева, который дважды посещает каждый узел. При обоих посещениях назначаются номера в порядке посещения. Обход оставляет два числа для каждого узла, которые хранятся в виде двух атрибутов. Запрос становится недорогим: принадлежность к иерархии можно проверить, сравнив эти числа. Обновление узла требует перенумерации дерева и поэтому является дорогостоящим. Улучшения, в которых вместо целых чисел используются рациональные числа, помогут избежать перенумерации и поэтому узлы обновляются быстрее, хоть и намного сложнее[2].
Пример
[править | править код]В каталоге магазина одежда может быть классифицирована в соответствии с иерархией, приведённой слева:
| № п/п | Узел | Левый | Правый |
|---|---|---|---|
| 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[3]. Однако, можно ожидать, что рекурсивные SQL-запросы будут выполняться сопоставимо для запросов «найти ближайших потомков» и гораздо быстрее для других запросов поиска в глубину, а также являются более быстрым вариантом для баз данных, которые их предоставляют, таких как PostgreSQL[4], Oracle[5] и Microsoft SQL Server[6].
Недостатки
[править | править код]Случай использования динамически-бесконечной иерархии дерева баз данных встречается редко. Модель вложенного множества уместна там, где элемент дерева и один или два атрибута являются единственными данными. Модель будет плохим выбором, когда для элементов дерева существуют более сложные реляционные данные. Чтобы учесть произвольную начальную глубину для категории «Транспортные средства» и дочернего элемента «Автомобили» с дочерним элементом «Мерседес», должна быть установлена связь таблицы с помощью внешнего ключа, если только таблица дерева изначально не нормализована. Атрибуты вновь созданного элемента дерева не могут использовать все атрибуты совместно с родительским, дочерним или даже сестринским элементом. Если внешний ключ таблицы установлен для таблицы атрибутов «Растения», то целостность данных дочернего атрибута «Деревья» и его дочернего «Дуба» не предоставляется. Следовательно, в каждом случае для всех атрибутов элемента, вставленного в дерево, должен быть создан внешний ключ таблицы, кроме самых тривиальных вариантов использования.
Если предполагается, что дерево не будет часто меняться, то при первоначальном проектировании системы можно создать правильно нормализованную иерархию таблиц, что приведет к более простым и переносимым SQL-операторам, особенно тем, которые не требуют для изменений в дереве произвольного количества времени выполнения, программно созданных или удаленных таблиц. Для более сложных систем иерархия может быть разработана с помощью реляционных моделей, а не неявной числовой древовидной структуры. Глубина — это просто ещё один атрибут, а не основа для всей архитектуры БД. Как сказано в SQL Antipatterns[7]:
Модель вложенного множества это умное решение, может быть, даже слишком умное. Она также не поддерживает ссылочную целостность. Лучше всего используется, когда вам нужно запрашивать дерево чаще, чем его изменять[8].
Модель не допускает наличие нескольких родительских категорий. Например, «Дуб» может быть дочерним по отношению к «Типу дерева», но также и к «Типу древесины». Для этого необходимо установить дополнительную маркировку или таксономию, что снова приведет к проектировании более сложной структуры, чем простая фиксированная модель.
Вложенные множества очень медленны для вставок, поскольку после вставки требуют обновления значений левого и правого ключа для всех записей в таблице. Это может вызвать большую нагрузку на базу данных, так как многие строки переписываются и индексы перестраиваются. Однако если в таблице можно хранить лес небольших деревьев вместо одного большого дерева, это может значительно снизить расходы, поскольку необходимо обновить только одно маленькое дерево.
Модель вложенных интервалов[англ.] не испытывает такой проблемы, но является более сложной для реализации и не так широко известна. Она по-прежнему страдает от проблемы внешних ключей таблицы. Модель вложенных интервалов хранит положение узлов в виде рациональных чисел, выраженных как коэффициенты (n/d)[9].
Варианты
[править | править код]Использование модели вложенного множества имеет некоторые ограничения производительности при выполнении определённых операций обхода дерева. Например, при поиске дочернего узла, заданного родительским узлом, требуется сократить поддерево до определённого уровня, как в следующем примере кода 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, 2012.
- ↑ Hazel, Daniel. "Using rational numbers to key nested sets". arXiv:0806.3115.
{{cite arXiv}}: Неизвестный параметр|accessdate=игнорируется (справка) - ↑ Quassnoi. Adjacency list vs. nested sets: MySQL (29 сентября 2009). Дата обращения: 19 мая 2020. Архивировано 1 октября 2020 года.
- ↑ Quassnoi. Adjacency list vs. nested sets: PostgreSQL (24 сентября 2009). Дата обращения: 19 мая 2020. Архивировано 14 августа 2020 года.
- ↑ Quassnoi. Adjacency list vs. nested sets: Oracle (28 сентября 2009). Дата обращения: 19 мая 2020. Архивировано 30 октября 2020 года.
- ↑ Quassnoi. Adjacency list vs. nested sets: SQL Server (25 сентября 2009). Дата обращения: 19 мая 2020. Архивировано 26 сентября 2020 года.
- ↑ Bill Karwin. SQL Antipatterns, 2010.
- ↑ Bill Karwin. SQL Antipatterns, 2010, p. 44.
- ↑ Vadim Tropashko. Nested Intervals Tree Encoding in SQL, 2005.
Литература
[править | править код]- 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.