Карпова Т.С. Базы данных: модели, разработка, реализация

Подождите немного. Документ загружается.

Сетевая

модель

данных

Записью

называется

совокупность

агрегатов

или

элементов

данных,

модели-

рующая

некоторый

класс объектов

реального

мира.

Понятие

записи

соответ-

ствует

понятию

«сегмент»

иерархической

модели.

Для

записи,

так же как и

для

сегмента,

вводятся

понятия

типа

записи

экземпляра

записи.

Следующим

базовым

понятием

сетевой модели является

понятие

«Набор».

Набором называется

двухуровневый

граф,

связывающий

отношением

«однп-ко-

многим»

два

типа

записи.

Набор

фактически

отражает иерархическую

связь

между двумя

типами

записей.

Родительский

тип

записи

данном

наборе

называется

владельцем

набора,

а до-

черний

тип'записи

—

членом

того

же

набора.

Для

любых двух типов

записей

может

быть

задано

любое

количество

наборов,

которые

их

связывают.

Фактически

наличие

подобных

возможностей

позволяет

промоделировать

отношение

«многие-ко-многпм»

между двумя объектами

ре-

ального

мира,

что

выгодно отличает

сетевую

модель

от

иерархической.

рам-

ках

набора

-возможен

последовательный

просмотр экземпляров

членов

набора,

связанных-с

одним

экземпляром владельца набора.

Между двумя

типами

записей

может быть

определено

любое

количество

набо-

ров;

например,

можно

построить

два

взаимосвязанных

набора.

Существенным

ограничением

набора

является

то, что

один

тот же тип

записи

не

может быть

одновременно

владельцем

членом

набора.

качестве

примера

рассмотрим

таблицу,

на

основе которой

организуем

два на-

бора

определим

связь

между

ними;

Преподаватель

Ищи

Мшшоо

Карпопа

Карп

она

Кар

попа

Смирно»

См up]

юн

Группа

4306

4307

4309

84305

4306

4309

День

недели

Понедельник

Вторник

№

пары

Аудитория

22-13

22-14

23-07

Дисциплина

кид

БЗ ч ЭС

БЗ

ЭС

БД

ГВП

Глава

Теоретико-графовые

модели

данных

Экземпляров

набора

Ведет

занятия

будет

3 (по

числу

преподавателей),

экзем-

пляров

набора

Занимается

будет

4 (по

числу

групп).

На

рис.

3.6

представлены

взаимосвязи

экземпляров

данных

наборов.

Рис.

3.6. Пример взаимосвязи

экземпляров

двух

наборов

Среди

всех

наборов

выделяют

специальный

тин

набора,

называемый

«Сингу-

лярным

набором»,

владельцем

которого

формально

определена

нем

система.

Сингулярный

набор

изображается

виде

входящей

стрелки,

которая

нМсст

соб-

ственно

имя

набора

л имя

члени

набора,

но

которой

не

определен

тин

записи

«Владелец

набора».

Например,

сингулярный

набор

М.

Сингулярные

наборы

позволяют

обеспечить

доступ

экземплярам

отдельных

типов

данных,

поэтому

если

задаче

алгоритм

обработки

информации

предпо-

лагает

обеспечение

произвольного

доступа

некоторому

типу

записи,

то для

поддержки

этой

возможности

необходимо

ввести

соответствующий сингуляр-

ный

набор.

общем случае сетевая база

данных

представляет

совокупность

взаимосвязан-

ных

наборов,

которые

образуют

на

концептуальном

уровне

некоторый

граф.

Язык описания данных

сетевой

модели

Язык

описания

данных

сетевой

модели

имеет

несколько

разделов;

описание

базы

данных

области

размещения;

описания

записей

—

элементов

агрегатов (каждого

отдельности);

описания

наборов

(каждого

отдельности).

SCHEMA

<Иня

БД>.

AREA

NAME

<Иня

физической

области>.

RECORD

NAME

<Иня

записи

(уникальное}>

Для

каждой

записи

определяется

способ

размещения

экземпляров

записи

дан-

ного

типа:

LOCATION

MODE

