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

 

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

СОДЕРЖАНИЕ

 

 

Введение

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

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

Историю технологии БД принято отсчитывать  с начала 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 Структура данных

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