[sql] Каковы варианты хранения иерархических данных в реляционной базе данных?



2 Answers

Это очень частый ответ на ваш вопрос, но я надеюсь, что он еще полезен.

Microsoft SQL Server 2008 реализует две функции, которые чрезвычайно полезны для управления иерархическими данными:

  • тип данных HierarchyId .
  • общие выражения таблицы, используя ключевое слово.

Взгляните на «Моделировать свои иерархии данных с SQL Server 2008» от Kent Tegels на MSDN для запуска. См. Также мой собственный вопрос: рекурсивный запрос с одной таблицей в SQL Server 2008

Question

Хорошие обзоры

Вообще говоря, вы принимаете решение между быстрыми временами чтения (например, вложенным набором) или быстрым временем записи (список смежности). Как правило, вы получаете комбинацию из следующих вариантов, которые наилучшим образом соответствуют вашим потребностям. Ниже приводится некоторое углубленное чтение:

Опции

Я знаю и общие особенности:

  1. Список аджанс :
    • Столбцы: ID, ParentID
    • Легко реализуется.
    • Дешевые узлы перемещаются, вставляются и удаляются.
    • Дорого, чтобы найти уровень (может хранить как вычисленный столбец), предки и потомки (Bridge Table в сочетании с столбцом уровня могут решить), путь (Lineage Column может решить).
    • Используйте общие выражения таблиц в тех базах данных, которые поддерживают их для прохождения.
  2. Вложенный набор (также известный как измененный обход дерева предзаказов)
    • Популяно Джо Целько в многочисленных статьях и его книге « Деревья и иерархии» в SQL для Smarties
    • Столбцы: влево, вправо
    • Дешевый уровень, родословная, потомки
    • Неустойчивое кодирование - перемещает, вставляет, удаляет более дорогие.
    • Требуется определенный порядок сортировки (например, созданный). Поэтому сортировка всех потомков в другом порядке требует дополнительной работы.
  3. Вложенные интервалы
    • Как вложенный набор, но с real / float / decimal, чтобы кодировка не была изменчивой (недорогой move / insert / delete)
    • Необходимо иметь дело с проблемами реального / плавающего / десятичного представления
    • Более сложный вариант матричного кодирования добавляет преимущества кодирования предков, как материализованный путь для «свободного»
  4. Bridge Table (aka Closure Table : некоторые хорошие идеи о том, как использовать триггеры для поддержки этого подхода)
    • Столбцы: предки, потомок
    • Он находится отдельно от таблицы, которую он описывает.
    • Может включать некоторые узлы в несколько иерархии.
    • Дешевая родословная и потомки (хотя и не в каком порядке)
    • Для полного знания иерархии необходимо объединить с другим вариантом.
  5. Плоский стол
    • Модификация списка смежности, который добавляет столбец уровня и ранга (например, упорядочение) к каждой записи.
    • Дорогой ход и удаление
    • Дешевая родословная и потомки
    • Хорошее использование: обсуждение темы - форумы / комментарии в блоге
  6. Столбец Lineage (также называемый Materialized Path , Path Enumeration)
    • Колонка: lineage (например, / parent / child / grandchild / etc ...)
    • Ограничьте глубину иерархии.
    • Потомки дешевы (например, LEFT(lineage, #) = '/enumerated/path' )
    • Происхождение сложно (запросы по конкретным базам данных)
  7. Несколько столбцов линии
    • Столбцы: по одному для каждого уровня линии, относятся ко всем родителям до корня, уровни вниз от уровня элемента равны NULL
    • Ограничьте, насколько глубока иерархия
    • Дешевые предки, потомки, уровень
    • Дешевая вставка, удаление, перемещение листьев
    • Дорогое вставка, удаление, перемещение внутренних узлов

Специфические примечания к базе данных

MySQL

оракул

  • Используйте CONNECT BY для перемещения списков Adjacency

PostgreSQL

SQL Server

  • Общее резюме
  • 2008 предлагает тип данных HierarchyId , который помогает с помощью подхода Lineage Column и расширяет глубину, которая может быть представлена.



Это действительно квадратный вопрос, круглый вопрос.

Если реляционные базы данных и SQL - единственный молот, который у вас есть или который готов, то ответы, которые были опубликованы до сих пор, являются адекватными. Однако почему бы не использовать инструмент, предназначенный для обработки иерархических данных? Графическая база данных идеально подходит для сложных иерархических данных.

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

Рассмотрите Билль материалов как общую иерархическую структуру данных.

class Component extends Vertex {
    long assetId;
    long partNumber;
    long material;
    long amount;
};

class PartOf extends Edge {
};

class AdjacentTo extends Edge {
};

Самый короткий путь между двумя подсборками : простой алгоритм обхода графика. Допустимые пути могут быть квалифицированы на основе критериев.

Сходство : Какова степень сходства между двумя сборками? Выполните обход на обоих поддеревах, вычисляя пересечение и объединение двух поддеревьев. Процент подобный - это пересечение, разделенное союзом.

Transitive Closure : Пройдите подэлемент и суммируйте интересующее поле (например): «Сколько алюминия в сборе?»

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




Модель Adjacency Model + Вложенные модели

Я пошел на это, потому что я мог легко вставлять новые элементы в дерево (вам просто нужен идентификатор филиала, чтобы вставить в него новый элемент), а также запросить его довольно быстро.

+-------------+----------------------+--------+-----+-----+
| category_id | name                 | parent | lft | rgt |
+-------------+----------------------+--------+-----+-----+
|           1 | ELECTRONICS          |   NULL |   1 |  20 |
|           2 | TELEVISIONS          |      1 |   2 |   9 |
|           3 | TUBE                 |      2 |   3 |   4 |
|           4 | LCD                  |      2 |   5 |   6 |
|           5 | PLASMA               |      2 |   7 |   8 |
|           6 | PORTABLE ELECTRONICS |      1 |  10 |  19 |
|           7 | MP3 PLAYERS          |      6 |  11 |  14 |
|           8 | FLASH                |      7 |  12 |  13 |
|           9 | CD PLAYERS           |      6 |  15 |  16 |
|          10 | 2 WAY RADIOS         |      6 |  17 |  18 |
+-------------+----------------------+--------+-----+-----+
  • Каждый раз, когда вам нужны все дети любого родителя, вы просто запрашиваете parent столбец.
  • Если вам нужны все потомки любого родителя, вы запрашиваете элементы, у которых их lft между rgt и rgt родителя.
  • Если вам нужны все родители любого узла до корня дерева, вы запрашиваете для элементов, имеющих на lft меньше, чем rgt узла и rgt больше, чем rgt узла, и rgt их по parent .

Мне нужно было делать доступ и запрашивать дерево быстрее, чем вставки, поэтому я выбрал это

Единственная проблема - исправить left и right столбцы при вставке новых элементов. я создал для него хранимую процедуру и вызвал ее каждый раз, когда я вставил новый элемент, который был редок в моем случае, но он очень быстро. Я получил идею из книги Джо Селко, а хранимая процедура и то, как я ее придумал, объясняется здесь в DBA SE https://dba.stackexchange.com/q/89051/41481




Related