Иерархическая модель. Системы инвертированных списков

Системы инвертированных списков

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

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

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

Свойства:

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

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

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

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

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

2) Операторы над адресуемыми записями (удалить, обновить, добавить, найти запись).

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

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

Достоинства:

1) простота и понятность схемы данных.

2) удобство реализации на ЭВМ.

3) эффективная обработка данных.

Недостатки:

1) отсутствие стандартных средств идентификации отдельных записей.

2) сложность описания иерархических и сетевых связей.

3) сложность обращения к записям для пользователя.

В иерархической модели связи между данными можно описать с помощью упорядоченного графа (дерева):

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

Для описания структуры (схемы) иерархической БД на некотором языке программирования используется тип «дерево». Данный тип схож с типом «запись» языка Паскаль. Как и там, в типе «дерево» допускается вложенность типов, т.е. данный тип является составным. Подтипы также являются типом «дерево».

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

ЗдесьОтдел является предком для Начальник и Сотрудники, а Начальник и Сотрудники - потомки Отдел. Между типами записи поддерживаются связи.

Корневым называется тип, который имеет подчиненные типы и сам не является подтипом. Подчиненный тип (подтип) является потомком по отношению к типу, который выступает для него в роли предка (родителя). Потомки одного и того же типа являются близнецами по отношению друг к другу.

В целом тип «дерево» представляет собой иерархически организованный набор типов «запись».

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

Для БД определен полный порядок обхода - сверху-вниз, слева-направо.

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

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

1) Поиск указанного экземпляра БД (например, дерева со значением 310 в поле Отд_номер);

2) Переход от одного дерева к другому или переход от одной записи к другой внутри дерева (например, от отдела - к первому сотруднику);

3) Вставка или удаление записи в указанную позицию;

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

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

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

Достоинства:

1) эффективное использование памяти ЭВМ.

2) быстрота выполнения основных операций.

3) эффективна при работе с иерархически упорядоченной информацией.

Недостатки:

1) громоздкость модели.

2) сложность логических связей.

3) сложность понимания для обычного пользователя.

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