Правила концевого прохождения

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

2-Перечисляются все значения в том веерном отношении, на котором остановился шаг 1.

3. Перечисляются значения всех вееров этого веерного отношения.

4. От достигнутого уровня происходит подъем на предыдущий уровень, и если возможно применить шаг 1, то процесс повторяется.

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

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

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

Рассмотрим алгоритм формирования иерархической БД на основе известного множества атрибутов и функциональных зависимостей. Исходное множество функциональных зависимостей и атрибуты первичного ключа получаются так же, как при формировании множества отношений в ЗНФ. Алгоритм иллюстрируется тем же примером, что и в п. 2.2.2.

Алгоритм получения структуры иерархической БД

1. Для каждой функциональной зависимости вида А —> В создается отношение Si(A,B). Каждый блок взаимно-однозначных соответствий также порождает отношение с ключом, равным старшему по объему понятия атрибуту.

В нашем примере будут созданы следующие отношения (ключи помечены знаком #):

S1(НИИ #, Директор, Адрес),

S2(0тдел #, НИИ, Ксотр),

S3(Тема #, Датанач, Датакон, Приор),

S4(ФИО #, Отдел),

S5(Тема #, Работа #, ФИО #, Прод),

S6(Тема #, Заказ #, Обфин).

2. Разделить отношения на группы по признаку: два отно­шения находятся в общей группе, если их ключи функциональ­но определяют хотя бы один общий атрибут.

Для отношений Sl - S6 получаем две группы:

• Sl, S2, S4, S5 (все ключи функционально определяют атрибут НИИ);

• S3, S6, S5 (все ключи функционально определяют атри­бут ТЕМА).

Далее шаги 3,4,5 выполняются раздельно для каждой группы. Количество групп определяет количество иерархических БД.

3. У всех пар отношений группы проверяется условие для ключей Kj —» Ki. Если оно соблюдается, то из соответствую­щих отношений создается веерное отношение Wij(Si,Sj).

4. Найти в группе цепи веерных отношений и сцепить их в дерево. Элемент цепи образуется по условию Wij - Wjk.

В нашем примере получим:

группа 1: цепь Wl 2(S I,S2), W24(S2,S4), W45(S4,S5) образует дерево;

группа 2: цепей нет, но W35(S3,S5) и W36(S3,S6) образуют дерево.

5. Атрибуты, оставшиеся вне цепей на шаге 4, добавить в структуру тех отношений, где они будут не ключевыми, либо в структуру отношений, соответствующих висячим вершинам дерева.

6. Если группы, полученные на шаге 2, содержат общие отношения, то решить вопрос о целесообразности установления логических связей между иерархическими БД.

7. Сократить список атрибутов в сегментах за счет удаления атрибутов зависимого отношения, общих в паре "основной -зависимый".

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

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

Минимальное множество вариантов выборки соответствует трем операциям.

1. GU - получить уникальную запись по известным значе­ниям первичного ключа на каждом уровне дерева иерархичес­кой базы данных.

2. GN - получить следующую запись на том уровне дере­ва, где находится текущая запись после выполнения операто­ра GU.

3. GNP - получить следующую запись на расположенном непосредственно ниже уровня дерева относительно позиции, где находится текущая запись после выполнения оператора GU или GN.

Например, для запроса - получить информацию о преподавателе с кодом 1103 кафедры 11 факультета 01 - потребуется оператор

GU Факультет (Факультет="01")

Кафедра (Кафедра="11")

Преподаватель (Преподаватель="1103")

print Преподаватель

В этом примере названия отношений совпадают с названиями соответствующих первичных ключей.

Запрос - получить список всех студентов группы 102 - реали­зуется следующей последовательностью операторов

GU Факультет (Факультет="01")

Группа (Группа="102")

Студент Ml: GN Студент print Студент

goto Ml

Поскольку в операторе GU не указано условие выборки в отношении Студент, текущей записью станет первая запись этого отношения, и далее циклическое повторение оператора GN обеспечит требуемое извлечение всех записей о студентах группы 102. Выход из цикла произойдет в результате получения кода возврата "конец отношения".

Сравнение моделей данных

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

Рассматривая преимущества и недостатки известных моделей данных, следует отметить ряд несомненных достоинств реляционного подхода'.

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

• Теоретическое обоснование. Наличие теоретически обоснованных методов нормализации отношений и проверки ацикличности структуры позволяет получать базы данных с заданными характеристиками.

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

Среди недостатков реляционной модели данных необходимо назвать следующие.

• Низкая скорость при выполнении операции соединения.

• Большой расход памяти для представления реляционной БД. Хотя проектирование в ЗНФ рассчитано на минимальную избыточность (каждый факт представляется в БД один раз), другие модели данных обеспечивают меньший расход памяти для представления тех же фактов. Например, длина адреса связи обычно намного меньше, чем длина значения атрибута.

Достоинствами иерархической модели данных являются следующие.

• Простота. Хотя модель использует три информационные конструкции, иерархический принцип соподчиненности понятий является естественным для многих экономических задач (например, организация статистической отчетности).

• Минимальный расход памяти. Для задач, допускающих реализацию с помощью любой из трех моделей данных, иерархическая модель позволяет получить представление с минимально требуемой памятью.

Недостатки иерархической модели.

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

• Допустимость только навигационного принципа доступа к данным.

• Доступ к данным производится только через корневое

отношение.

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

• Универсальность. Выразительные возможности сетевой модели данных являются наиболее обширными в срав­нении с остальными моделями.

• Возможность доступа к данным через значения нескольких отношений (например, через любые основные отношения). В качестве недостатков сетевой модели данных можно назвать.

• Сложность, т.е. обилие понятий, вариантов их взаимосвязей и особенностей реализации.

• Допустимость только навигационного принципа доступа к данным.

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

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

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

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