ДАЛЬНЕВОСТОЧНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ

Филиал в г.Уссурийске

кафедра Финансов и сервиса

Курсовая работа

"Дореляционные базы данных"

Выполнил  студент гр.10312

Абасова Э.А.

Руководитель: Ким В.С.

Уссурийск-2011 г.

СОДЕРЖАНИЕ

Введение              3

1 Дореляционные базы данных              5

1. 1 Иерархические БД              6

1. 1. 1 Структура данных              6

1. 1. 2 Операции над данными              10

1. 1. 3 Ограничение целостности              11

1. 2 Сетевые БД              11

1. 2. 1 Структура данных              11

1. 2. 2 Операции над данными              14

1. 2. 3 Ограничение целостности              15

1. 3 БД, основанные на инвертированных списках              15

1. 3. 1  Структура данных              16

1. 3. 2 Манипулирование данными              16

1. 3. 3 Ограничение целостности              17

1. 4 Достоинства и недостатки дореляционных баз данных              17

Заключение              19

Список использованной литературы              21

Введение

Исторически сложившееся развитие вычислительных систем обусловило необходимость хранения в электронном виде все большего количества информации. Одновременно с совершенствованием и дальнейшим развитием вычислительных систем росли объемы информации, подлежащей обработке и хранению. Сложности, возникшие при решении на практике задач структурированного хранения и эффективной обработки возрастающих объемов информации, стимулировали исследования в соответствующих областях. Задачи хранения и обработки данных были формализованы. Была создана теоретическая база для решения задач такого класса, результатом реализации на практике которой стали системы, предназначенные для организации обработки, хранения и предоставления доступа к информации. Позже такие системы стали называть системами баз данных.

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

              Историю технологии БД принято отсчитывать с начала 1960-х гг., когда появились первые попытки создания специальных программных средств управления базами данных. За прошедшие десятилетия возникали и использовались различные подходы к организации баз данных. Для описания и сравнения некоторых из них мы воспользуемся понятием модели данных, предложенным в 1969 г. Эдгаром Коддом.

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

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

1 Дореляционные базы данных

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

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

      не основывались на каких-либо абстрактных моделях. Как упоминалось, понятие модели данных фактически вошло в обиход специалистов в области БД только вместе с реляционным подходом. Абстрактные представления ранних систем появились позже на основе анализа и выявления общих признаков у различных конкретных систем.

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

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

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

      После появления реляционных систем большинство ранних систем было оснащено «реляционными» интерфейсами. Однако в большинстве случаев это не сделало их по-настоящему реляционными системами, поскольку оставалась возможность манипулировать данными в естественном для них режиме [5].

1. 1 Иерархические БД

Первые системы управления базами данных, появившиеся в середине 60-х годов, использовали иерархическую модель данных, и во времени их появление предшествует появлению сетевой модели. Типичным представителем (наиболее известным и распространенным) является Information Management System (IMS) фирмы IBM. Первая версия появилась в 1968 г в результате повышенных требований к огромному хранилищу информации, связанной с полетом на Луну по программе Apollo. Известны и другие системы этого класса: PC/Focus, Team-UP, Data Edge, Ока, ИНЭС, МИРИС. До сих пор поддерживается много баз данных, что создает существенные проблемы с переходом как на новую технологию БД, так и на новую технику [1].

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

Появление иерархической модели связано с тем, что в реальном мире очень многие связи соответствуют иерархии, когда один объект выступает как родительский, а с ним может быть связано множество подчиненных объектов. Иерархия проста и естественна в отображении взаимосвязи между классами объектов. В иерархических моделях основная структура представления данных имеет форму дерева. На самом высшем (первом) уровне иерархии находится только вершина, которая называется корнем дерева. Эта вершина имеет связи с вершинами третьего уровня и т. д. Связи между вершинами одного уровня отсутствуют. Следовательно, данные в иерархической структуре не равноправны: одни жестко подчинены другим. Доступ к информации возможен только по вертикальной схеме, начиная с корня, так как каждый элемент связан только с одним элементом на верхнем уровне и с одним или несколькими на нижнем [1].

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

Рис.1 – Иерархическая модель данных

              Реальный пример иерархической базы данных представлен на рис. 2.

