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

Представляет собой совокупность связан­ных элементов, образующих иерархическую структуру — перевернутый граф (дерево). К основным понятиям иерархической модели данных относятся уровень, элемент (или узел) и связь. Узлом называют совокупность атрибутов данных, описывающих некоторый объект. Каждый узел связан с одним узлом более высокого уровня и с любым количеством (в том числе и с нулем) узлов нижнего уровня. Исключением является узел самого высокого уровня, который не связан ни с одним узлом более высокого уровня. Этот узел называется корнем дерева. Подчинённые узлы располагаются на втором, третьем и т.д. уровнях. Количество деревьев в базе данных определяется количеством корней деревь­ев. К каждой записи базы данных существует единственный путь от корневой записи. Примером иерархической модели данных может служить адрес. Действительно, на первом уровне (в корне дерева) лежит страна, на втором — регион, на третьем - город, на четвертом - улица, дом и квартира. Один и тот же город не может принадлежать двум странам или регионам. Другим примером иерархической модели является пространство доменных имен интернета – система DNS.

Рис. 1. Иерархическая модель данных. Структура организации.

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

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

Рис. 2. Сетевая модель данных. Принадлежность сотрудников проектам.

1.6. Инвертированные списки.

Организация доступа к данным на основе инвертированных списков используется и сейчас практически во всех современных реляционных СУБД, но в этих системах пользователи не имеют непосредственного доступа к внутренней структуре инвертированных списков, (см. Главу 11. Физическая организация баз данных) как это было на заре становления технологии баз данных. Более того, пользователь может и не догадываться о наличии такой структуры.

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

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

(значение поля;

значение адреса записи или уникального идентификатора записи)

Список таких пар упорядочен по значению поля.

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

№ амбулаторной карты	1	2	3	4	5	6	7	8	9	10	11	12
Дата лечения	11.10	01.10	10.10	11.10	08.10	30.09	11.10	10.10	11.10	07.10	05.10	07.10
Специализ. врача	Терапевт	Невролог	Кардиолог	Терапевт	Терапевт	Терапевт	Кардиолог	Невролог	Терапевт	Терапевт	Кардиолог	Терапевт

Таблица 1. Данные о лечениях.

Список, инвертированный по дате лечения:

Дата лечения	30.09	01.10	05.10	07.10	08.10	10.10	11.10
№ амбулаторной карты	6	2	11	10,12	5	3,8	1,4,7,9

Таблица 2. Список, инвертированный по дате лечения.

Список, инвертированный по специализации врача:

Специализация врача	Кардиолог	Невролог	Терапевт
№ амбулаторной карты	3, 7, 11	2, 8	1, 4, 5, 6, 9, 10, 12

Таблица 3. Список, инвертированный по специализации врача.

Объединение инвертированных списков по всем вторичным ключам составляет так называемый (полностью) инвертиро­ванный файл. Имея такой файл, легко найти записи с данными значениями атрибутов. Например, в нашем случае специализации врача Кардиолог и одновременно дату лечения 11.10 имеет лишь амбулаторная карта №8. Если инвертированные списки не перекрывают все множество ключей, то говорят о частично инвертированном файле.

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

Иерархическая и сетевая модели данных обладают определенными недостатками, затрудняющими обработку и доступ к дан­ным, основными из которых являются:

1. Высокая логическая сложность работы с данными

2. Зависимость приложений от физической реализации базы данных

3. Наличие только навигационного метода доступа к данным. Это означает, что для осуществления запроса на выборку данных приходится организовывать в программе перебор запись за записью – нельзя выразить запрос в виде высокоуровнего выражения, осуществляющего обработку сразу множества записей.

По этим причинам такие модели данных в настоящее время применяются мало. Что касается инвертированных списков, то это скорее не модель данных, а механизм поиска. И этот механизм не утратил значения в наши дни – на нем основаны так называемые вторичные индексы (см. главу 11).

С течением времени упомянутые способы организации данных уступили своё место новой модели данных, получившей название реляционной.