Автор работы: Пользователь скрыл имя, 18 Февраля 2011 в 21:20, контрольная работа
Структуры данных в моделях. Особенности и сравнение моделей
Иерархическая модель.
Исторически иерархическая модель появилась раньше сетевой. Она наиболее проста из всех моделей данных. Самой известной иерархической системой позволяющей создавать иерархические базы данных является система IMS (Information Management System) фирмы IBM, используемая в свое время для поддержки лунного проекта «Аполлон». Появление иерархической модели связано с тем, что в реальном мире очень многие связи соответствуют иерархии, когда один объект выступает как родительский, а с ним может быть связано множество подчиненных объектов.
Основными информационными единицами в иерархической модели являются: база данных (БД), сегмент и поле. Поле данных определяется как минимальная, неделимая единица данных, доступная пользователю с помощью СУБД. Выделяют также тип поля, представляющий собой совокупность полей одного типа. Сегмент состоит из конкретных экземпляров полей. Тип сегмента - совокупность входящих в него типов полей. Иерархическая модель представляет собой неориентированный граф, в вершинах которого располагаются сегменты (или типы сегмента). Особенностью такой модели является то, что каждый сегмент может иметь не более одного предка, произвольное количество потомков и, по крайней мере, одно поле. Сегмент, который не имеет потомков, называют листовым сегментом. Иерархическое дерево начинается с одного сегмента, называемого корневым сегментом. Очень важно, что каждый сегмент должен иметь свое уникальное имя или идентификатор.
На рисунке 1.1 схематически представлена иерархическая структура. Узлы (сегменты) соединены друг с другом связующими дугами. Сегмент A является корневым сегментом. Сегменты B, E, H, J, I являются листовыми сегментами. Каждый сегмент, при этом, может содержать произвольное количество полей.
Для иерархической модели данных выделяют два языковых средства:
Описание базы данных предполагает описание всех ее сегментов и установление связей между ними.
Рис.1.1. Иерархическая структура
Пример иерархической структуры. Иерархическая модель довольно удобна для представления предметных областей, так как иерархические отношения довольно часто встречаются между сущностями реального мира. Но иерархическая модель не поддерживает отношения «многие ко многим», когда множество объектов одного типа связаны с множеством объектов другого типа. Предположим, что требуется построить модель отношения между множеством собственников жилья и множеством квартир. Если основной вопрос будет заключаться в определении того, каким жильем владеет тот или иной собственник, то естественно взять в качестве родительских узлов данные о собственнике. При этом каждый сегмент - собственник будет связан с N узлами – квартирами. Таким образом, по собственнику мы легко найдем все квартиры, которые находятся в его собственности. Однако проблема заключается в том, что у одной и той же квартиры может быть несколько собственников. Т.е. одна и та же квартира может встречаться в разных деревьях. В результате решения таких задач, как получение списка всех квартир, или получения всех собственников конкретной квартиры, будут уже не столь очевидными. Кроме того, сложной выглядит даже операция удаления из базы конкретной квартиры, поскольку для этого придется просматривать все деревья. Можно, конечно, построить параллельно деревья, в которых родительскими сегментами будут данные о квартирах, а порождаемыми сегментами – данные о владельцах, но в результате мы получим еще избыточность данных, что породит дополнительную проблему их согласованности.
Основной единицей обработки в иерархической модели является сегмент. К сегментам могут применяться такие операции как запомнить, модифицировать, удалить, извлечь, найти. Операция поиска сводится к одной из возможных процедур обхода дерева. Иерархические СУБД поддерживают, обычно, правило: никакой сегмент не может существовать без своего родителя (исключая корневой сегмент). Подобные правила, поддерживаемые СУБД, называют ограничениями целостности.