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

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

ГЛАВА

Теоретико-

графовые

модели

данных

Как

уже

упоминалось

ранее,

эти

модели отражают

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

объектов реаль-

ного мира

виде графа

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

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

объектов,

зависи-

мости

от

типа

графа

выделяют

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

или

сетевую

модели.

Историче-

ски

эти

модели

появились раньше,

и в

настоящий

момент

они

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

реже,

чем

более

современная

реляционная

модель

данных. Однако

до сих пор

существуют системы, работающие

па

основе этих моделей,

одна

из

концепций

развития

объектно-ориентированных

баз

данных

предполагает объединение

принципов

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

концепцией реляционной.

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

модель

данных

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

модель

данных

является

наиболее

простой

среди

всех

даталоги-

ческих

моделей.

Исторически

она

появилась первой среди

всех

диалогических

моделей:

именно

эту

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

из

зарегистрированных про-

мышленных СУБД

IMS

фирмы IBM.

Появление иерархической модели связано

тем,

что в

реальном мире

очень

мно-

гие

связи соответствуют иерархии, когда один объект выступает

как

родитель-

ский,

а с ним

может быть

связано

множество подчиненных объектов. Иерархия

проста

естественна

отображении взаимосвязи между классами

объектов.

Основными информационными единицами

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

база

данных

(БД),

Сегмент

поле, Поле данных

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

как

минимальная,

неделимая

единица

данных,

доступная

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

помощью

СУБД.

Напри-

мер, если

задачах

требуется

печатать

документах

адрес

клиента,

но не

требуется

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

анализа

полного

адреса,

то

есть города,

улицы,

дома, кварти-

ры,

то мы

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

за

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

и он

будет храниться

полностью,

пользователь сможет получить

его

только

как

полную строку сим-

волов

из БД,

Если

же в

наших

задачах существует анализ частей, составляющих

адрес, например города,

где

расположен

клиент,

то нам

необходимо выделить

город

как

отдельный

элемент

данных, только

этом

случае

пользователь может

Глава

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

модели

данных

получить

нему доступ

выполнить,

например,

запрос

на

поиск всех

клиентов,

которые

проживают

конкретном городе, например

Париже. Однако если

пользователю понадобится

полный

адрес клиента,

то

остальную информацию

по

адресу также необходимо хранить

отдельном

поле,

которое может быть

на-

звано,

например,

Сокращенный

адрес.

этом случае

для

каждого клиента

в БД

хранится

как

Город,

так и

Сокращенный

адрес.

Сегмент

терминологии Американской Ассоциации

по

базам

данных

DBTG

(Data

Base

Task

Group) называется

записью,

при

этом

рамках

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

модели определяются

два

понятия:

тип

сегмента

или тип

записи

экземпляр

сегмента

или

экземпляр

записи.

Тип

сегмента

— это

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

него

входящих. Экземпляр сегмента образуется

из

конкретных значений полей

или

элементов данных,

него

входящих.

Каждый

тип

сегмента

рамках иерархиче-

ской

модели образует

некоторый

набор однородных записей.

Для

возможности

различия

отдельных записей

данном наборе каждый

тип

сегмента должен

иметь

ключ

или

набор ключевых атрибутов (полей, элементов данных). Ключом

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

элементов

данных, однозначно идентифицирующих экземп-

ляр

сегмента. Например, рассматривая

тип

сегмента, описывающий

сотрудника

организации,

мы

должны выделить

те

характеристики

сотрудника,

которые

мо-

гут его

однозначно идентифицировать

рамках

БД

предприятия. Если предполо-

жить,

что на

предприятии

могут

работать

однофамильцы,

то,

вероятно,

наибо-

лее

надежным будет идентифицировать сотрудника

по его

табельному номеру.

Однако

если

мы

будем

строить

БД,

содержащую

описание множества граждан,

например нашей страны,

то,

скорее всего,

нам

придется

качестве ключа

вы-

брать совокупность полей, отражающих

его

паспортные

данные.

иерархической модели сегменты объединяются

ориентированный

древо-

видный граф.

При

этом полагают,

что

направленные

ребра графа отражают

иерархические связи между сегментами: каждому экземпляру

сегмента,

стояще-

му

выше

по

иерархии

соединенному

данным

типом

сегмента,

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

несколько

(множество) экземпляров

данного

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

типа сегмента.

Тип

сегмента, находящийся

на

более высоком уровне иерархии, называется

ло-

гически

исходным

по

отношению

типам сегментов, соединенным