{DIRECT

(напрямую)

(

CALC

<Иня

программы*

USING

<[Слисок

пер,>]

Сетевая

модель данных

DUPLICATE

ARE

[NOT]

ALLOWED

VIA

<Имя

набора>

SL-Т

(рядом

записями

владельца)

SYSTEM

(решать

будет

система)}

Каждый

тип

записи

должен

быть

приписан

некоторой

физической

области

размещения:

WITHIN

<Имя

области

размещения>

AREA

После

описания

записи

целом

идет

описание

внутренней

структуры:

<Имя

уровня>

<Имя

данного>

<Шаблон>

<Тип>

Номер уровня определяет уровень

вложенности

при

описании

элементов

агре-

гатов

данных.

Первый

уровень

—

сама

запись.

Поэтому

элементы

или

агрегаты

данных

имеют

уровень

начиная

со

второго.

Если

данное

соответствует

агрегату,

то

любая

его

составляющая добавляет

одни

уровень

вложенности.

Если агрегат является

вектором,

то он

описывается

как

<Номе|э

уровня>

<Иня

агрегата>.<Нонер

уровня>

<Иия

1-й

сост,>

если

—

повторяющейся группой,

то

следующим

образом:

<Номер

уровня>

<Иня

агрегата>,OCCURS

Ф-

TIMES

где N —

среднее

количество элементов

группе.

Описание

набора

порядка

включения

членов

него

выглядит

следующим

об-

разом:

SET

NAME

<Иня

наборам

OWNER

<<Имя

владельца>

SYSTEM).

указывается

порядок

включения

новых

экземпляров'члена

данного

набо-

ра

экземпляр

набора:

ORDER PERMANENT

INSERTION

{SORTED

LAST

FIRST}

После

этого

описывается

член набора

указанием

способа

включения

способа

исключения

экземпляра

члена

набора

из

экземпляра набора.

MEMBER

<Иня

члена

набора>

{AUTOMATIC

MANUAL}

{MANDATORY

OPTIONAL}

KEY

(ACCENDING

DESCENDING)

<Имя

элемента

данных*

При

автоматическом

включении

каждый

новый

экземпляр

члена

набора

авто-

матически

попадает

текущий

экземпляр

набора

соответствии

заданным

ра-

нее

порядком

включения.

При

ручном

способе

экземпляр

члена

набора

сначала

попадает

БД,

только потом

командой

CONNECT

может быть включен

конкрет-

ный

экземпляр

набора.

Если

задан способ

исключения

MANDATORY,

то

экземпляр

записи,

исключаемый

из

набора,

автоматически

исключается

и из

базы

данных.

Иначе просто разрыва-

ются

связи.

Внешняя'модель

при

сетевой

организации

данных

поддерживается

путем описа-

ния

части

общего

связного

графа.

Глава

Теоретико-графовые

модели данных

Язык

манипулирования

данными

сетевой

модели

Все

операции

манипулирования

данными

сетевой модели делятся

на

навига-

ционные

операции

операций

модификации.

Навигационные

операции осуществляют

перемещение

по БД

путем

прохожде-

ния

по

связям,

которые

поддерживаются

схеме

БД. В

этом случае результатом

является новый единичный

объект,

который

получает

статус

текущего

объекта.

Операции

модификации

осуществляют

как

добавление новых экземпляров

от-

дельных

типов записей,

так и

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

ров

записей

наборов, модификацию отдельных составляющих внутри конкрет-

ных

экземпляров

записей,

Средства

модификации

данных сведены

табл.

3.1:

Таблица

3.1.

Операторы

Манипулирования

данными

сетевой модели

Операция

READY

FINISH

FIND

GET

STORE

CONNECT

DISCONNECT

MODIFY

ERASE

Назначение

Обеспечение

доступа

данного

процесса

или

пользователя

БД

(сходна

по

смыслу

операцией

открытия

файла)

Окончание

работы

с БД

Группа

операции,

устанавливающих

указатель

найденного

объекта

на

текущий

объект

Передача

найденного

объекта

рабочую

область.

Допустима

только

после

FIND

Помещение

в БД

записи,

сформированной

рабочей

области

Включение

текущем

записи

текущий

экземпляр

набора

Исключение

текущей

записи

из

текущего

экземпляра

набора

Обновление

текущей

записи

данными

из

рабочей

области

пользователя

Удаление

экземпляра

текущей

записи

рабочей области пользователя хранятся

шаблоны

записей,

программные пере-

менные

и три

типа указателей текущего

состояния:

текущая запись процесса (код

или

ключ последней записи,

которой работа-

ла

данная

программа);

