Иерархические структуры данных

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

Ограничения целостности

Манипулирование данными

Структуры данных

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

1. Строки таблиц упорядочены системой в некоторой физической последовательности.

2. Физическая упорядоченность строк всех таблиц может определяться и для всей БД (так делается, например, в Datacom/DB).

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

Поддерживаются два класса операторов:

1. Операторы, устанавливающие адрес записи, среди которых:

1.1. прямые поисковые операторы (например, найти первую запись таблицы по некоторому пути доступа);

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

2. Операторы над адресуемыми записями

Типичный набор операторов:

1. Найти первую запись таблицы T в физическом порядке;

2. Найти первую запись таблицы T с заданным значением ключа поиска K;

3. Найти запись, следующую за записью с заданным адресом в заданном пути доступа;

4. Найти следующую запись таблицы T в порядке пути поиска с заданным значением K;

5. Найти первую запись таблицы T в порядке ключа поиска K cо значением ключевого поля, большим заданного значения K;

6. Выбрать запись с указанным адресом;

7. Обновить запись с указанным адресом;

8. Удалить запись с указанным адресом;

9. Включить запись в указанную таблицу; операция генерирует адрес записи.

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

Типичным представителем (наиболее известным и распространенным) является Information Management System (IMS) фирмы IBM. Первая версия появилась в 1968 г. До сих пор поддерживается много баз данных, что создает существенные проблемы с переходом как на новую технологию БД, так и на новую технику.

Иерархическая БД состоит из упорядоченного набора деревьев; более точно, из упорядоченного набора нескольких экземпляров одного типа дерева.

Тип дерева (рис. 2.1) состоит из одного "корневого" типа записи и упорядоченного набора из нуля или более типов поддеревьев (каждое из которых является некоторым типом дерева). Тип дерева в целом представляет собой иерархически организованный набор типов записи.

рис. 2.1 Пример типа дерева (схемы иерархической БД)

Здесь (рис. 2.1) Группа является предком для Куратора и Студенты, а Куратор и Студенты – потомки Группа. Между типами записи поддерживаются связи.

База данных с такой схемой могла бы выглядеть следующим образом (рис. 2.2):

рис. 2.2 Один экземпляр дерева.

Все экземпляры данного типа потомка с общим экземпляром типа предка называются близнецами. Для БД определен полный порядок обхода – сверху-вниз, слева-направо.

В IMS использовалась оригинальная и нестандартная терминология: "сегмент" вместо "запись", а под "записью БД" понималось все дерево сегментов.