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

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

Основные понятия.Иерархическая модель БД представляется связным графом типа дерева, вершины которого расположены на разных иерархических уровнях. При этом одна из вершин на самом высоком уровне, называемая корнем, не подчиняется ни одной вершине, а все остальные вершины связаны с одной и только одной вершиной, расположенной на более высоком уровне.

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

Можно дать следующее рекурсивное определение дерева: конечное множество G, состоящее из одной или более вершин, таких, что: одна из вершин является корнем; остальные вершины (кроме корня) содержатся в m≥0 попарно непересекающихся множествах G₁, ...,G_m, каждое из которых, в свою очередь, является деревом. Деревья G₁,...,G_m называются поддеревьями корня.

Иерархическую модель можно применять как при рассмотрении логической структуры (схемы, подсхемы), так и физической. Вершины дерева логической структуры соответствуют типам логических записей, а физической структуры — экземплярам записей. В последнем случае имеем множество деревьев значений (или лес), составляющих содержимое БД. Множество корневых вершин удобно связать с фиктивной корневой вершиной, которая для них будет являться отцом, и в этом случае множество деревьев значений будет представлено одним деревом. Заметим, что различные вершины дерева значений могут иметь одинаковые значения.

Дуга дерева соответствует типу связи, называемому «исходный—порожденный», и не помечается, так как между двумя типами записей может быть не более одной такой связи. Дуги направлены от исходных записей к порожденным.

Различные СУБД иерархического типа по-разному строят дерево для своей модели БД.

Рассмотрим пример иерархической модели БД. Подобная модель включает пять объектов: КОМПАНИЯ (название компании, количество менеджеров, количество служащих); МЕНЕДЖЕР (табельный номер, фамилия, должность); ОТДЕЛ (номер отдела, количество служащих); ПРОЕКТ (планируемые задания, фамилия менеджера, время на выполнение задания);. СЛУЖАЩИЙ (табельный номер, фамилия, должность). Дерево для этой модели приведено на рис. 2.1.

Рис. 2.1. Иерархическая модель БД БИЗНЕС

Операции манипулирования данными в иерархических системах ориентированы прежде всего на поиск информации «сверху вниз», т.е. по заданному экземпляру записи-отца можно найти все экземпляры записей-сыновей. Обратный же поиск (найти экземпляр отца по заданному экземпляру сына) затруднен, а часто и невозможен.

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

Названные недостатки связаны прежде всего с неудовлетворительной реализацией связи типа М:N в иерархических моделях. Применение других моделей БД позволяет избежать приведенные выше трудности.

Сетевая модель

Сетевая модель была разработана рабочей группой по БД КОДАСИЛ. Целью работы группы было создание иерархической модели, позволяющей описывать связи типа М: N, и уменьшение недостатков этой модели. Более того, было введено понятие «подсхема БД», позво­ляющее решать задачи защиты, целостности, разделения данных.

Основные понятия. В сетевой модели данные представляются с помощью записей и связей. Запись в сетевой модели в отличие от иерархической может иметь множество как подчиненных ей записей, так и записей, которым она подчинена. Сеть позволяет непосредственно моделировать отношение типа M:N (рис. 2.2). Так, на рисунке экземпляры записи МЕНЕДЖЕР связываются с экземплярами записи ОТДЕЛ с помощью записе й пересечения (ПРОЕКТ), указывающих наименование проекта, фамилию менеджера, время на выполнение проектов. Данные пересечения соединены адресными ссылками в цепочки, соответствующие экземплярам записей МЕНЕДЖЕР и ОТДЕЛ. Аналогично связываются экземпляры записей МЕНЕДЖЕР и СЛУЖАЩИЙ посредством экземпляров записи ЗАДАНИЕ. Атрибутами записи ЗАДАНИЕ могут быть: наименование задания (повышение уровня продаж продукта, изготовление нового продукта, изменение внешнего вида продукта и т.п.); количество часов, выделяемых менеджеру на выполнение задания.

Рис. 2.2. Сетевая модель БД БИЗНЕС

В сетевой модели БД (ПОСТАВЩИК, ИЗДЕЛИЕ) (рис. 2.3, а) поставщики связаны с продуктами (изделиями). Экземпляры связующей записи (данные пересечения) содержат количество поставляемых изделий и адресные ссылки. В сетевой модели БД (ИЗДЕЛИЕ, УЗЕЛ, ДЕТАЛЬ) (рис. 2.3,б) связующие записи содержат количества: узлов в изделии, деталей в узле, деталей в изделии.