текущая запись типа

записи

(для

каждого

типа

записи ключ последней запи-

си,

которой работала программа);

текущая запись типа набор

(для

каждого набора

владельцем

Т1 и

членом

Т2

указывается,

Т1 пли Т2

были

последней

обрабатываемой

записью).

На

рис.

3.7

представлена

концептуальная модель

торгово-посредпаческой

орга-

низации.

Сетевая

модель

данных

Рис.

3.7.

Схема

БД

«Торговая фирма»

При

необходимости возможно

описание

элементов

данных,

которые

не

принад-

лежат

непосредственно

данной

записи,

по

при

ее

обработке часто

используются.

Для

этого

используется

тип

VIRTUAL

обязательным

указанием

источника

дан-

ного

элемента

данных.

RECORD

Цены

Цена

TYPE

REAL

Товар VIRTUAL

SOURCE

Товары.НаименованиеТовара

OWNER

Товар-Цены

SET

Наиболее

интересна

операция

поиска

(FIND),

так как

именно

она

отражает суть

навигационных

методов, применяемых

сетевой

модели.

Всего

существует

семь

типов

операций

поиска:

По

ключу

(запись

должна

быть

описана

через

CALC

USING

...)'

FIND

<Иня

записи*

RECORD

CALC

KEY

<Имя

параметра*

Последовательный

просмотр

записей

данного

типа:

FIND DUPLICATE

<Имя

записи>

RECORD

CALC

KEY

Найти

владельца

текущего

экземпляра набора;

FIND

OWNER

CURRENT

<Иня набора>

SET

Последовательный

просмотр

записей-членов

текущего экземпляра

набора:

FIND

(FIRST

NEXT)

<Имя

записи>

RECORD

CURRENT

<Иня

набора*

SET

Глава

Теоретике-графовые

модели данных

Просмотр

записей—членов

экземпляра

набора,

специфицированных

рядом

нолей;

FIND

[DUPLICATE]

<Иия

записи>

RECORD

CURRENT <Иия

набора>

SET

USING

<Список

полей>

Сделать

текущей

записью

процесса

текущий

экземпляр

набора:

FIND

CURRENT

<Иня

набора^

SET

Установить

текущую

запись

процесса:

FIND

CURRENT

<Имя

записи*

RECORD

Например,

алгоритм

программа печати заказов, сделанных

Петровым,

будут

выглядеть

так:

ФИО

"Петров"

FIND

Люди

RECORD

CALC

KEY

FIND FIRST

Заказы

RECORD

CURRENT

Лйди-Заказы

SET

WHILE

NOT

FAIL

DO-

FIND

OWNER

CURRENT

Товары-Заказы

SET

GET

Товары

НаимТовара

FIND NEXT

Заказы

RECORD

CURRENT

Люди-Заказы

SET

END

ГЛАВА

Реляционная

модель

данных

Основные

определения

Появление

теоретико-множественных

моделей

системах

баз

данных было пред

определено

настоятельной

потребностью пользователей

переходе

от

работы

элементами данных,

как это

делается

графовых

моделях,

работе

некоторы-

ми

макрообъсктамн.

Основной

моделью

этом классе

является

реляционная

модель

данных.

Простота

наглядность

модели

для

пользователей-непрограм-

мистов,

одной стороны,

серьезное

теоретическое

обоснование,

другой сто-

роны,

определили

большую популярность

;УГОН

модели.

Кроме того,

развитие

формального аппарата

представления

манипулирования

данными

рамках

реляционной

модели

сделали

се

наиболее

перспективной

для

использования

системах

представления

знаний,

что

обеспечивает

качественно

иной

подход

обработке

данных

больших

информационных

системах.

Теоретической

основой

этой

модели

стала

теория

отношений,

основу

которой

заложили

два

логика

—

американец

Чарльз

Содерс

Пире

(1839-1914)

немец

Эрнст

Шредер

(18-11-1902).

руководствах

по

теории

отношении

было

показа-'

по,

что

множество

отношений

замкнуто

относительно

некоторых

специальных

операций,

то.есть

образует вместе

этими

операциями

абстрактную алгебру.

Это

важнейшее

свойство

отношений

было

использовано

реляционной

модели

для

разработки

языка

манипулирования

данными,

связанного

исходной

алгеб-

рой,

Американский

математик

