Иерархическая древовидная структура

Иерархическая древовидная структура строится из узлов и ветвей. Узел представляет собой совокупность атрибутов данных, описываю­щих некоторый объект. Наивысший узел в иерархической древовидной структуре называется корнем (например, руководитель предприятия). Зависимые узлы располагаются на более низких уровнях дерева. Уровень, на котором находится данный узел, определяется расстоянием от кор­невого узла (рис. 4.5). (Иерархическое дерево представляет собой пере­вернутое обычное дерево: корень находится наверху, а ветви растут вниз.)

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

 

 

 

Рис. 4.5. Узлы и ветви образуют иерархическую древовидную структуру. Узел является совокупностью атрибутов, описывающих объект. Наивысший в иерархии узел называется корневым (это главный тип объекта). Корневой узел находится на первом уровне. Зави­симые узлы (подчиненные типы объектов) находятся на втором, третьем и т. д. уровнях

узлы, находящиеся на уровне 2, называются порожденными узла на уровне 1, Узел на уровне 1 называется исходным для узлов на уровне 2. Узлы, находящиеся на уровне 3, считаются порожденными узла уров­ня 2, который для них является исходным, и т. д.

Иерархическая древовидная структура всегда удовлетворяет следую­щим условиям:

1. Иерархия неизменно начинается с корневого узла.

2. Каждый узел состоит из одного или нескольких атрибутов, которые
описывают объект в данном узле.

3. На низших уровнях могут находиться зависимые узлы. Узел, находящийся на предшествующем уровне, является исходным для новых зависимых узлов. Зависимые узлы могут добавляться как в вертикальном, так и в горизонтальном направлении без всяких ограничений

(Исключение. На первом уровне может находиться только один узел, называемый корневым.)

4. Каждый узел, находящийся на уровне 2, соединен с одним и только одним узлом на уровне 1. Каждый узел, находящийся на уровне 3, соединен с одним и только одним узлом, находящимся на уровне 2, и т. д. Поскольку между двумя узлами может существовать лишь одна дуга (соединение), дуги не нуждаются в метках.

5. Исходный узел может иметь в качестве зависимых один или несколько порожденных узлов. Если узел не имеет ни одного зависимого
узла, он не является исходным.

6. Доступ к каждому узлу, за исключением корневого, происходит через исходный узел. Выборка каждого ^зла, представленного в иерархии, осуществляется через его исходный узел, поскольку это в действительности отражает семантику данных. В связи с этим в иерархической модели данных пути доступа к каждому узлу являются уникальными
(рис. 4.6). (Например, доступ к узлу I может осуществляться только по пути A-G-H-I, а доступ к узлу D — только по пути A-B-D.) Поэтому иерархическая модель данных обеспечивает только линейные пути доступа.

 

 

Рис. 4.6. В иерархической модели данных путь доступа к каждому узлу уникален. На­пример, доступ к узлу I может осуществляться только по пути A-G-H-I, а доступ к узлу D — только по пути A-B-D. Таким образом, иерархическая модель обеспечивает лишь ли­нейные пути доступа

7. Возможно существование любого числа экземпляров узлов каж­дого уровня. Каждый экземпляр узла (за исключением корневого) соеди­нен с экземпляром исходного узла, т. е. может существовать много экземпляров узла А. Каждый экземпляр узла А начинает логическую запись. Для каждого экземпляра узла А может существовать нуль, один или несколько экземпляров узла В и т. д.

Рассмотрим в качестве примера информацию, содержащуюся в от­ношениях ПАЦИЕНТ, ХИРУРГ, ПАЦИЕНТ-И-ХИРУРГ и ПРЕПАРАТ, показанных на рис. 4.3а—г. Информация в иерархической модели дан­ных может быть представлена различными способами. Один из вариантов показан на рис. 4.7. Корневой узел представляет объект ПАЦИЕНТ.

Для каждого пациента имеется экземпляр корневого сегмента. В рас­сматриваемый момент в базе данных содержатся записи для пациентов Джона Уайта (1111), Мэри Джонс (1234), Чарльза Брауна (2345), Хола Кейна (4876), Пола Кошера (5123) и Энн Худ (6845). Экземпляр записи базы данных для Джона Уайта (1111) показан на рис. 4.8. Тип узла второго уровня, приведенный на рис. 4.7, на рис. 4.8 имеет два экземпляра. Иерархическая модель позволяет для каждого пациента представить сведения о нескольких операциях и нескольких хирургах (см. рисунок).