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

Иерархическая модель данных является наиболее простой. Исторически она появилась первой и именно эту модель поддерживает первая из зарегистрированных про­мышленных СУБД IMS фирмы IBM.

Появление иерархической моделисвязано с тем, что в реальном мире очень мно­гие связи соответствуют иерархии, когда один объект выступает как родитель­ский, а с ним может быть связано множество подчиненных объектов. Иерархия проста и естественна в отображении взаимосвязи между объектами.

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

Объекты, связанные иерархическими отношениями образуют ориентированный граф, вид которого представлен на рис. 1.

Уровень 1                            А

Уровень 2           В1        В2         В3

 

Уровень 3  С1     С2 С3    С4

 

Уровень 4 D1 D2 D3 D4 D5 D6 …….

…………

Рис. 1. Графическое изображение иерархической структуры БД.

К основным понятиям иерархической структуры относятся: уровень, элемент (узел), связь.

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

К каждой записи БД существует только один (иерархический) путь от корневой записи. Например, как видно из рис.2.1. для записи Д5 путь проходит через записи А, В2 и С4.

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

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

Стандарт сетевой модели впервые был определен в 1975 году организацией CODASYL (Conference of Data System Languages), которая определила базовые понятия модели и формальный язык описания.

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

Графическое изображение сетевой структуры может быть представлено в виде рис.2.

                    А                       В

 

   С                       D                       Е

  

                  F                        G                     L

Рис.2 Сетевая модель данных

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

Иерархические и сетевые модели данных относятся к так называемым теоретико-графовым моделям.

Реляционная модель данных

 Основные определения

Реляционные модели относятся к теоретико-множественным моделям. Появление теоретико-множественных моделей в системах баз данных было предопределено настоятельной потребностью пользователей в переходе от работы с элементами данных, как это делается в графовых моделях, к работе с некоторы­ми макрообъектами. Основной моделью в этом классе является реляционная модель данных. Простота и наглядность модели для пользователей-непрограм­мистов, с одной стороны, и серьезное теоретическое обоснование, с другой сто­роны, определили большую популярность этой модели. Кроме того, развитие формального аппарата представления и манипулирования данными в рамках реляционной модели сделали ее наиболее перспективной для использования в системах представления знаний, что обеспечивает качественно иной подход к обработке данных в больших информационных системах.

Теоретической основой этой модели стала теория отношений, основу которой заложили два логика — американец Чарльз Содерс Пирс (1839-1914) и немец Эрнст Шредер (1841-1902). В руководствах по теории отношенийбыло показа­но, что множество отношений замкнуто относительно некоторых специальных операций, то есть образует вместе с этими операциями абстрактную алгебру. Это важнейшее свойство отношений было использовано в реляционной модели для разработки языка манипулирования данными, связанного с исходной алгеб­рой. Американский математик Э. Ф. Кодд в 1970 году впервые сформулировал основные понятия и ограничения реляционной модели, ограничив набор опера­ций в ней семью основными и одной дополнительной операцией. Предложения Кодда были настолько эффективны для систем баз данных, что за эту модель он был удостоен престижной премии Тьюринга в области теоретических основ вы­числительной техники.

Основной структурой данных в модели является отношение, именно поэтому модель получила название реляционной ( от английского relation — отношение).

Отношением R называют подмножество декартова произведения D1хD2х... xDn множеств d1,D2,..., Dn (n ³ 1), необязательно различных. Исход­ные множества D1, D2,..., Dn называют в модели доменами.

R Í D1xD2x...xDn,

где D1xD2x...xDn— полное декартово произведение.

Полное декартово произведение — это набор всевозможных сочетаний из n эле­ментов каждое, где каждый элемент берется из своего домена. Например, имеем три домена: D1 содержит три фамилии, D2 — набор из двух учебных дисциплин и D3 — набор из трех оценок. Допустим, содержимое доменов следующее:

- D1 = {Иванов, Крылов, Степанов};

- D2 = {Теория управления, Базы данных};

- D3 = {3, 4, 5}

Тогда полное декартово произведение содержит набор из 18 троек, где первый элемент — это одна из фамилий, второй — это название одной из учебных дис­циплин, а третий — одна из оценок.

