Модель вложенного набора
Модель вложенных множеств — это метод представления коллекций вложенных множеств (также известных как деревья или иерархии ) в реляционных базах данных .
Он основан на вложенных интервалах, которые «невосприимчивы к проблемам реорганизации иерархии и позволяют алгоритмически отвечать на иерархические запросы пути предка - без доступа к сохраненному отношению иерархии». [1]
Мотивация
[ редактировать ]Стандартная реляционная алгебра и реляционное исчисление , а также основанные на них операции SQL не могут напрямую выражать все желаемые операции над иерархиями. Модель вложенных множеств является решением этой проблемы.
Альтернативное решение — выражение иерархии как отношение «родитель-потомок». Джо Селко назвал это моделью списка смежности . Если иерархия может иметь произвольную глубину, модель списка смежности не позволяет выражать такие операции, как сравнение содержимого иерархии двух элементов или определение того, находится ли элемент где-то в подиерархии другого элемента. Когда иерархия имеет фиксированную или ограниченную глубину, операции возможны, но являются дорогостоящими из-за необходимости выполнения одного реляционного соединения на каждом уровне. Эту проблему часто называют проблемой спецификации материалов .
Иерархии можно легко выразить, переключившись на графовую базу данных . Альтернативно, для реляционной модели существует несколько решений, которые доступны в качестве обходного пути в некоторых системах управления реляционными базами данных :
- поддержка выделенного типа данных иерархии SQL ; иерархических запросов , например, в средстве
- расширение реляционного языка с помощью манипуляций с иерархией, например, во вложенной реляционной алгебре .
- расширение реляционного языка с помощью транзитивного замыкания , такого как оператор SQL CONNECT; это позволяет использовать отношение родитель-потомок, но выполнение остается дорогостоящим;
- запросы могут быть выражены на языке, который поддерживает итерацию и охватывает реляционные операции, например PL/SQL , T-SQL или язык программирования общего назначения .
Когда эти решения недоступны или неосуществимы, необходимо использовать другой подход.
Техника
[ редактировать ]Модель вложенного множества заключается в нумерации узлов в соответствии с обходом дерева , при котором каждый узел посещается дважды, присваивая номера в порядке посещения, причем при обоих посещениях. В результате для каждого узла остается два числа, которые сохраняются как два атрибута. Запросы становятся недорогими: членство в иерархии можно проверить путем сравнения этих чисел. Обновление требует изменения нумерации и поэтому является дорогостоящим. Уточнения, в которых вместо целых чисел используются рациональные числа , позволяют избежать перенумерации и поэтому обновляются быстрее, хотя и намного сложнее. [2]
Пример
[ редактировать ]В каталоге магазина одежды одежда может быть классифицирована в соответствии с иерархией, представленной слева:
| Узел | Левый | Верно |
|---|---|---|
| Одежда | 1 | 22 |
| Мужской | 2 | 9 |
| Женский | 10 | 21 |
| Костюмы | 3 | 8 |
| брюки | 4 | 5 |
| Куртки | 6 | 7 |
| Платья | 11 | 16 |
| Юбки | 17 | 18 |
| Блузки | 19 | 20 |
| Вечерние платья | 12 | 13 |
| Солнечные платья | 14 | 15 |
Категория «Одежда», занимающая наивысшее положение в иерархии, охватывает все подчиненные категории. Поэтому ему даны значения левого и правого домена 1 и 22, причем последнее значение в два раза превышает общее количество представленных узлов. Следующий иерархический уровень содержит «Мужской» и «Женский», оба содержат внутри себя уровни, которые необходимо учитывать. Узлу данных каждого уровня присваиваются значения левого и правого домена в соответствии с количеством содержащихся в нем подуровней, как показано в данных таблицы.
Производительность
[ редактировать ]Можно ожидать, что запросы, использующие вложенные наборы, будут быстрее, чем запросы, использующие хранимую процедуру для обхода списка смежности, и поэтому являются более быстрым вариантом для баз данных, в которых отсутствуют собственные рекурсивные конструкции запросов, такие как MySQL 5.x. [3] Однако можно ожидать, что рекурсивные SQL-запросы будут выполняться сопоставимо для запросов «найти непосредственных потомков» и намного быстрее для других запросов поиска по глубине, и поэтому они являются более быстрым вариантом для баз данных, которые их предоставляют, таких как PostgreSQL . [4] Оракул , [5] и Microsoft SQL-сервер . [6] Раньше в MySQL отсутствовали конструкции рекурсивных запросов, но в версии 8 такие функции были добавлены. [7]
Недостатки
[ редактировать ]Вариант использования динамической бесконечной иерархии дерева базы данных встречается редко. Модель вложенного набора подходит там, где единственными данными являются элемент дерева и один или два атрибута, но является плохим выбором, когда для элементов дерева существуют более сложные реляционные данные. Учитывая произвольную начальную глубину для категории «Транспортные средства» и дочернего элемента «Автомобили» с дочерним элементом «Мерседес», должна быть установлена связь таблицы внешнего ключа, если только древовидная таблица не является изначально ненормализованной. Атрибуты вновь созданного элемента дерева не могут разделять все атрибуты с родительским, дочерним или даже одноуровневым элементом. Если для таблицы атрибутов «Растения» установлена таблица внешнего ключа, целостность данных дочернего атрибута «Деревья» и его дочернего элемента «Дуб» не обеспечивается. Следовательно, в каждом случае, когда элемент вставляется в дерево, таблица внешних ключей атрибутов элемента должна быть создана для всех случаев использования, кроме самых тривиальных.
Если не предполагается, что дерево будет часто меняться, при первоначальном проектировании системы можно создать должным образом нормализованную иерархию таблиц атрибутов, что приведет к более простым и переносимым операторам SQL; в частности, те, которые не требуют произвольного количества времени выполнения, программно созданных или удаленных таблиц для внесения изменений в дерево. Для более сложных систем иерархию можно разработать с помощью реляционных моделей, а не неявной числовой древовидной структуры. Глубина элемента — это просто еще один атрибут, а не основа всей архитектуры БД. Как сказано в «Антипаттернах SQL» : [8]
Вложенные наборы — это умное решение, возможно, даже слишком умное. Он также не поддерживает ссылочную целостность. Его лучше всего использовать, когда вам нужно запрашивать дерево чаще, чем изменять его. [9]
Модель не позволяет использовать несколько родительских категорий. Например, «Дуб» может быть дочерним элементом «Тип дерева», но также и «Тип дерева». Для этого необходимо установить дополнительную маркировку или таксономию, что снова приводит к более сложной конструкции, чем простая фиксированная модель.
Вложенные наборы очень медленны для вставки, поскольку требуют обновления значений левого и правого домена для всех записей в таблице после вставки. Это может вызвать большую нагрузку на базу данных, поскольку многие строки перезаписываются и индексы перестраиваются. Однако если в таблице можно хранить лес небольших деревьев вместо одного большого дерева, накладные расходы могут быть значительно уменьшены, поскольку необходимо обновлять только одно маленькое дерево.
Модель вложенных интервалов не страдает от этой проблемы, но ее сложнее реализовать, и она не так хорошо известна. Он по-прежнему страдает от проблемы с реляционной таблицей внешних ключей. Модель вложенных интервалов сохраняет положение узлов в виде рациональных чисел, выраженных в виде частных (n/d). [1]
Вариации
[ редактировать ]Использование модели вложенных множеств, как описано выше, имеет некоторые ограничения производительности во время определенных операций обхода дерева. Например, попытка найти непосредственные дочерние узлы для родительского узла требует сокращения поддерева до определенного уровня, как в следующем примере кода 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 ( -- No Middle Node
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 -- Given Parent Node Left Index
Или, что то же самое:
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 -- associate Child Nodes with ancestors
GROUP BY Child.Node, Child.Left, Child.Right
HAVING max(Parent.Left) = 1 -- Subset for those with the given Parent Node as the nearest ancestor
Запрос будет более сложным при поиске дочерних элементов глубиной более одного уровня. Чтобы преодолеть это ограничение и упростить обход дерева, в модель добавляется дополнительный столбец для поддержания глубины узла внутри дерева.
| Узел | Левый | Верно | Глубина |
|---|---|---|---|
| Одежда | 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.Depth = 1 -- Given Parent Node Left Index
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ «Кодирование дерева вложенных интервалов в SQL», Вадим Тропашко; Oracle Corp. Оригинал на https://web.archive.org/web/20111119165033/http://sigmod.org/publications/sigmod-record/0506/p47-article-tropashko.pdf .
- ^ Хейзел, Дэниел (2008). «Использование рациональных чисел для определения вложенных множеств». arXiv : 0806.3115 [ cs.DB ].
- ^ Quassnoi (29 сентября 2009 г.), «Список смежности и вложенные наборы: MySQL» , объяснение расширенного , получено 11 декабря 2010 г.
- ^ Quassnoi (24 сентября 2009 г.), «Список смежности и вложенные наборы: PostgreSQL» , объяснение расширенного , получено 11 декабря 2010 г.
- ^ Quassnoi (28 сентября 2009 г.), «Список смежности и вложенные множества: Oracle» , объяснение расширенного , получено 11 декабря 2010 г.
- ^ Quassnoi (25 сентября 2009 г.), «Список смежности и вложенные наборы: SQL Server» , Расширенное объяснение , получено 11 декабря 2010 г.
- ^ «MySQL :: Справочное руководство MySQL 8.0 :: 13.2.15 С (Общие табличные выражения)» . dev.mysql.com . Проверено 1 сентября 2021 г.
- ^ Билл, Карвин (17 июня 2010 г.). SQL-антипаттерны . п. 328.
- ^ Билл, Карвин. SQL-антипаттерны . п. 44.
Внешние ссылки
[ редактировать ]- Ссылки Троэльса на иерархические данные в СУБД.
- Управление иерархическими данными в реляционных базах данных
- Реализация PHP PEAR для вложенных наборов — Дэниел Хан
- Преобразуйте любой список смежности во вложенные наборы с помощью хранимых процедур MySQL.
- Реализация PHP Doctrine DBAL для вложенных наборов - от НазадСледующая
- R Nested Set — пример вложенного набора в R