данным

на-

правленными

иерархическими ребрами, которые

свою

очередь

называются

ло-

гически

подчиненными

по

отношению

этому типу сегмента. Иногда исходные

сегменты называют

сегментами-предками,

подчиненные

сегменты

называют

сегментами-потомками.

Логически

исходный

сегмент

Логически

подчиненные

сегменты

Рис,

3.1.

Пример

иерархических связей между сегментами

На

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

уровне

определяется понятие схемы

БД в

терминологии

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

модели.

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

модель

данных

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

БД

представляет собой

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

отдельных деревьев,

каждое

дерево

рамках модели называется физической базой

данных.

Каждая

физическая

БД

удовлетворяет следующим иерархическим

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

каждой физической

БД

существует

один

корневой

сегмент,

то

есть

сегмент,

которого

нет

логически

исходного

(родительского)

типа сегмента;

каждый

логически

исходный

сегмент может быть связан

произвольным чис-

лом

логически подчиненных сегментов;

каждый логически

подчиненный

сегмент может быть связан только

одним

логически

исходным

(родительским

)

сегментом.

Очень

важно

понимать различие между

сегментом

типом

сегмента

— оно та-

кое же, как

между типом

переменной

самой

переменной:

сегмент является

эк-

земпляром

типа

сегмента.

Например,

у нас

может быть

тип

сегмента

Группа

(Но-

мер,

Староста)

сегменты

этого

типа,

такие

как

(4305,

Петров

Ф. И.) пли

(383,

Кустова

Т.

С.).

Между

экземплярами

сегментов

также

существуют

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

связи.

Рас-

смотрим,

например,

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

граф, представленный

на

рис. 3.2.

Рис. 3.2.

Пример

структуры

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

дерева

Каждый

тип

сегмента

может

иметь

множество

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

ему

экземпля-

ров. Между экземплярами

сегментов

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

связи.

На

рис.

3.3

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

экземпляра

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

дерева

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

струюуры.

рис. 3.3.

Пример

двух

экземпляров

данного

дерева

Глава

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

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

Экземпляры-потомки

одного типа,

связанные

одним

Экземпляром

сегмента-

предка,

называют

«близнецами».

Так,

для

нашего

примера

экземпляры

Ы,

Ь2

ЬЗ

являются

«близнецами»,

но

экземпляр

Ь4

подчинен

другому

экземпляру

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

сегмента,

и он

не

является

«близнецом»

по

отношению

экземп-

лярам

Ы,

1)2

ЬЗ.

Набор всех

экземпляров

сегментов,

подчиненных

одному

эк-

земпляру

корневого сегмента,

называется

физической

записью.

Количество

эк-

земпляров-потомков

может

быть

разным

для

разных

экземпляров

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

сегментов,

поэтому

общем случае

физические

записи

имеют

разную

длину.

Так,

используя

принцип

линейной

записи

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

графов,

пример

на

рис.

3.3

можно

представив

виде

двух

записей:

Как

видно

из

нашего

примера,

физические

записи

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

модели раз*

лнчаются

по

длине

структуре,

Язык

описания

данных

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

модели

рамках

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

модели

выделяют

языковые

средства

описания

данных

(DDL,

Data Definition

Language)

средства

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

данными

(DML,

Data Manipulation

Language).

Каждая

физическая

база

описывается

набором

операторов,

определяющих

как

се

логическую

структуру,

так л

структуру

храпения

БД.

Описание

начинается

оператора

DBD

(Data

Base

Definition):

D3D

Name

< имя

БД>. ACCESS

= <

способ'доступа>

Способ

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

организации

взаимосвязи

физических

запи-

сей.

Определено

способов

доступа:

HSAM

hierarchical sequential access

method

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

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

метод),

ШЗАМ

hierarchical index

sequential

access method

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

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

метод),

ЯОЛА/

hierarchical

direct access

method

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

прямой

метод),

HIDAM

hierarchical

index

direct

access

method

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

нидскспо-гфямой

метод),

INDEX

—

индексный

метод.

идет

описание

наборов

данных,

предназначенных

для

хранения

БД:

DATA

SET DD1

пня

оператора,

определяющего

хранимый

набор

данных>,

DEVICE

устройство

хранения БД>.

IOVFLW

< имя

области

переполнения^

Так как

физические

записи

имеют

разную

длину,

то

при

модификации

данных

запись

может

увеличиться

превысит

исходную

длину

записи

до

модифика-

ции.

этом случае

при

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

