Иерархические системы

Следствия из основных правил

Основные правила

1. Рефлексивность. Пусть задано множество Х и У Í Х, тогда Х ® Х или Х ® У. Это тривиальные функциональные зависимости, означающие, что множество определяет любое свое подмножество.

2. Транзитивность. Если Х ® У, У ® Z, то Х ® Z.

3. Дополнительность. Если Х ® У и Х Í W, то W ® Y

1. Аддитивность (объединение). Если Х ® Y и W ® Z, то ХW ® УZ, или X ® Y и X ® Z, то Х ® YZ.

2. Проективность (декомпозиция). Если Х ® YZ, то Х ® Y и X ® Z

3. Псевдотранзитивность. Если Х ® У и YW ® Z, то XW ® Z.

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

Основным типом логической структуры, поддерживаемой иерархическими СУБД, является иерархия, или древовидная структура. Иерархическая структура определяется на соответствующих типах записей (или сегментах) согласно схеме прикладной базы данных или дереву определений. В этом дереве типы записей являются узлами, а дуги представляют связи исходный — порожденный между узлами дерева различных уровней. Если разность уровней двух связанных узлов равна единице, то связь является непосредственной (без промежуточных узлов). Кроме того, любые две вершины дерева, принадлежащие одной ветви, транзитивно связаны друг с другом. На рис. 1 показана иерархия пяти типов записей, сокращенный вариант исходной схемы и пример загруженной базы данных.

Рис.1

На рис. 1, в приведено несколько экземпляров иерархических записей базы данных, соответствующих дереву определений. Экземпляр дерева базы данных не обязательно должен содержать все свои сегменты. (Примерами являются первое дерево R₁ и предпоследнее дерево R_n-1. При необходимости можно добавлять или удалять экземпляры типов записей в соответствии с требованиями приложения. Предположим, что типы записей А, В, С, D и Е интерпретируются как типы записей «Курс», «Предварительная регистрация», «Семестр», «Преподаватель» и «Студент». Информация о некотором курсе может отсутствовать (например, R_n-1), либо для курса может быть известна лишь предварительная регистрация (R₁). В качестве упражнения читатель может предложить содержательную интерпретацию оставшихся экземпляров деревьев базы данных. (Предположите, что распределение преподавателей по курсам в различные семестры и предварительная регистрация студентов на курсы проводятся независимо, а решение о необходимости чтения курса принимается позже.)

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

Дата добавления: 2014-01-03