 |
|
|
 |
|
2001 г
Моделирование иерархических объектовВиноградов С. А. ВведениеМногим структурам и объектам свойственна иерархичность. За примера Из-за внешнего сходства, иерархические модели часто называют деревьями, вершину иерархии - корнем дерева, самые низшие ответвления - листьями. По аналогии с поколениями человеческого рода, непосредственно более высокий уровень иерархии называют родителем, а все уровни, под которыми находиться текущий элемент, - его предками. Все элементы, находящиеся непосредственно под текущим называют его детьми, а вообще все, находящиеся под ним - потомками. Иерархические структуры довольно часто приходиться моделировать в базах данных, при этом возникают некоторые, характерные только для иерархии, вопросы. Например, как узнать количество всех потомков у данного элемента, или, на каком уровне он находится, или, допустим, требуется получить список всех потомков заданного элемента, у которых нет детей. Попробуем получить ответы на эти и другие вопросы. Простейшая иерархияВ качестве примера, возьмем часть схемы подразделений на предприятии:
где А1 - подразделение верхнего уровня (возможно Можно легко создать таблицу, которая содержит информацию об этих подразделениях (здесь идалее - синтаксис MS SQL): create table Departments ( Id int not null identity primary key, Parent int not null references Departments(Id), Name varchar(32) not null ) Поле Parent является ссылкой на Id (первичный ключ) вышестоящего уровня в иерархии. В данном случае оно указывает, в какое подразделение входит каждый отдел.
Характерные вопросыПользуясь такой таблицей, легко можно найти родителя или детей у определенного элемента. Но обычно с иерархическими объектами возникают более сложные задачи. Вероятно, мы захотим узнать, является ли данный элемент терминальным, то есть, отсутствуют ли другие элементы, входящие в него. Это нужно, например, для того, чтобы отличать такие элементы от нетерминальных при выводе иерархического справочника пользователю. Также может потребоваться узнать, на каком уровне иерархии находится заданный элемент. Может оказаться необходимым получить всех предков данного элемента, начиная сверху или снизу. Часто бывает нужно получить всех потомков какого-нибудь элемента, при этом с разными условиями: например, только терминальных, или, находящихся только на определенном уровне и т. д. Из приведенной выше схемы совсем не очевидны ответы на все эти вопросы. Конечно, если сервер базы данных специально поддерживает иерархию или допускает рекурсию в запросах, то большинство ответов можно получить одним запросом. В противном случае получение результатов будет крайне неэффективным. Как же организовать хранение иерархических объектов, чтобы легко и быстро получать ответы на перечисленные вопросы? Обход дереваОдно из решений было предложено Joe Celko (см. [1]). Он рекомендовал добавить в таблицу два дополнительных целочисленных поля: Left и Right, в которые заносятся результаты обхода дерева, начиная с корня. Обход организуется следующим образом: каждый раз, при прохождении какого-нибудь элемента указателем, счетчик увеличивается на единицу; при попадании в терминальный элемент, указатель возвращается в родителя и ищет следующего ребенка. В поле Left записывается значение create table Departments ( Id int not null identity primary key, Parent int not null references Departments(Id), Name varchar(32) not null, Left int not null, Right int not null )
Комбинируя эти поля и сравнивая их с такими же полями других элементов, такая схема позволяет получить ответы на все поставленные вопросы. Терминальные элементы заметно сразу - у них Left = Right. Отношения предок Информацию об уровне заданного элемента можно узнать, получив количество его предков. Количество Главный недостаток этого решения в том, что при изменении в структуре дерева, приходится заново пересчитывать значения полей Left и Right во всей таблице. То есть, такой способ годится только для небольших, редко изменяемых таблиц. Вспомогательная таблицаБолее эффективный и удобный способ create table DepartmentsAncestors ( Department int not null references Departments(Id), Ancestor int not null references Departments(Id) constraint DepartmentAncestor primary key (Department, Ancestor) ) Поле Ancestor ссылается на Id предка каждого элемента. В данном случае оно позволяет узнать все подразделения, в которые входит данный отдел.
Подобная схема легко позволяет получить любую информацию об иерархических элементах одним запросом. Очевидным образом, исходя из самой структуры вспомогательной таблицы, можно получить всех предков, либо потомков определенного элемента. Информацию об уровне заданного элемента можно узнать, получив количество его предков. Терминальность элемента можно узнать, пользуясь только основной таблицей - достаточно проверить, есть ли элементы, Parent которых равен Id текущего. Модификация Если запросы с использование информации об уровне и признаке терминальности встречаются часто, и требования к времени их выполнения высоки, то желательно создать соответствующие поля в основной таблице и поддерживать в них актуальные значения. Например: create table Departments ( Id int not null identity primary key, Parent int not null references Departments(Id), Name varchar(32) not null, Level int not null, Terminal bit not null defaul(1) )
Пользуясь двумя такими таблицами, можно легко строить практически любые запросы, характерные для иерархических объектов. Используемые источники [1] Joe Celko "A Look at SQL Trees",
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Примера Дивизион (исп.Primera Divisin) профессиональной футбольной лиги Испании (исп.Liga de Ftbol Profesional, LFP), известный также как Примера и Ла Лига (исп.La Liga), является профессиональным футбольным турниром клубов высшего уровня в системе футбольных лиг Испании. Ла Лига считается одной из лучших футбольных лиг в мире.