методах

хранения

может понадобиться

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

пространство

храпения,

где

будут размешены

дрполпитель-

иые

данные.

Это

пространство

называется

областью

переполнения.

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

модель

данных

После

описания

веси

физической

БД

идет

описание

тппоп

сегментов,

ее

состав-

ляющих,

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

иерархией.

Описание

сегментов

всегда

начинается

описания

корневого

сегмента,

Общая схема

описания

типа

сегмента

такова:

SEGM

NAMF

имя

сегнента>.

BYTES

•=<

размер

байтах>,

FREQ

<средняя

частота

реализаций

сегмента

под

одним

исходные

PARENT

<иня

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

сегнента>

Параметр

FREQ

определяет

сроднее

количество

экземпляров

данного

сегмента,

связанных

одним

экземпляром

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

сегмента.

Для

корневого сег-

мента

это

число

возможных

экземпляров

корневого

сегмента.

Для

корневого

сегмента

параметр

PARENT

равен

(нулю).

для

каждого

сегмента

дается

описание

полей:

FIELD

NAME

{(<цня

поля>

SEQ].{U

И})

<имя

поля>

START

номер

байта,

которого начинается значения поля

BYTES

<размер

поля

байтах>,

TYPE

1 Р |

С}

Признак

SEQ —

задается

для

ключевого

поля,

если

экземпляры

данного

сегмен-

та

физически

упорядочены

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

со

значениями

данного поля.

Параметр

задается,

если

значения

ключевого

поля

уникальны

для

всех экзем-

пляров

данного

сегмсцта,

— в

противном

случае.

Если

ноле

является

кладче-

вым,

то его

описание

задается

круглых

скобках,

противном

случае

имя

поля

задается

без

скобок. Параметр

TYPE

определяет

тип

данных.

Для

ранних

иерар-

хических

моделей

были

определены

только

три

типа

данных;

X —

шестнадцате-

ричпый,

—упакованный

десятичный,

С —

символьный.

Закапчивается

описание

схемы

вызовом

процедуры

генерации:

DBDGEN

—

указывает

на

конец

последовательности

управляющих

операторов

описания

БД;

FINISH

—

устанавливает

ненулевой

код

завершения

при

обнаружении

ошибки;

END

—

конец.

системе

может

быть

несколько

физических

БД

(ФБД),

но

каждая

из

них

огш-

сьшается

отдельно

своим

DBD

ей

присваивается

уникальное

имя. Каждая

ФБД

содержит

только

одни

корневой

сегмент.

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

ФБД

образует

концеп-

туальную

модель

данных.

Внешние

модели

При

работе

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

моделью каждая программа,

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

пли

при-

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

внешнюю

модель,

Внешняя

модель

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

со-

бой

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

поддеревьев

для

физических

баз

данных,

которыми работает

данный

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

Каждый

подграф внешней

модели

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

поряд-

ке

должен

содержать

корнеиои

тип

сегмента

соответствующе]

физической

базы

данных

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

модели.

Глава

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

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

Представление внешней

модели

называется

логической базой данных

опреде-

ляется

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

блоков

связи

данного

приложения

физическими

БД,

входящими

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

схему

БД.

Блок связи

—

РСВ,

program

commu-

nication

bloc

—

описывает

связь

одной физической

БД по

следующим

правилам:

DBD

NAME

имя

логической

БД

(подсхемы)>

ACCESS

LOGICAL

DATA

SET

LOGICAL.

SEGM

NAME

<иня

сегмента

подсхеме>, PARENT

=<имя

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

сегмента

подсхеме:*.

SOURSE

~(Мия

соответствующего сегмента ФБД,

имя

ФБД)

DBDGEN

FINISH

END

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

.блоков

РСВ

образует полное внешнее

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

данного при-

ложения,

называемое

«блоком

спецификации

программ»

(PSB,

program

specifi-

cation

block).

Рассмотрим пример иерархической

БД.

Наша

организация

занимается

производством

продажей

компьютеров,

рам-

ках

производства

мы

комплектуем компьютеры

из

готовых деталей

по

индиви-

дуальным заказам.

У лас

существует

несколько

базовых

моделей,

которые

мы

продаем

без

предварительных

заказов

по

наличию

на

складе.

организации

су-

ществуют

несколько

филиалов

(рис. 3.4)

несколько

складов,

на

которых хра-

нятся комплектующие.

Нам

необходимо

вести

учет

продаваемой продукции.

Рис.

3.4.

Физическая

БД

