Базы данных. Учебное пособие


Основные понятия и определения


Иерархическая  модель  данных  является  частным  случаем  сетевой  модели  данных.  Как  уже  описывалось  в  предыдущей  главе,  сеть  - это  направленный  граф,  который  состоит  из  точек,  соединенных  стрелками.  Точки  - это  типы  записей,  а  стрелки – это  отношение  один-к-одному  или  один – ко-многим.  Стрелка  в  сети  имеет  по  точке  с  каждого  конца.  Точка  в  «хвосте»  стрелки  в  иерархической  модели  называется  предком,  а  точка  на  острие  стрелки  называется  потомком.  Разница  между  сетевой  и  иерархической  моделями  состоит  в  том,  что  в  сетевой  модели  потомок  может  принадлежать  нескольким  предкам,  а  в  иерархической  модели  - только  одному.

Дерево  данных  - это  иерархия  сегментов,  удовлетворяющих  следующим  правилам:

1. Существует  единственный  сегмент  верхнего  уровня,  который  назывантся  корнем.     Корневой  сегмент  не  входит  в  качестве  потомка  ни  в  один  тип  ОПП.

2. За  исключением  корневого  сегмента,  каждый  сегмент  входит  в  качестве  потомка  ровно  в  один  тип  ОПП.

3. Сегмент  может  быть  в  качестве  предка  в  нескольких  типах  ОПП  (например,  СЛУЖАЩИЙ  на  рис.6.1).

4. Сегмент-предок  обладает  произвольным  количеством  потомков,  но  каждый  сегмент-потомок  обладает  только  одним  сегментом-предком.  Это  означает,  что  отношения  между  предком  и  потомком  в  дереве  один-ко-многим.

5. Сегмент,  у  которого  нет  потомка,  называется  листовым  сегментом.

6. Для  любого  типа  сегмента  А  существует  единственный  путь  в  дереве  от  корня  до  А.  Записи  этого  пути  называются  предшественниками. А -   зависимый  сегмент   всех  сегментов  пути,  включая  корень.

7. Сегмент  А  сам  может  быть  корнем  поддерева.

Вхождения  одного  и  того  же  типа  сегмента,  который  имеет  одного  и  того     же  предка,  называются  близнецами. 

В  иерархической  модели  данных  существует  такой  термин,  как  сбалансированное  дерево  -  это  такое дерево,  у  которого  все  пути  от  корневого  сегмента  до  листовых  имеют  одну  и  ту  же  длину.




Начало  Назад  Вперед



Книжный магазин