<Иванов, Теория управления,3>;<Иванов, Теория управления, 4>;<Иванов, Теория управления,5>;<Крылов, Теория управления, 3>;<Крылов, Теория управления,4>;<Крылов, Теория управления, 5>; <Степанов, Теория управления, 3>; <Степанов Теория управления, 4>;<Степанов, Теория управления.5>; <Иванов, Базы данных, 3>; <Иванов, Базы данных, 4>; <Иванов, Базы данных, 5>; <Крылов, Базы данных, 3>; <Крылов, Базы данных, 4>; <Крылов, Базы данных,5>;<Степанов, Базы данных,3>; <Степанов, Базы данных. 4>; <Степанов, Базы данных,5>.

Отношение R моделирует реальную ситуацию и оно может содержать, допус­тим, только 5 строк, которые соответствуют результатам сессии (Крылов экза­мен по «Базам данных» еще не сдавал):

<Иванов, Теория управления,4>;<Крылов, Теория управления, 5>; <Степанов, Теория управления, 5>; <Иванов, Базы данных,3>; <Степанов, Базы данных,4>;

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

R
Фамилия	Дисциплина	Оценка
Иванов	Теория управления	4
Иванов	Базы данных	3
Крылов	Теория управления	5
Степанов	Теория управления	5
Степанов	Базы данных	4

Данная таблица обладает рядом специфических свойств:

1.В таблице нет двух одинаковых строк.

2.Таблица имеет столбцы, соответствующие атрибутам отношения.

3.Каждый атрибут в отношении имеет уникальное имя.

4.Порядок строк в таблице произвольный.

Домен, входящий в отношение принято называть атрибутом. Строки отношения называются кортежами.

Количество атрибутов в отношении называется степенью, или рангом, отно­шения.

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

В соответствии со свойствами отношений два отношения, отличающиеся только порядком строк или порядком столбцов, будут интерпретироваться в рамках ре­ляционной модели как одинаковые, то есть отношение R и отношениеR1, изо­браженное далее, одинаковы с точки зрения реляционной модели данных.

R1
Дисциплина	Фамилия	Оценка
Теория управления	Крылов	5
Теория управления	Степанов	5
Теория управления	Иванов	4
Базы данных	Иванов	3
Базы данных	Степанов	4

Любое отношение является динамической моделью некоторого реального объ­екта внешнего мира. Поэтому вводится понятие экземпляра отношения, которое отражает состояние данного объекта в текущий момент времени, и понятие схе­мы отношения, которая определяет структуру отношения.

Схемой отношения R называется перечень имен атрибутов данного отношения с указанием домена, к которому они относятся:

Sr = (A1, А2, Аn), Ai Í Di.

Если атрибуты принимают значения из одного и того же домена, то они называ­ются q - сравнимыми, где q — множество допустимых операций сравнения, заданных для данного домена. Например, если домен содержит числовые данные, то для него допустимы все операции сравнения, тогда q = {=, <>,>=, <=,<,>}. Одна­ко и для доменов, содержащих символьные данные, могут быть заданы не толь­ко операции сравнения по равенству и неравенству значений. Если для данного домена задано лексикографическое упорядочение, то он имеет также полный спектр операций сравнения.

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

Sri = (А1, А2,..., Аn) — схема отношения R1.

Sr2 = (В11, В12,..., В1n) — схема отношения R2 после упорядочения имен атрибутов.

Как уже говорилось ранее, реляционная модель представляет базу данных в виде множества взаимосвязанных отношений. В отличие от теоретико-графовых мо­делей в реляционной модели связи между отношениями поддерживаются неяв­ным образом. Какие жесвязи между отношениями поддерживаются в реляци­онной модели? В этой модели, так же как и в остальных, поддерживаются иерархические связи между отношениями. В каждой связи одно отношение мо­жет выступать как основное, а другое отношение выступает в роли подчиненно­го. Это означает, что один кортеж основного отношения может быть связан с несколькими кортежами подчиненного отношения. Для поддержки этих связей оба отношения должны содержать наборы атрибутов, по которым они связа­ны. В основном отношении это первичный ключ отношения (PRIMARY KEY).

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

В подчиненном отношении для моделирования связи должен присутствовать набор атрибутов, соответствующий первичному ключу основного отношения. Однако здесь этот набор атрибутов уже является вторичным ключом, то есть он определяет мно­жество кортежей подчиненного отношения, которые связаны с единственным кортежем основного отношения. Данный набор атрибутов в подчиненном отно­шении принято называть внешним ключом (FOREIGN KEY).

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

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