Модель вложенного множества - Nested set model

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

Мотивация

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

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

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

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

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

Техника

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

пример

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

Иерархия: типы одежды

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

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

Спектакль

Можно ожидать, что запросы с использованием вложенных наборов будут быстрее, чем запросы с использованием хранимая процедура для обхода списка смежности, и поэтому это более быстрый вариант для баз данных, в которых отсутствуют собственные рекурсивные конструкции запросов, такие как MySQL.^[2] Однако можно ожидать, что рекурсивные SQL-запросы будут работать сравнимо с запросами на поиск непосредственных потомков и намного быстрее с другими запросами глубинного поиска, и поэтому они являются более быстрым вариантом для баз данных, которые их предоставляют, например PostgreSQL,^[3] Oracle,^[4] и Microsoft SQL Server.^[5]

Недостатки

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

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

Вложенные наборы - умное решение, возможно, слишком умное. Он также не поддерживает ссылочную целостность. Лучше всего использовать его, когда вам нужно запрашивать дерево чаще, чем нужно его изменять.^[7]

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

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

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

Вариации

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

ВЫБРАТЬ Ребенок.Узел, Ребенок.Оставили, Ребенок.ПравильноИЗ Дерево так как Родитель, Дерево так как РебенокКУДА	Ребенок.Оставили МЕЖДУ Родитель.Оставили И Родитель.Правильно	И НЕТ СУЩЕСТВУЮТ (    - Нет среднего узла		ВЫБРАТЬ *		ИЗ Дерево так как Середина		КУДА Середина.Оставили МЕЖДУ Родитель.Оставили И Родитель.Правильно     			И Ребенок.Оставили МЕЖДУ Середина.Оставили И Середина.Правильно			И Середина.Узел НЕТ В (Родитель.Узел, Ребенок.Узел)	)	И Родитель.Оставили = 1  - Указанный левый индекс родительского узла

Или, что то же самое:

ВЫБРАТЬ ОТЧЕТЛИВЫЙ Ребенок.Узел, Ребенок.Оставили, Ребенок.ПравильноИЗ Дерево так как Ребенок, Дерево так как Родитель КУДА Родитель.Оставили < Ребенок.Оставили И Родитель.Правильно > Ребенок.Правильно  - связать дочерние узлы с предкамиГРУППА ОТ Ребенок.Узел, Ребенок.Оставили, Ребенок.ПравильноИМЕЕТ Максимум(Родитель.Оставили) = 1  - Подмножество для тех, у кого данный родительский узел является ближайшим предком

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

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

ВЫБРАТЬ Ребенок.Узел, Ребенок.Оставили, Ребенок.ПравильноИЗ Дерево так как Ребенок, Дерево так как РодительКУДА	Ребенок.Глубина = Родитель.Глубина + 1	И Ребенок.Оставили > Родитель.Оставили	И Ребенок.Правильно < Родитель.Правильно	И Родитель.Глубина = 1  - Указанный левый индекс родительского узла

Смотрите также

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

Рекомендации

внешняя ссылка

• Ссылки Troels на иерархические данные в СУБД
• Управление иерархическими данными в реляционных базах данных
• Реализация PHP PEAR для вложенных наборов - Дэниел Хан
• Преобразование любого списка смежности во вложенные наборы с помощью хранимых процедур MySQL
• Реализация PHP Doctrine DBAL для вложенных наборов - от PreviousNext
• R Вложенный набор - Пример вложенного множества в R