SQL отлично подходит для многих вещей, но иерархические данные - это одна из самых больших проблем.Некоторые поставщики предоставляют специальные расширения для решения этой проблемы (например, синтаксис Oracle CONNECT или тип данных SQL Server hierarchyid), но мы, вероятно, хотим сохранить этот стандартный SQL 1 .
То, что вы смоделировали, называется "списком смежности" - это очень просто и понятно, и всегда соответствует 2 .Но, как вы выяснили, это отстой для запросов, особенно для неизвестной глубины или поддерева, а не из корневого узла.
Поэтому нам нужно дополнить это дополнительной моделью.Есть в основном 3 другие модели, которые вы должны использовать вместе с моделью списка смежности.
- Вложенные множества
- Материализованный путь
- Закрытие обхода предков
Для более глубокого их изучения мы будем использовать эту диаграмму: 
Для этого обсуждения мы также предполагаем, что это простая иерархия, что естьбез циклов.
Вложенные наборы Джо Селко.
По сути, вы сохраняете значения "Left" и "Right" каждого узла, которые указываютего положение в дереве.Корневой узел всегда будет иметь 1 для «левого» и <count of nodes * 2> для «правого».Это проще проиллюстрировать на диаграмме:
Обратите внимание, что каждому узлу присваивается пара номеров, один для «левого», а другой для"Правильно".С этой информацией вы можете сделать некоторые логические выводы.Поиск всех дочерних элементов становится легким - вы фильтруете значения, в которых «Left» узла больше, чем «Left» целевого узла, а «Right» того же узла меньше, чем «Right» целевого узла.
Самым большим недостатком модели является то, что изменение иерархии почти всегда требует обновления всего дерева, что делает его очень ужасным для поддержки быстро движущихся диаграмм.Если это то, что вы обновляете только один раз в год, это может быть приемлемо.
Другая проблема с этой моделью заключается в том, что, если существует необходимость в нескольких иерархиях, вложенный набор не будет работать без дополнительных столбцов дляотслеживать отдельную иерархию.
Материализованный путь
Вы знаете, как работает путь к файловой системе, верно?Это в основном то же самое, за исключением того, что мы храним это в базе данных 3 .Например, возможная реализация материализованного пути может выглядеть следующим образом:
ID Name Path
1 Alice 1/
2 Bob 1/2/
3 Christina 1/3/
4 Dwayne 1/4/
5 Erin 1/2/5/
6 Frank 1/2/6/
7 Georgia 1/2/7/
8 Harry 1/2/7/8/
9 Isabella 1/3/9/
10 Jake 1/3/10/
11 Kirby 1/3/10/11/
12 Lana 1/3/12/
13 Mike 1/4/13/
14 Norma 1/4/13/14/
15 Opus 1/4/15/
16 Rianna 1/4/16/
Это довольно интуитивно понятно и может выполнять ОК, пока вы пишете свои SQL-запросы для использования предикатов, таких как WHERE Path LIKE '1/4/*'.Двигатели смогут использовать индекс по столбцу пути.Обратите внимание, что если ваши запросы связаны с запросом середины дерева или снизу вверх, это означает, что индекс не может быть использован и производительность пострадает для него.Но программирование по материализованному пути довольно легко понять.Обновление части дерева не будет распространяться на несвязанные узлы как вложенные множества, так что это тоже плюс в его пользу.
Самый большой недостаток - то, что для индексации текст должен быть коротким столбцом.Для базы данных Access, которая устанавливает ограничение в 255 символов в поле вашего путиХуже того, нет хорошего способа предсказать, когда вы собираетесь достичь предела - вы можете достичь его, потому что у вас слишком глубокое дерево или слишком широкое дерево (например, большие числа занимают слишком много места).По этой причине большие деревья могут потребовать какого-то жесткого ограничения, чтобы избежать этой ситуации.
Закрытие обхода предков
В этой модели используется отдельная таблица, которая обновляется при каждом обновлении таблицы сотрудников.Вместо того, чтобы записывать только непосредственные отношения, мы перечисляем все происхождение между двумя узлами.Чтобы проиллюстрировать это, таблица будет выглядеть следующим образом:
Таблица сотрудников:
ID Name
1 Alice
2 Bob
3 Christina
4 Dwayne
5 Erin
6 Frank
7 Georgia
8 Harry
9 Isabella
10 Jake
11 Kirby
12 Lana
13 Mike
14 Norma
15 Opus
16 Rianna
Таблица предков сотрудников:
Origin Ancestor
1 1
2 1
2 2
3 1
3 3
4 1
4 4
5 1
5 2
5 5
6 1
6 2
6 6
7 1
7 2
7 7
8 1
8 2
8 7
8 8
9 1
9 3
9 9
10 1
10 3
10 10
11 1
11 3
11 10
11 11
12 1
12 3
12 12
13 1
13 4
14 1
14 4
14 13
14 14
15 1
15 4
15 15
16 1
16 4
16 16
Как видите, мы генерируем на несколько строк все возможные отношения между двумя узлами.В качестве бонуса, потому что это таблица, мы можем использовать внешний ключ и каскадное удаление, чтобы обеспечить его согласованность.Тем не менее, мы все равно должны вручную управлять вставками и обновлениями.Поскольку таблица также узкая, очень легко создать запрос, который может использовать индекс по ключу, источнику и предку, чтобы найти поддерево, дочерние элементы, родительские элементы.Это самая гибкая система за счет дополнительной сложности в обслуживании.
Поддержание модели
Все 3 обсуждаемые модели в основном немного денормализуют данные, чтобы упростить запрос и поддержать произвольный поиск по глубине.,Следствием этого является то, что нам необходимо вручную управлять изменениями, когда таблица сотрудника каким-либо образом модифицируется.
Самый простой подход - просто написать процедуру VBA, которая будет усекать и перестраивать всюграфик с использованием вашей предпочтительной модели.Это может очень хорошо работать, когда график маленький или не часто меняется.
С другой стороны, вы можете рассмотреть возможность использования Макросы данных в таблице сотрудников для обслуживания, необходимого для распространения обновлений в иерархии.Однако, если вы используете макросы данных, это усложняет перенос данных в другую систему RDBMS, поскольку ни один из этих макросов данных не поддерживает.(Чтобы быть справедливым, проблема все еще существовала бы, если бы вы портировали из хранимых процедур / триггеров SQL Server в хранимые процедуры / триггеры Oracle - они очень погрязли в диалекте вендора, что портирование является проблемой).Использование макросов данных или триггер + хранимая процедура означают, что вы можете положиться на механизм, чтобы поддерживать иерархию для вас без какого-либо программирования в формах.
Распространенным искушением является использование события AfterUpdate формы для сохранения изменений, и это сработает .... если кто-то не обновит его вне формы.По этой причине я бы предпочел, чтобы мы использовали макрос данных, а не полагались на то, что все всегда используют форму.
Обратите внимание, что во всем этом обсуждении мы должны НЕ отказаться от модели списка смежности.Как я уже говорил ранее, это наиболее нормализованный и последовательный способ моделирования иерархии.С его помощью невозможно создать бессмысленную иерархию.Только по этой причине вы должны держать это как свою «авторитетную правду», на которой вы можете затем построить свою модель, чтобы повысить производительность запросов.
Еще одна веская причина продолжать использовать модель списка смежности - независимо от того, какую модель вы используете выше, они вводят либо дополнительные столбцы, либо дополнительные таблицы, которые не предназначены для непосредственного редактирования пользователями, но для целей, в некоторой степени эквивалентныхрассчитанное поле и, следовательно, не должны быть возиться с.Если пользователям разрешено редактировать только поле SupervisorID, тогда становится легко кодировать процедуру макросов / триггеров / VBA данных вокруг этого одного поля и обновлять «вычисления» дополнительных полей / таблиц, чтобы обеспечить корректность длязапросы в зависимости от таких моделей.
1.Стандарт SQL описывает способ создания рекурсивного запроса.Тем не менее, соответствие для этой конкретной функции кажется плохим.Кроме того, производительность может быть не такой хорошей.(что имеет место в конкретной реализации SQL Server). Обсуждаемые 3 модели легко реализуются в большинстве СУБД, и запросы для запроса иерархии могут быть легко написаны и перенесены.Однако реализация для автоматического управления изменениями в иерархии неизменно требует специфичного для поставщика диалекта с использованием триггеров или хранимых процедур, которые не очень переносимы.
2.Когда я говорю «непротиворечивый», я имею в виду только то, что модель не может создать бессмысленный результат.Все еще возможно предоставить неверные данные и создать странную иерархию, такую как руководитель сотрудника, отчитывающийся перед сотрудником, но не такую, которая дала бы неопределенные результаты.Тем не менее, это все еще иерархия (даже если она заканчивается как циклический граф).В других моделях неправильное ведение полученных данных означает, что запросы начнут возвращать неопределенные результаты.
3.Тип данных * SQL Server hierarchyid фактически является реализацией этой модели.