Э.

Ф.

Кодд

1070

году

впервые

сформулировал

основные

понятия

ограничения

реляционной

модели,

ограничив

набор

опера-

ций

ней

семью

основными

одной

дополнительной

операцией.

Предложения

Кодда

были

настолько

эффективны

для

систем

баз

данных,

что за эту

модель

он

был

удостоен

престижной

премии

Тьюринга

области

теоретических

основ

вы-

числительной

техники.

Основной структурой

данных

модели

является

отношение,

именно

поэтому

модель

получила

название

реляционной

(от

английского

relation

—

отношение).

N-арным

отношением

называют

подмножество

декартова

произведения

D^D-jx

...

множеств

D,,

Ц, (п

1),

необязательно

различных.

Исход-

ные

множества

D,,

....

называют

модели

доменами.

Глава

Реляционная

модель

данных

DjxD2X...xD,,,

где

DjxD

...xD

,—

полное

декартово

произведение.

Полное

декартово

произведение

— это

набор

всевозможных

сочетаний

из

эле-

ментов каждое,

где

каждый

элемент

берется

из

своего

домена.

Например,

имеем

три

домена:

содержит

три

фамилии,

—

набор

из

двух

учебных

дисциплин

—

набор

из

трех

оценок.

Допустим,

содержимое доменов

следующее:

{Иванов,

Крылов,

Степанов};

{Теория

автоматов,

Базы

данных};

{3,

4, 5}

Тогда полное декартово

произведение

содержит набор

из 18

троек,

где

первый

элемент

— это

одна

из

фамилий, второй

— это

название

одной

из

учебных дис-

циплин,

третий

—

одна

из

оценок.

<Иванов,Теория

автоматов.3>:

«Иванов.Теория

автоматов,4>;

<Ивано8,Теория

автоматов.5>

<Крылов,Теория

автоматов,3>:

<Крылов.Теория

автоматов.4>:

<Крылов.Теория

автоматов,5>;

<Степаноз.Теория

автоматов.3>;

<Степанов.Теория

автоматов.4>:

«Степанов.Теория

автоматов,5>:

<Иванов.Базы

данных,3>:

<Иванов,Базы

данных.4>;

<Иеанов.Базы

данных.5>:

<Крылов,Базы

данных.3>:

<Крылов.Базы

данных.4>:

«Крылов.Базы

данных.5>:

<Степанов'.Базы

данных,3>;

<Степанов,Базы

данных.4>:

<Степанов,Базы

данных.5>;

Отношение

моделирует реальную

ситуацию

оно

может

содержать,

допус-

тим,

только

строк, которые соответствуют результатам

сессии

(Крылов экза-

мен

по

«Базам

данных»

еще не

сдавал);

<Иванов.Теория

автоматов,4>:

<Крылов,Теория

автоматов.5>;

«Степанов.Теория

автоматов,5>:

<Иванов.Базы

данных.3>;

-Степанов.Базы

данных,4>;

Отношение

имеет простую графическую

интерпретацию,

оно

может быть пред-

ставлено

виде

таблицы,

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

доменов

отношение,

строки

наборам

из п

значений,

взятых

из

исходных доменов,

которые

расположены

строго

определенном

порядке

соответствии

заголов-

ком. Такие наборы

из п

значений

часто

называют

п-ками.

Фамилия

пап

он

Иванов

Крылов

Степанов

Дисциплина

Теория

автоматов

Базы

данных

Теория

автоматов

Теория

автоматов

Базы

данных

Оценка

Данная

таблица обладает рядом

специфических

свойств;

Основные

определения

таблице

нет

двух

одинаковых

строк,

Таблица

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

Каждый

атрибут

отношении

имеет

уникальное

имя.

Порядок

строк

таблице

произвольный.

Вхождение

домена

отношение

принято

называть

атрибутом.

Строки

отноше-

ния

называются

кортежами.

Количество атрибутов

отношении

называется

степенью,

или

рангом,

отно-

шения.

Следует

заметить,

что в

отношении

не

может быть одинаковых кортежей,

это

следует

из

математической модели: отношение

— это

подмножество декартова

произведения,

а в

декартовом

произведении

все

и-ки

различны.

соответствии

со

свойствами

отношений

два

отношения,

отличающиеся только

порядком

строк

или

порядком

столбцов,

будут интерпретироваться

