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

Основные структуры

Тип записи - именованная структура, которая содержит один или больше имено­ванных элементов данных, каждый из которых обладает своим осо­бым форматом. Некоторые элементы данных могут содержать два или больше именованных элементов данных, каждый из которых тоже обладает своим особым форматом.

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

На диаграммах каждый тип записи отображается в виде имени, заключенного в пря­моугольник. Тип записи определяет особую структуру, которая обычно связана с некоторым типом сущности. Отдельные значения типа записи называются экземплярами.

Интраструктурой называется структура, размещенная внутри типа записи.

Тип набора - именованная связь типа "один ко многим" (1:М), установленная между записью-владельцем и одной или несколькими записями-членами.

Тип набора представляет собой конструкцию, которая поддерживает работу с интраструктурами, т.е. со структурами внутри типов записей. Тип набора поддерживает связь 1:М, в которой тип записи на стороне "один" называется типом записи-владельца, а тип записи на стороне "многие" называется типом записи-члена. Используя типы записи и типы набора, проектировщик базы данных может создать диаграм­му структуры данных, или схему данных, используемую для представления структуры CODASYL-совместимой базы данных.

При создании типов наборов необходимо учитывать следующие особенности.

- Все типы наборов должны иметь имя;

- Тип набора может иметь несколько экземпляров;

- Набор может быть пустым, т.е. в нем может находиться только одна за­пись-владелец.

Наборы являются единственным способом представления связей между записями. Связи могут быть следующих типов: "многие ко многим" (M:N), «один к одному» (1:1), «один ко многим» (1:М), системный тип набора.

Системный тип набора - именованная связь между воображаемым типом записи-владельца, который является системой (System), и (обычно) одним типом запи­си-члена.

Существуют два языка описания данных (DDL): один — для схемы и второй для подсхемы (представления).

Иерархическая модель данных рассматривается на примере самой известной СУБД этого типа — Information Management System (IMS) фирмы IBM. Иерархические СУБД используются до сих пор — в основном из-за уровня ин­вестиций, вложенных в уже существующие системы, стоимости работ по их замене, а также по той причине, что они вполне удовлетворительно выполняют свою работу в полном соответствии с требованиями организации, обеспечивая ключевые системные функции. Как и в сетевых СУБД, в иерархических СУБД используются такие структуры и способы их реализации, которые позволяют отнести системы данного типа к классу "навигационных".

Иерархическая модель данных - модель, объединяющая записи, хранимые в общей древовидной структуре с одним корневым типом записи, который имеет нуль или больше подчиненных типов записей. Каждый подчиненный тип записи также может иметь нуль или больше подчиненных типов записей.

Как следует из названия, данные в этой модели структурированы иерархически. Так же, как и в случае сетевых СУБД, сначала появились иерархические СУБД, а уже потом на их основе была разработана иерархическая модель данных.

Иерархическая структура. Основной структурой, поддерживающей иерархическое представление информации, является дерево. Для моделирования информации с помощью древовидной структуры зачастую используется обобщенное дерево. Абстрактное представление данной структуры состоит из узлов, соединенных связями, которые называются дугами или ребрами. Самый верхний узел называется корневым узлом. Он может иметь нуль или несколько дочерних узлов, которые, в свою очередь, также могут иметь нуль или несколько дочерних узлов. В результате подобная структура может быть определена рекурсивно. Все узлы дерева, за исключением корня, должны иметь родительский узел. Любая часть дерева, исходящая из одного узла (помимо корня дерева), называется поддеревом. С практической точки зрения, каждый узел может быть представлен либо в виде некоторого типа записи, где каждая связь является встроенным указателем (или адресом), либо с помощью некоторого физического упорядочения записей.

Узлы представляют интересующие нас объекты, а связи между ними определяются самим расположением узлов и ребер, которые, соединяя узлы, образуют эту древовидную структуру. Объекты могут иметь одинаковый тип.

Иерархическая структура вполне естественным образом поддерживает связи как типа "один ко многим" (1:М), так и типа "один к одному" (1:1).

В обобщенной структуре дерева типы записей обычно упорядочены внутри структуры, причем, как правило, слева направо. Экземпляры записей также обычно упорядочиваются.

При работе с обобщенной древовидной структурой используются два метода доступа ко всем узлам (типам записей) внутри дерева. Один метод начинается с доступа к корню с последующей обработкой всего дерева с доступом к поддеревьям в порядке слева направо. Это так называемый прямой порядок обхода дерева, или нисходящий порядок обхода. Другой метод начинается с доступа к самым нижним узлам с постепенным восходящим переходом от одного поддерева к другому слева направо и с завершением обработки в корне. Этот метод называют обратным порядком обхода дерева или восходящим порядком обхода.

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

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

Основная литература: 1[1028-1058]

Контрольные вопросы:

1. Сетевая модель данных.

2. Иерархическая модель.

Дата добавления: 2014-01-07