Рис. 2 – Пример иерархической базы данных

Основными информационными единицами в иерархической модели являются: база данных (БД), сегмент и поле. Поле данных определяется как минимальная, неделимая единица данных, доступная пользователю с помощью СУБД. Например, если в задачах требуется печатать в документах адрес клиента, но не требуется дополнительного анализа полного адреса, то есть города, улицы, дома, квартиры, то мы можем принять весь адрес за элемент данных, и он будет храниться полностью, а пользователь сможет получить его только как полную строку символов из БД. Если же в наших задачах существует анализ частей, составляющих адрес, например города, где расположен клиент, то нам необходимо выделить город как отдельный элемент данных, только в этом случае пользователь может получить к нему доступ и выполнить, например, запрос на поиск всех клиентов, которые проживают в конкретном городе, например в Париже [2].

Сегмент в терминологии Американской Ассоциации по базам данных DBTG называется записью. В рамках иерархической модели определяются два понятия: тип сегмента или тип записи и экземпляр сегмента или экземпляр записи. Тип сегмента –  это поименованная совокупность типов элементов данных, в него входящих. Экземпляр сегмента образуется из конкретных значений полей или элементов данных, в него входящих. Очень важно понимать различие между сегментом и типом сегмента – оно такое же,

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

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

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

1. 1. 2 Операции над данными 

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

Типичные операторы поиска данных:

        Найти указанное дерево БД;

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

        Найти экземпляр сегмента, удовлетворяющий условию поиска;

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

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

Типичные операторы поиска данных с возможностью модификации:

      Найти и удержать для дальнейшей модификации единственный экземпляр сегмента, удовлетворяющий условию поиска;

      Найти удержать для дальнейшей модификации следующий экземпляр сегмента с теми же условиями поиска;

      Найти удержать для дальнейшей модификации следующий экземпляр для того же родителя;

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

      Вставить новый экземпляр сегмента в указанную позицию;

      Обновить текущий экземпляр сегмента;

      Удалить текущий экземпляр сегмента;

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

1. 1. 3 Ограничение целостности

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

1. 2 Сетевые БД

Сетевые модели были призваны устранить некоторые недостатки иерархических моделей. Одна из первых сетевых данных, разработанная группой CODASYL (COnferens on DAta SYstem Languages), была предложена в 1969 г. и стала в свое время (1971 г.) стандартом СУБД, и развивалась до 80-х годов. Эта модель позволила ускорить доступ к данным, но изменение структуры базы по-прежнему требовало значительных усилий и времени. К известным сетевым системам управления базами данных относится: DBMS, IDMS, TOTAL, VISTA, Сеть, Сетор, Компас и др. [1].

1. 2. 1 Структура данных

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

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

Элемент данных – это наименьшая поименованная информационная единица данных, доступная пользователю. Элемент данных должен иметь свой тип.

Агрегат данных соответствует следующему уровню обобщения – поименованная совокупность элементов данных внутри записи или другого агрегата. Пример агрегата представлен на рис. 3.

Рис. 3 – Агрегат Дата

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

Агрегат данных Дата входит в состав записи Сотрудник. (рис. 4 )

Тип записей – это совокупность логически связанных экземпляров записей. Тип записей моделирует некоторый класс объектов реального мира.

В качестве элемента данных могут быть использованы только простые типы, а в качестве агрегатов могут быть использованы сложные типы: вектор и повторяющаяся группа [2].

Рис. 4 – Запись Сотрудник

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

Рис. 5 – Запись Заказ

Набор – это поименованная двухуровневая иерархическая структура, которая содержит запись владельца и записи членов. Наборы выражают связи «один ко многим» или «один к одному» между двумя типами записей. Тип набора поддерживает работу с внутренними структурами типов записей.

Набор, приведенный на рис. Определяет тип записи-владельца Отдел и тип записи-члена набор Сотрудник, а также тип связи между ними «один ко многим» –  с именем Работает. Имя набора – это метка, присвоенная стрелке. Связь типа «один ко многим» допускает возможность того, что с данным экземпляром записи-владельца может быть связан ноль, один, или несколько экземпляров записи-члена [2].

Рис. 6 – Диаграмма типа набора Работает

