Из Википедии, свободной энциклопедии
Перейти к навигации Перейти к поиску

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

Мотивация [ править ]

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

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

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

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

Техника [ править ]

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

Пример [ править ]

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

Иерархия: типы одежды
Нумерация, присвоенная обходом дерева
УзелЛевыйВерно
Одежда122
Мужской29
Женский1021 год
Костюмы38
Слаксы45
Куртки67
Платья1116
Юбки1718
Блузки1920
Вечерние платья1213
Солнечные платья1415
Полученное представление

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

Производительность [ править ]

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

Недостатки [ править ]

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

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

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

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

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

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

Варианты [ править ]

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

ВЫБЕРИТЕ  ребенка . Узел ,  ребенок . Слева ,  ребенок . Справа ОТ  Дерева  как  Родителя ,  Дерево  как  Дочернего ГДЕ Дочернее . Слева  МЕЖДУ  родителем . Левый  И  Родительский . Справа И  НЕ  СУЩЕСТВУЕТ  (  - Среднего узла НЕ ВЫБРАТЬ  * FROM  Tree  as  Mid WHERE  Mid . Left  BETWEEN  Parent . Left И  Родитель . Правильно  и  ребенок . Слева  МЕЖДУ  серединой . Слева  И  Середине . Вправо И  Середина . Узел  НЕ  В  ( Родитель . Узел ,  Дочерний . Узел ) ) И  Родитель . Left  =  1  - Указанный левый индекс родительского узла

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

ВЫБЕРИТЕ  DISTINCT  Child . Узел ,  ребенок . Слева ,  ребенок . Справа ОТ  Дерева  как  Дочернего ,  Дерево  как  Родителя  ГДЕ  Родитель . Слева  <  Ребенок . Левый  И  Родительский . Справа  >  Ребенок . Справа  - свяжите дочерние узлы с предками GROUP  BY  Child . Узел ,  ребенок . Слева ,  ребенок .Right HAVING  max ( Parent . Left )  =  1  - Подмножество для тех, у кого данный родительский узел является ближайшим предком

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

УзелЛевыйВерноГлубина
Одежда1220
Мужской291
Женский1021 год1
Костюмы382
Слаксы453
Куртки673
Платья11162
Юбки17182
Блузки19202
Вечерние платья12133
Солнечные платья14153
Полученное представление

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

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

См. Также [ править ]

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

Ссылки [ править ]

  1. ↑ Хейзел, Дэниел. «Использование рациональных чисел для обозначения вложенных множеств». arXiv : 0806.3115 .
  2. ^ Quassnoi (29 сентября 2009 г.), «Список смежности по сравнению с вложенными наборами: MySQL» , Explain Extended , получено 11 декабря 2010 г.
  3. ^ Quassnoi (24 сентября 2009 г.), «Список смежности по сравнению с вложенными наборами: PostgreSQL» , Explain Extended , получено 11 декабря 2010 г.
  4. ^ Quassnoi (28 сентября 2009), "Список смежности по сравнению с вложенными наборами: Oracle" , Объясните Extended , извлекаться 11 декабря 2010
  5. ^ Quassnoi (25 сентября 2009 г.), «Список смежности по сравнению с вложенными наборами: SQL Server» , Explain Extended , получено 11 декабря 2010 г.
  6. ^ Билл, Карвин (17.06.2010). SQL-антипаттерны . п. 328.
  7. ^ Билл, Карвин. SQL-антипаттерны . п. 44.

Внешние ссылки [ править ]

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