Иерархические базы данных
В основе построения БД лежит иерархическая модель данных, в которой имеется один и остальные - подчиненные - объекты, находящиеся на разных уровнях иерархии.
Модель БД представляется связным графом типа дерева, вершины которого расположены на разных иерархических уровнях. При этом одна из вершин на самом высоком уровне, называемая корнем (главным объектом) не подчиняется ни одной вершине, а все остальные вершины (подчиненные объекты) связаны с одной и только одной вершиной, расположенной на более высоком уровне.
Уровень вершины — это расстояние от нее до корня, уровень которого — нуль. Вершины, подчиненные другой вершине, т.е. имеющие предка, называют потомками. В дереве любой потомок может иметь не более одного предка, а любой предок — множество потомков. Любая из вершин может иметь множество подчиненных ей вершин, находящихся на более низком уровне. Дерево имеет n вершин и n – 1 дуг, не имеет циклов, каждая пара вершин соединена одной и только одной простой дугой.
Иерархическую модель можно применять как при рассмотрении логической структуры БД, так и физической. Вершины дерева логической структуры соответствуют типам логических записей, а физической структуры — экземплярам записей. В последнем случае имеем множество деревьев значений (или лес), составляющих содержимое БД. Множество корневых вершин удобно связать с фиктивной корневой вершиной, которая для них будет являться отцом, и в этом случае множество деревьев значений будет представлено одним деревом. Различные вершины дерева значений могут иметь одинаковые значения.
Дуга дерева соответствует типу связи, называемому «исходный—порожденный», и не помечается, так как между двумя типами записей может быть не более одной такой связи. Дуги направлены от исходных записей к порожденным.
В качестве примера на рис. 2.4. приведена иерархическая модель БД ФАКУЛЬТЕТ, включающая пять объектов:
КАФЕДРА (Наименование кафедры, Количество преподавателей, Количество студентов);
ПРЕПОДАВАТЕЛЬ (Табельный номер, Фамилия, Имя, Отчество, Должность);
ГРУППА (Номер группы, Количество студентов, Староста);
РАСПИСАНИЕ (Наименование предмета, Фамилия преподавателя, День недели, Время, Аудитория);
СТУДЕНТ (Номер зачетной книжки, Фамилия, Имя, Отчество, Курс).
Операции манипулирования данными в иерархических системах ориентированы, прежде всего, на поиск информации «сверху вниз», т.е. по заданному экземпляру вершины-отца можно найти все экземпляры вершин-сыновей. Обратный же поиск (найти экземпляр отца по заданному экземпляру сына) затруднен.
Указанная особенность приводит к тому, что симметричные запросы реализуются по-разному и имеют различное время выполнения. Например, в схеме БД (см. рис. 2.4) запрос «Какие преподаватели проводят занятия с определенной группой?» реализуется проще и быстрее, чем запрос «С какими группами ведет занятия определенный преподаватель?».
Иерархической модели присущи и другие недостатки, например дублирование данных на логическом уровне. Так, если один преподаватель проводит занятие одновременно с несколькими группами, то соответствующий экземпляр РАСПИСАНИЕ должен повторяться несколько раз.
Наиболее известной и распространенной СУБД подобного типа является Information Management System (IMS) фирмы IBM. Первая версия появилась в 1968 г. До сих пор поддерживается много баз данных этой системы.