Используя понятия сетевой модели данных, можно получить другое изображение такого набора (рис. 7), где представлены логические типы записей Отдел и Сотрудник, их структура и связь между типами записей Работает.

База данных в сетевой модели данных – это поименованная совокупность экземпляров записей различного типа и экземпляров наборов содержащих связи между ними.

Рис. 7 – Набор Работает между двумя типами записей Отдел и Сотрудник

1. 2. 2 Операции над данными 

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

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

      Найти конкретную запись в наборе однотипных записей и сделать ее текущей;

      Перейти от записи-владельца к записи-члену в некотором наборе;

      Перейти к следующей записи в некоторой связи;

      Перейти от записи-члена к владельцу по некоторой связи;

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

      Извлечь текущую запись в буфер прикладной программы для обработки;

      Заменить в извлеченной записи значения указанных элементов данных на заданные новые их значения;

      Запомнить запись из буфера в БД;

      Создать новую запись;

      Уничтожить запись;

      Включить текущую запись из текущего экземпляра набора [1].

1. 2. 3 Ограничение целостности

Как и в иерархической модели обеспечивается только поддержание целостности по ссылкам (владелец отношения - член отношения).

1. 3 БД, основанные на инвертированных списках

К числу наиболее известных и типичных представителей таких систем относятся Datacom/DB компании Applied Data Research, Inc. (ADR), ориентированная на использование на машинах основного класса фирмы IBM, и Adabas компании Software AG.

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

1. 3. 1 Структура данных

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

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

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

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

1. 3. 2 Манипулирование данными

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

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

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

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

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

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

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

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

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

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

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

1. 3. 3 Ограничение целостности

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

1. 4 Достоинства и недостатки дореляционных баз данных

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

Основное достоинство сетевой модели – это высокая эффективность затрат памяти и оперативность обработки данных. Недостаток – сложность и жесткость схемы базы, а также сложность понимания. Кроме того, в этой модели ослаблен контроль целостности, так как в ней допускается устанавливать произвольные связи между записями [1].

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

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

      Развитые средства управления данными во внешней памяти на низком уровне;

      Возможность построения вручную эффективных прикладных систем;

      Возможность экономии памяти за счет разделения подобъектов (в сетевых системах).

Недостатки:

      Слишком сложно пользоваться;

      Фактически необходимы знания о физической организации;

      Прикладные системы зависят от этой организации;

      Их логика перегружена деталями организации доступа к БД.

Заключение

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

В классической теории баз данных, модель данных есть формальная теория представления и обработки данных в системе управления базами данных (СУБД), которая включает, по меньшей мере, три аспекта:

1.      аспект структуры: методы описания типов и логических структур данных в базе данных;

2.      аспект манипуляции: методы манипулирования данными;

3.      аспект целостности: методы описания и поддержки целостности базы данных.

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

В данной курсовой работе были рассмотрены дореляционные базы данных на основе этих трех аспектов. Основное различие между этими моделями данных состоит в способах описания взаимодействий между объектами и атрибутами.

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

Список использованной литературы

1.      Бородина, А. И. Технологии баз данных и знаний [Текст]: Курс лекций. Мн.: БГЭУ, 2008. – 505 с.

2.      Бураков, П. В., Петров, В. Ю. Введение в системы баз данных [Текст]: Учебное пособие. Спб.: Питер, 2010. – 129 с.

3.      Дейт, К. Дж. Введение в системы баз данных [Текст]: Учебник. – 7-е издание. – М.: Издательский дом «Вильямс», 2001. – 1072 с.

4.      Карпова, Т. С. Базы данных: модели, разработка, реализация [Текст]: Учебное пособие. Спб.: Питер, 2001. – 304 с.

5.      Кузнецов, С. Основы современных баз данных [Текст]: Учебное пособие. – 2-е изд., испр. – М.: Интернет-Университет Информационных Технологий; БИНОМ. Лаборатория знаний, 2007. – 484 с.

6.      Мишенин, А. И. Теория экономических информационных систем [Текст]: Учебник.– 4-е изд., доп. и перераб. – М.: «Финансы и статистика», 2002.– 240 с.

7.      Ролланд, Ф. Д. Основные концепции баз данных [Текст]: Учебник. – М.: Издательский дом «Вильямс», 2002. – 256 с.

16