рамках

ре-

ляционной

модели

как

одинаковые,

то

есть отношение

R и

отношение

RI,

изо-

браженное

далее,

одинаковы

точки

зрения

реляционной модели данных.

Дисциплина

Теория

автоматов

Теория

автоматов

Теория

автоматов

Базы

данных

Базы

данных

Фамилия

Крылов

Степанов

Иванов

Степанов

Оценка

Любое

отношение

является

динамической

моделью некоторого реального объ-

екта

внешнего

мира.

Поэтому вводится понятие экземпляра отношения, которое

отражает

состояние

данного

объекта

текущий

момент

времени,

понятие схе-

мы

отношения,

которая определяет структуру

отношения.

Схемой

отношения

называется перечень

имен

атрибутов данного отношения

указанием

домена,

которому

они

относятся;

5л

(А|,

Аи),

А, с

D,.

Если

атрибуты

принимают

значения

из

одного

того

же

домена,

то они

называ-

ются

^-сравнимыми,

где 9 -

множество

допустимых

операций

сравнения,

задан-

ных

для

данного

домена.

Например,

если домен содержит числовые данные

, то

для

него допустимы

все

операции

сравнения,

тогда

{=,

<>,>=,<",<,>}.

Одна-

ко

и для

доменов,

содержащих

символьные

данные,

могут быть заданы

не

толь-

ко

операции

сравнения

по

равенству

неравенству

значений.

Если

для

данного

домена

задано

лексикографическое

упорядочение,

то он

имеет

также

полный

спектр

операций сравнения.

Схемы

двух

отношений

называются

эквивалентными,

если

они

имеют

одинако-

вую

степень

возможно

такое

упорядочение

имен

атрибутов

схемах,

что

на

одинаковых

местах

будут

находиться

сравнимые

атрибуты,

то

есть

атрибуты,

принимающие

значения

из

одного

димепа.

Глава

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

SRI

(А

АЗ,

...,

А„)

схема отношения

SRS

(Вц,

В|2

[п

)

—

схема

отношения

после

упорядочения

имен

атрибутов.

Тогда

Как

уже

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

цпде

множества взаимосвязанных

отношений.

отличие

от

теоретико-графовых

лю-

делей

реляционной модели

связи

между

отношениями

поддерживаются неяв-

ным

образом.

Какие

же

связи

между

отношениями

поддерживаются

реляци-

онной

модели?

этой

модели,

так же как и в

остальных,

поддерживаются

иерархические

связи между

отношениями.

каждой связи одно

отношение

мо-

жет

выступать

как

основное;

другое отношение выступает

роля

подчиненно-

го. Это

означает,

что

один

кортеж

основного

отношения

может

быть

связан

несколькими

кортежами

подчиненного

отношения.

Для

поддержки

этих связей

оба

отношения

должны

содержать

наборы

атрибутов»

по

которым

они

связа-

ны.

основном

отношении

это

первичный ключ отношения

(PRIMARY

KEY),

который

однозначно

определяет

кортеж основного

отношения.

подчиненном

отношении

для

моделирования

связи должен присутствовать

набор

атрибутов,

соответствующий

первичному

ключу

основного

отношения.

Однако здесь этот

набор

атрибутов

уже

является вторичным ключом,

то

есть

он

определяет мно-

жество

кортежей подчиненного

отношения,

которые связаны

единственным

кортежем

основного

отношения.

Данный

набор

атрибутов

подчиненном

отно-

шении

принято называть

внешним

ключом (FOREIGN KEY).

Например, рассмотрим ситуацию, когда

надо

описать карьеру

некоторого

инди-

видуума. Каждый человек

своей трудовой

деятельности

сменяет несколько мест

работы

разных организациях,

где

он

работает

разных

должностях. Тогда

мы

должны создать

два

отношения;

одно

для

моделирования

всех

работающих

лю-

дей,

другое

для

моделирования записей

в их

трудовых

книжках,

если

для нас

важно

не

только отследить

переход

работника

из

одной

организации

другую,

но

прохождение

его по

служебной

лестнице

рамках

одной

организации

(рис,

4.1).,

Рис, 4.1; Связь

между

основным

подчиненным отношениями

KIMAKY

К1:У

опюшения

Сотрудник

атрибут

Паспорт

являс-п

FOREIGN

KEY

отнищсшш

«карьера».