Презентация на тему Нереляционные модели данных

составные единицы информации (СЕИ): векторы (массивы); повторяющиеся группы (когда

в записи присутствует несколько экземпляров СЕИ, состоящих из разнотипных элементов), неповторяющиеся составные единицы информации. Например: в состав записи СОТРУДНИК могут входить простые элементы (ТабНомер, Фамилия), вектор ИнострЯзыки, повторяющаяся группа ПослужнойСписок (ДатаНазначения, ДатаУвольнения, МестоРаботы, Должность) и неповторяющаяся группа Адрес (Город, улица, дом, квартира, индекс). Сложная структура записей характерна для нереляционных БД.

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

Типичными представителями таких систем являются Datacom/DB компании Applied Data Research, Inc. и Adabas компании Software AG. Они применяются, как правило, на больших ЭВМ фирмы IBM. База данных на инвертированных списках похожа на реляционную БД, то есть также состоит из таблиц отношений, однако есть важные отличия:

допускается сложная структура атрибутов (не атомарность);

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

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

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

адреса записи по некоторому пути доступа и некоторому условию,

обновление, удаление или выборка записи с заданным адресом.

Достоинство рассмотренного метода построения базы данных:

более быстрый поиск по сравнению с РБД (особенно поиск уникальной записи по нескольким условиям),

возможность хранения элементов данных со сложной структурой.

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

ПРИМЕР.

Основная таблица:

по условию Фамилия ="Пикулин" и Группа = "98е1" достаточно

найти пересечение списков с соответствующими индексами: адрес искомой записи = (500, 900) ^ (800, 900) = 900.

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

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

записей, каждая структура имеет вид дерева. Деревом называется связный

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

Рассмотрим пример иерархической БД (рис.7.1).

Рис. 7.1. Схема иерархической БД и один экземпляр дерева

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

Каждому узлу соответствует своя структура записей. Например, в узле Отдел запись содержит поля Номер, Название, Фонд з\п.

дерева, содержащий конкретные данные для планового отдела. Для другого

отдела строится другой экземпляр дерева с такой же структурой.

Для отображения другой информации о предприятии могут быть построены другие типы деревьев.

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

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

Найти указанное дерево БД (например, плановый отдел);

Перейти от одного дерева к другому;

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

Перейти от одного узла к другому в порядке обхода иерархии;

Вставить новую запись (экземпляр узла) в указанную позицию;

Удалить текущую запись.

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

Достоинства иерархической модели:

простота и естественность представления экономических данных;

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

N без увеличения избыточности
сложность включения информации о

новых объектах и удаления устаревших данных;

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

Рассмотрим перечисленные недостатки на примере.

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

Рис.7.2. Исходная ER-модель

Можно выделить два варианта в соответствии с тем, какой объект принять за корень дерева:

1. Корень дерева - преподаватель.

о Преподаватель ( Код_пр, ФИО_пр, Уч. звание, кафедра)

о Студент+дисциплина ( N_зач, ФИО_ст, группа, дисциплина, дата_экз, оценка)

но неудобна для представления сведений об успеваемости студентов: если

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

2. Корень дерева - студент

о Студент ( N_зач , ФИО_ст, группа)

о Дисциплина+преподаватель ( Код_пр, ФИО_пр, звание, кафедра, дисциплина, дата_экз, оценка)

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

Переход от инфологической модели к иерархической БД

Методика перехода к иерархической БД может быть различной. Один из способов описан в учебнике [7].

Рассмотрим более простую методику, идея которой состоит в том, чтобы построить дерево на графе инфологической модели. Таких деревьев может быть несколько. При этом корень дерева - узел, в который не входят дуги (если такого узла нет, то следует ввести его). Часть связей нужно удалить и заменить их соответствующими атрибутами объектов.

атрибуты понятия кроме тех, которые принадлежат вышестоящим узлам,

добавляются атрибуты для моделирования связей, явно не отраженных в структуре дерева.

Дублирование атрибутов в узлах позволяет отобразить реальные связи, но увеличивает объем БД.

Пример. Рассмотрим ER-модель факультета (на рис. 7.3 показаны связи типа "является частью" и процесс сдачи экзаменов и чтения лекций).

Рис. 7.3. ER-модель факультета

рис.7.4.
Рис. 7.4. Вариант иерархической модели
В качестве корня выбран

узел “Факультет”, так как все дуги выходят из него. Обратите внимание, как изменился состав атрибутов в узлах дерева: добавлены внешние ключи вместо разорванных связей типа 1:М (например - в узле Экзамен). Вместо удаленных связей М : М добавлены векторные атрибуты "Лекторы" и "Дисциплины" в узле Группа; атрибут "Группы" в узле Лектор, атрибут "Группы" в узле Дисциплина. Налицо дублирование информации, которое можно уменьшить, но тогда усложнится обработка запросов к БД.

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

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

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

сетевой структуре между исходным и порожденными узлами реализуется связь

1:М. Сложной сетевой структурой называют такую схему, в которой присутствует хотя бы одна связь N : M.

В настоящее время большинство СУБД поддерживают только простые сетевые структуры. Такие системы называют СУБД с равноправными (однотипными) файлами. Типичным представителем является Integrated Database Management System (IDMS) компании Cullinet Software Inc., предназначенная для использования на машинах основного класса фирмы IBM под управлением большинства операционных систем. Архитектура системы основана на предложениях Комитета по языкам программирования Conference on Data Systems Languages (CODASYL). В дальнейшем мы будем пользоваться терминологией, принятой в КОДАСИЛ.

Основная конструкция сетевой модели данных КОДАСИЛ - набор (рис.7.5).

Рис. 7.5. Графическое
представление набора

Набор - это поименованное двухуровневое дерево, которое реализует связь между записями двух типов: владельцем набора и членом набора. Разрешаются только связи 1 : М или М : 1 , но связи M : N в явном виде не поддерживаются.

Для каждого набора, устанавливающего связь между предком P и потомком C должны выполняться два условия:

1. Каждый экземпляр Р является предком только в одном экземпляре набора;

2. Каждый экземпляр C является потомком не более чем в одном экземпляре набора.

в каждом наборе только один владелец,
в каждом

наборе 0, 1 или несколько членов,

набор существует, только если существует запись - владелец.

поскольку набор имеет имя, то два экземпляра записи могут быть в разных наборах,

экземпляр записи может входить только в один экземпляр набора данного типа.

в общем случае каждый набор - это вход в БД;

С помощью наборов можно строить многоуровневые деревья и простые сетевые структуры. Так как роль записи жестко не фиксируется, то в одном наборе запись (файл) может быть членом, а в другом владельцем, поэтому такая модель и называется моделью с равноправными файлами.

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

от способа физического хранения различают одночленные, многочленные и сингулярные

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

Рис. 7.7. Примеры одночленного (а) и многочленного (б) наборов