Рис.2.3. Сетевая модель БД а)-(ПОСТАВЩИК,ИЗДЕЛИЕ); б)-(ИЗДЕЛИЕ,УЗЕЛ,ДЕТАЛЬ)

Преобразование сетей в деревья. Сетевую структуру можно преобразовать в одно или несколько деревьев, вводя дополнительные вершины (записи). При этом если основой сети является отношение не типа М:N, то не нужно вводить новые уровни дерева (рис. 2.5). Рассмотрим сеть, включающую записи МЕНЕДЖЕР и ОТДЕЛ, связанные отношением типа М:N. Эту сеть можно преобразовать в два дерева, записи которых связаны отношениями типа 1:N и 1:М (рис. 2.9).

Сетевые модели могут содержать циклы, когда предшествующая вершина является в то же время последующей. Связь записей одного типа называют петлей (рис. 2.4).

Рис. 2.4. Сетевая модель БД

(УЗЕЛ, ДЕТАЛЬ) с циклом и петлей

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

Модель БД, определенная при использовании сетевой модели, представляет собой граф с вершинами двух типов. Этим двум типам вершин соответствуют основные и зависимые записи. На физическом уровне говорят об основных и зависимых файлах. Связи могут устанавливаться только между основными и зависимыми записями, причем зависимая запись не может существовать самостоятельно, без связей с основными файлами.

Сетевая СУБД поддерживает связь типа → в направлении от основной к зависимой записи.

M:N 1:N 1:M

Рис.2.5. Преобразование сети с отношением типа M:N в деревья с отношениями типа 1:N и 1:M

Рассмотрим одну из первых моделей БД, которая практически был реализована в сетевой СУБД ВМР в середине шестидесятых годов прошлого столетия в США. Впоследствии аналогичная сетевая СУБД ВМР была разработана в Германии и позднее сетевая СУБД СЕТОР в Советском Союзе.

Указанная сетевая модель включала четыре файла: два основных файла – ПРЕДМЕТЫ и РАБОЧИЕ МЕСТА и два файла связей – СПЕЦИФИКАЦИЙ и ТЕХНОЛОГИЧЕСКИЕ МАРШРУТЫ (рис. 2.6).

Рис. 2.6. Сетевая модель БД

Представленная сетевая модель БД адекватно отображает схему производственного процесса на предприятии, например, на машиностроительном или другом, на котором производятся или используются некоторые изделия.

Файл ПРЕДМЕТЫ включает записи о произведенных или используемых на предприятии продуктах, изделиях, комплектующих узлах или деталях, материалах и пр.

Файл СПЕЦИФИКЦИИ включает записи конструкторских спецификаций, указывающих, что некоторая деталь, узел или изделие, указанные в файле ПРЕДМЕТЫ, входит (т.е. используется для производства) в другой узел, изделие, которое содержится в файле ПРЕДМЕТЫ, в таком-то количестве.

Файл ТЕХНОЛОГИЧЕСКИЕ МАРШРУТЫ включает технологические процессы производства деталей, узлов, изделий и пр., указанных в файле ПРЕДМЕТЫ. Технологический маршрут – это перечень операций от заготовительных до финишных операций производства предметов с указанием их характеристик.

Файл РАБОЧИЕ МЕСТА включает записи, содержащие характеристики рабочих мест, оборудования, станков и пр.

Перечислим основные операции поиска данных, выполняемые с помощью предложенной сетевой модели:

· Используя два файла ПРЕДМЕТЫ и СПЕЦИФИКАЦИИ, можно решить так называемую задачу «разузлования», т.е. получить перечень всех деталей и узлов с указанием их количества для некоторого узла или изделия, указанного в файле ПРЕДМЕТЫ.

· Используя три файла ПРЕДМЕТЫ, СПЕЦИФИКАЦИЯ и ТЕХНОЛОГИЧЕСКИЕ МАРШРУТЫ можно получить, например, общее время производства некоторого изделия, указанного в файле ПРЕДМЕТЫ.

Рассмотрим подробнее указанные выше преимущества БД на примере этой сетевой модели.

Модель ВМР появилась из практики разработки и применения информационных систем управления предприятиями. Информация в четырех файлах является условно-постоянной и она обязательна для любой информационной системы управления предприятия. Только предлагаемая сетевая модель отличается от других программных реализаций:

1) установлением ссылок между записями различных файлов;

2) наличием языка макрокоманд, позволяющего осуществлять поиск информации, актуализацию и пр.;

3) наличием типового программного обеспечения, позволяющего производить настройку сетевой модели на различные объекты управления и тем самым существенно уменьшить трудовые затраты на разработку информационной системы.

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