|
|
|||||||||||||||||||||||||||||
|
Моделирование иерархических объектовВведение Многим структурам и объектам свойственна иерархичность. За примерами далеко ходить не надо. Почти все объекты состоят из частей, которые, в свою очередь, могут состоять из более мелких деталей. Общественные структуры, как правило, отражают жесткую иерархическую модель подчинения, сходящуюся к одному подразделению или человеку. Из-за внешнего сходства, иерархические модели часто называют деревьями, вершину иерархии - корнем дерева, самые низшие ответвления - листьями. По аналогии с поколениями человеческого рода, непосредственно более высокий уровень иерархии называют родителем, а все уровни, под которыми находиться текущий элемент, - его предками. Все элементы, находящиеся непосредственно под текущим называют его детьми, а вообще все, находящиеся под ним - потомками. Попробуем получить ответы на эти и другие вопросы. Простейшая иерархия
где А1 - подразделение верхнего уровня (возможно, не единственное на этом уровне), В1 и В2 - входят в А1, С1 - входит в В1, С2 и С3 - входят в В2. Можно легко создать таблицу, которая содержит информацию об этих подразделениях (здесь идалее - синтаксис MS SQL): Поле Parent является ссылкой на Id (первичный ключ) вышестоящего уровня в иерархии. В данном случае оно указывает, в какое подразделение входит каждый отдел.
Характерные вопросы Пользуясь такой таблицей, легко можно найти родителя или детей у определенного элемента. Но обычно с иерархическими объектами возникают более сложные задачи. Вероятно, мы захотим узнать, является ли данный элемент терминальным, то есть, отсутствуют ли другие элементы, входящие в него. Это нужно, например, для того, чтобы отличать такие элементы от нетерминальных при выводе иерархического справочника пользователю. Также может потребоваться узнать, на каком уровне иерархии находится заданный элемент. Может оказаться необходимым получить всех предков данного элемента, начиная сверху или снизу. Часто бывает нужно получить всех потомков какого-нибудь элемента, при этом с разными условиями: например, только терминальных, или, находящихся только на определенном уровне и т. д. Из приведенной выше схемы совсем не очевидны ответы на все эти вопросы. Конечно, если сервер базы данных специально поддерживает иерархию или допускает рекурсию в запросах, то большинство ответов можно получить одним запросом. В противном случае получение результатов будет крайне неэффективным. Как же организовать хранение иерархических объектов, чтобы легко и быстро получать ответы на перечисленные вопросы? Одно из решений было предложено Joe Celko (см. [1]). Он рекомендовал добавить в таблицу два дополнительных целочисленных поля: Left и Right, в которые заносятся результаты обхода дерева, начиная с корня. Обход организуется следующим образом: каждый раз, при прохождении какого-нибудь элемента указателем, счетчик увеличивается на единицу; при попадании в терминальный элемент, указатель возвращается в родителя и ищет следующего ребенка. В поле Left записывается значение счетчика при первом прохождении элемента, а в поле Right - при последнем. При таком варианте, наша таблица подразделений выглядела бы следующим образом: Departments
Комбинируя эти поля и сравнивая их с такими же полями других элементов, такая схема позволяет получить ответы на все поставленные вопросы. Терминальные элементы заметно сразу - у них Left = Right. Вспомогательная таблица Более эффективный и удобный способ состоит в том, чтобы, в дополнение к первоначальной таблице, создать вспомогательную таблицу, содержащую всего два поля. В одном из них следует хранить Id элемента, а в другом - Id всех его предков. Поле Ancestor ссылается на Id предка каждого элемента. В данном случае оно позволяет узнать все подразделения, в которые входит данный отдел. DepartmentsAncestors
Подобная схема легко позволяет получить любую информацию об иерархических элементах одним запросом. Очевидным образом, исходя из самой структуры вспомогательной таблицы, можно получить всех предков, либо потомков определенного элемента. Информацию об уровне заданного элемента можно узнать, получив количество его предков. Терминальность элемента можно узнать, пользуясь только основной таблицей - достаточно проверить, есть ли элементы, Parent которых равен Id текущего. Модификация вспомогательной таблицы, при изменении основной, производится довольно просто. Заботу о ней можно предоставить либо триггерам, либо приложению. Если запросы с использование информации об уровне и признаке терминальности встречаются часто, и требования к времени их выполнения высоки, то желательно создать соответствующие поля в основной таблице и поддерживать в них актуальные значения. Например: create table Departments Departments
Пользуясь двумя такими таблицами, можно легко строить практически любые запросы, характерные для иерархических объектов. Ссылки по теме
|
|