«Филиалы»

Какие задачи

нам

надо

решать

ходе

разработки

приложения?

При

приеме

заказа

мы

должны

выяснить,

какую модель заказывает

заказчик:

типичную

или

индивидуальную

комплектацию.

Если заказывается

типичная

модель,

то

выясняется, какая

модель

есть

ли

она

наличии, если

модель

есть,

то

надо уменьшить

количество

компьюте-

ров

данной

модели

данном

филиале

па

покупаемое

количество.

На

этом

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

модель

данных

будем

считать заказ

выполненным,

однако

при

оформлении заказа может

по-

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

спецификации

покупаемого изделия.

Если заказывается

индивидуальная

модель,

то

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

весь

состав

новой

модели.

Для

того

чтобы

можно

было

бы

принимать

заказы

на

индивидуальные

модели,

нам

понадобится

информация

наличие

конкретных

деталей

на

складе,

этом

случае

нам

необходимо

второе

дерево

—

Склады

(см. рис. 3.5).

Язык манипулирования данными

иерархических базах данных

Для

доступа

базе

данных

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

должна быть

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

специ-

альная среда

окружения,

поддерж!тающая

явном

виде

имеющиеся

навигаци-

онные

операции.

Для

этого

ней

должны

храниться;

шаблоны

всех

записей

логических

баз

данных,

доступных

пользователю;

указатели

па

текущий

экземпляр

сегмента

данного

типа

— для

всех

типов

сегментов.

Язык манипулирования

данными

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

модели

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

в яв-

ном

виде

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

операции.

Эти

операции

связаны

перемещением

ука-

зателя, который определяет

текущий

экземпляр

конкретного

сегмента.

Все

операторы

языке

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

данными

можно

разделить

на 3

груп-

пы.

Первую группу составляют операторы

поиска

данных,

Операторы поиска данных

Синтаксис;

GET

UNIQUE

<имя

сегмента>

WHERE

<список

поиска*;

Глава

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

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

список

поиска

состоит

из

последовательности

условий вида:

<иня

сегмента>.<имя

попя>ОС

<constant

или

пня

другого поля

данного

сегмента

или

пня

переменной>:

ОС —

операция

сравнения;

условия могут быть

соединены

логическими

операциями

И и ИЛИ {& ,

V}.

Назначение:

Получить

единственное

значение.

Пример:

Найти

типовую

модель

стоимостью

не

более

$600,

которая существует

не

менее

чем л 10

экземплярах.

GET

UNIQUE

ТИПОВЫЕ

МОДЕЛИ

WHERE

Типовые

модели.Стоимость

$600

AND

Типовые

подели.Количество

на

складе

Данная

команда

всегда

ищет

начала

БД и

останавливается,

найдя

первый

эк-

земпляр

сегмента,

удовлетворяющий

условиям поиска.

Синтаксис:

GET

<имя

сегмента>

WHERE

«список

аргументов

поиска>

Назначение:

Получить

следующий экземпляр

сегмента

для тех

же

условии.

Пример:

Напечатать

полный

список

заказов

стоимостью

не

менее

$500.

GET

UNIQUE

ИНДИВИДУАЛЬНЫЕ

МОДЕЛИ

WHERE

Индивидуальные

модели.Стоимость

$500

WHILE

NOT

TAIL

Спока

не

коне^

поиска)

заказа,

Стоимость,

Количество

GET

ИНДИВИДУАЛЬНЫЕ МОДЕЛИ

END

Синтаксис:

GET

<иня

сегнента>

WITHIN

PARENT

[

where

<дополн.усповия>.1

Назначение:

Получить

для

того

же

исходного.

Пример:

Получить

перечень

винчестеров,

шгеюншхся

на

скдаде

номер

количестве

не

менее

10 с

объемом

Гбайт.

GET

UNIQUE

СКЛАД WHERE

Склад.Номер

GET

ИЗДЕЛИЕ

WITHIN

PARENT

WHCRE

Изделие'.Наименование

"Винчестер"

GET

ХАРАКТЕРИСТИКИ

WITHIN'PARENT

WHERE

ХАРАКТЕРИСТИКИ.Параметр

= 10 AND

ХАРАКТЕРИСТИКИ.Единицы

Измерения

ГО AND

ХАРАКТЕРИСТИКИ.Величина

> 10

While

Not

Fall

(пока

поиск

не

завершен)

Get

WUh-in

Parent

end

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

Операторы

поиска данных

возможностью

модификации

Найти

удержать

единственны]!

экземпляр сегмента.

Эта

операция

подобна

nepBoii

операции

поиска

GET

UNIQUE,

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

отличием

этой

операции

является

то, что

после

выполнения

этой

операции

над

найденным

экземпля-

ром

сегмента

допустимы

операции

модификации

(изменения)

данных.

Синтаксис:

GET

HOLD

UNIQUE

<имя

сегнента>

WHERE

<список

поиска>

Hafmi

удержать

темп.жс

условиями

поиска.

Аналогично

опе-

рации

4 эта

операция

дублирует вторую

операции

поиска

GET

возмож-

ностью

выполнения

последующей

модификации

данных.

Синтаксис:

GET

HOLD NEXT [WHERE

"дополнительные

условия>]

Получить

удержать

для

того

же

родителя.

Эта

операция явля-

ется

аналогом

операции

поиска

3, но

разрешает

выполнение

операций

моди-

фикации

данных

после

себя.

Синтаксис:

GET

HOLD NEXT WITHIN PARENT

[

where

<дополн.условия>]

Операторы

модификации

данных

Удалить

Это

первая

из

трех

операции

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

Синтаксис:

DELETE

Эта

команда

не

имеет

параметров.

Почему?

Потому

что

операции

модифика-

ции

действуют

на

экземпляр сегмента,

найденный

командами

поиска

удер-

жанием,

Л он

всегда

сдинстиеиный

текущий

найденный

удерживаемый

для

модификации

экземпляр

конкретного

сегмента.

Поэтому,

при

выполнении

команды

удаления

будет

удален

именно

этот

экземпляр

сегмента.

Обновить

Синтаксис;

UPDATE

Как

же

происходит

обновление,

если

мы п в

этой команде

не

задаем

никаких

параметров.

СУБД

берет

данные

из

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

где

шаблонах

записей

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

nnyipeininx

переменных

находятся

зна-

чения

полей каждого

сегмента

внешней

модели,

которой работает

данный

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

Именно

этими

значениями

обновляется

текущий

экземпляр

сегмента.

Значит, перед

тем как

выполнить

операции

модификации

UPDATE,

необходимо

присвоить

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

переменным

новые

значения.

Ввести

новый

экземпляр

сегмента.

INSE'RT

<иня

сегиента>

Глава

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

модели

данных

Эта

команда

позволяет

ввести

новый

экземпляр

сегмента,

имя

которого

оп-

ределено

параметре

команды.

Если

мы

вводим

данные

сегмент,

который

является

подчиненным

некоторому

родительскому

экземпляру

сегмента,

то

он

будет

внесен

в БД

физически

подключен

тому

экземпляру

родитель-

ского

сегмента,

который

данный

момент

является

текущим.

Как

видим,

набор

операций

поиска

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

данными

иерархиче-

ской

БД

невелик,

но он

вполне

достаточен

для

получения

доступа

любому

эк-

земпляру

любого

сегмента

БД.

Однако

следует

отметить,

что

способ

доступа,

который

применяется

данной

модели,

связан

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

перемеще-

нием

от

одного

экземпляра

сегмента

другому.

Такой

способ

напоминает

дви-

жение

летательного

аппарата

или

корабля

по

заданным

координатам

называ-

ется

навигационным.

Сетевая

модель

данных

Стандарт сетевой модели

впервые

был

определен

1975 году

организацией

CODASYL

(Conference

Data

System

Languages),

которая определила базовые

понятия модели

формальный язык

описания.

Базовыми объектами модели являются:

элемент

данных;

агрегат данных;

запись;

набор

данных.

Элемент

данных

— то же, что и в

иерархической модели,

то

есть

минимальная

информационная

единица, доступная пользователю

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

СУБД.

Агрегат

данных

соответствует следующему

уровню

обобщения

модели.

В мо-

дели

определены

агрегаты двух типов: агрегат

типа

вектор

агрегат типа

повто-

ряющаяся группа.

Агрегат

данных

имеет имя,

и в

системе

допустимо

обращение

агрегату

по

име-

ни.

Агрегат

типа'

вектор

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

линейному

набору

элементов

данных.

Например, агрегат

Адрес

может быть

представлен

следующим

образом:

Адрес

Город

Улица

дом

киартнра

Агрегат

типа повторяющаяся группа

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

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

векторов дан-

ных.

Например,

агрегат

Зарплата

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

типу

повторяющаяся группа

чис-

лом

повторений

12.

Зарплата

Месяц

Сумма