Назад
Сетевая
модель
данных
41
Записью
называется
совокупность
агрегатов
или
элементов
данных,
модели-
рующая
некоторый
класс объектов
реального
мира.
Понятие
записи
соответ-
ствует
понятию
«сегмент»
в
иерархической
модели.
Для
записи,
так же как и
для
сегмента,
вводятся
понятия
типа
записи
п
экземпляра
записи.
Следующим
базовым
понятием
в
сетевой модели является
понятие
«Набор».
Набором называется
двухуровневый
граф,
связывающий
отношением
«однп-ко-
многим»
два
типа
записи.
Набор
фактически
отражает иерархическую
связь
между двумя
типами
записей.
Родительский
тип
записи
в
данном
наборе
называется
владельцем
набора,
а до-
черний
тип'записи
членом
того
же
набора.
Для
любых двух типов
записей
может
быть
задано
любое
количество
наборов,
которые
их
связывают.
Фактически
наличие
подобных
возможностей
позволяет
промоделировать
отношение
«многие-ко-многпм»
между двумя объектами
ре-
ального
мира,
что
выгодно отличает
сетевую
модель
от
иерархической.
В
рам-
ках
набора
-возможен
последовательный
просмотр экземпляров
членов
набора,
связанных-с
одним
экземпляром владельца набора.
Между двумя
типами
записей
может быть
определено
любое
количество
набо-
ров;
например,
можно
построить
два
взаимосвязанных
набора.
Существенным
ограничением
набора
является
то, что
один
и
тот же тип
записи
не
может быть
одновременно
владельцем
и
членом
набора.
В
качестве
примера
рассмотрим
таблицу,
на
основе которой
организуем
два на-
бора
и
определим
связь
между
ними;
Преподаватель
Ищи
ю
и
Мшшоо
Карпопа
Карп
она
Кар
попа
Смирно»
См up]
юн
Группа
4306
4307
4307
4309
84305
4306
4309
День
недели
Понедельник
Понедельник
Вторник
Вторник
Вторник
Вторник
Вторник
пары
1
2
2
4
1
3
4
Аудитория
22-13
22-13
22-14
22-14
22-14
23-07
23-07
Дисциплина
кид
кид
БЗ ч ЭС
БЗ
и
ЭС
БД
ГВП
ГВП
42
Глава
3.
Теоретико-графовые
модели
данных
Экземпляров
набора
Ведет
занятия
будет
3 (по
числу
преподавателей),
экзем-
пляров
набора
Занимается
у
будет
4 (по
числу
групп).
На
рис.
3.6
представлены
взаимосвязи
экземпляров
данных
наборов.
Рис.
3.6. Пример взаимосвязи
экземпляров
двух
наборов
Среди
всех
наборов
выделяют
специальный
тин
набора,
называемый
«Сингу-
лярным
набором»,
владельцем
которого
формально
определена
нем
система.
Сингулярный
набор
изображается
в
виде
входящей
стрелки,
которая
нМсст
соб-
ственно
имя
набора
л имя
члени
набора,
но
у
которой
не
определен
тин
записи
«Владелец
набора».
Например,
сингулярный
набор
М.
Сингулярные
наборы
позволяют
обеспечить
доступ
к
экземплярам
отдельных
типов
данных,
поэтому
если
в
задаче
алгоритм
обработки
информации
предпо-
лагает
обеспечение
произвольного
доступа
к
некоторому
типу
записи,
то для
поддержки
этой
возможности
необходимо
ввести
соответствующий сингуляр-
ный
набор.
В
общем случае сетевая база
данных
представляет
совокупность
взаимосвязан-
ных
наборов,
которые
образуют
на
концептуальном
уровне
некоторый
граф.
Язык описания данных
в
сетевой
модели
Язык
описания
данных
в
сетевой
модели
имеет
несколько
разделов;
Q
описание
базы
данных
-
области
размещения;
Q
описания
записей
элементов
п
агрегатов (каждого
в
отдельности);
Q
описания
наборов
(каждого
в
отдельности).
SCHEMA
IS
<Иня
БД>.
AREA
NAME
IS
<Иня
физической
области>.
RECORD
NAME
IS
<Иня
записи
(уникальное}>
Для
каждой
записи
определяется
способ
размещения
экземпляров
записи
дан-
ного
типа:
LOCATION
MODE
IS
{DIRECT
(напрямую)
(
CALC
<Иня
программы*
USING
<[Слисок
пер,>]
Сетевая
модель данных
43
DUPLICATE
ARE
[NOT]
ALLOWED
VIA
<Имя
набора>
SL-Т
(рядом
с
записями
владельца)
SYSTEM
(решать
будет
система)}
Каждый
тип
записи
должен
быть
приписан
к
некоторой
физической
области
размещения:
WITHIN
<Имя
области
размещения>
AREA
После
описания
записи
в
целом
идет
описание
внутренней
структуры:
<Имя
уровня>
<Имя
данного>
<Шаблон>
<Тип>
Номер уровня определяет уровень
вложенности
при
описании
элементов
и
агре-
гатов
данных.
Первый
уровень
сама
запись.
Поэтому
элементы
или
агрегаты
данных
имеют
уровень
начиная
со
второго.
Если
данное
соответствует
агрегату,
то
любая
его
составляющая добавляет
одни
уровень
вложенности.
Если агрегат является
вектором,
то он
описывается
как
<Номе|э
уровня>
<Иня
агрегата>.<Нонер
уровня>
<Иия
1-й
сост,>
а
если
повторяющейся группой,
то
следующим
образом:
<Номер
уровня>
<Иня
агрегата>,OCCURS
Ф-
TIMES
где N
среднее
количество элементов
в
группе.
Описание
набора
и
порядка
включения
членов
в
него
выглядит
следующим
об-
разом:
SET
NAME
IS
<Иня
наборам
OWNER
IS
<<Имя
владельца>
|
SYSTEM).
Далее
указывается
порядок
включения
новых
экземпляров'члена
данного
набо-
ра
в
экземпляр
набора:
ORDER PERMANENT
INSERTION
IS
{SORTED
|
NEXT
j
PREV
|
LAST
|
FIRST}
После
этого
описывается
член набора
с
указанием
способа
включения
н
способа
исключения
экземпляра
-
члена
набора
из
экземпляра набора.
MEMBER
IS
<Иня
члена
набора>
{AUTOMATIC
|
MANUAL}
{MANDATORY
|
OPTIONAL}
KEY
IS
(ACCENDING
|
DESCENDING)
<Имя
элемента
данных*
При
автоматическом
включении
каждый
новый
экземпляр
члена
набора
авто-
матически
попадает
в
текущий
экземпляр
набора
в
соответствии
с
заданным
ра-
нее
порядком
включения.
При
ручном
способе
экземпляр
члена
набора
сначала
попадает
в
БД,
а
только потом
командой
CONNECT
может быть включен
в
конкрет-
ный
экземпляр
набора.
Если
задан способ
исключения
MANDATORY,
то
экземпляр
записи,
исключаемый
из
набора,
автоматически
исключается
и из
базы
данных.
Иначе просто разрыва-
ются
связи.
Внешняя'модель
при
сетевой
организации
данных
поддерживается
путем описа-
ния
части
общего
связного
графа.
44
Глава
3,
Теоретико-графовые
модели данных
Язык
манипулирования
данными
в
сетевой
модели
Все
операции
манипулирования
данными
в
сетевой модели делятся
на
навига-
ционные
операции
и
операций
модификации.
Навигационные
операции осуществляют
перемещение
по БД
путем
прохожде-
ния
по
связям,
которые
поддерживаются
в
схеме
БД. В
этом случае результатом
является новый единичный
объект,
который
получает
статус
текущего
объекта.
Операции
модификации
осуществляют
как
добавление новых экземпляров
от-
дельных
типов записей,
так и
экземпляров новых наборов, удаление экземпля-
ров
записей
и
наборов, модификацию отдельных составляющих внутри конкрет-
ных
экземпляров
записей,
Средства
модификации
данных сведены
в
табл.
3.1:
Таблица
3.1.
Операторы
Манипулирования
данными
в
сетевой модели
Операция
READY
FINISH
FIND
GET
STORE
CONNECT
DISCONNECT
MODIFY
ERASE
Назначение
Обеспечение
доступа
данного
процесса
или
пользователя
к
БД
(сходна
по
смыслу
с
операцией
открытия
файла)
Окончание
работы
с БД
Группа
операции,
устанавливающих
указатель
найденного
объекта
на
текущий
объект
Передача
найденного
объекта
в
рабочую
область.
Допустима
только
после
FIND
Помещение
в БД
записи,
сформированной
п
рабочей
области
Включение
текущем
записи
в
текущий
экземпляр
набора
Исключение
текущей
записи
из
текущего
экземпляра
набора
Обновление
текущей
записи
данными
из
рабочей
области
пользователя
Удаление
экземпляра
текущей
записи
В
рабочей области пользователя хранятся
шаблоны
записей,
программные пере-
менные
и три
типа указателей текущего
состояния:
Q
текущая запись процесса (код
или
ключ последней записи,
с
которой работа-
ла
данная
программа);
Q
текущая запись типа
записи
(для
каждого
типа
записи ключ последней запи-
си,
с
которой работала программа);
Q
текущая запись типа набор
(для
каждого набора
с
владельцем
Т1 и
членом
Т2
указывается,
Т1 пли Т2
были
последней
обрабатываемой
записью).
На
рис.
3.7
представлена
концептуальная модель
торгово-посредпаческой
орга-
низации.
Сетевая
модель
данных
45
Рис.
3.7.
Схема
БД
«Торговая фирма»
При
необходимости возможно
описание
элементов
данных,
которые
не
принад-
лежат
непосредственно
данной
записи,
по
при
ее
обработке часто
используются.
Для
этого
используется
тип
VIRTUAL
с
обязательным
указанием
источника
дан-
ного
элемента
данных.
RECORD
Цены
02
Цена
TYPE
REAL
02
Товар VIRTUAL
SOURCE
IS
Товары.НаименованиеТовара
OF
OWNER
OF
Товар-Цены
SET
Наиболее
интересна
операция
поиска
(FIND),
так как
именно
она
отражает суть
навигационных
методов, применяемых
в
сетевой
модели.
Всего
существует
семь
типов
операций
поиска:
1.
По
ключу
(запись
должна
быть
описана
через
CALC
USING
...)'
FIND
<Иня
записи*
RECORD
BY
CALC
KEY
<Имя
параметра*
2.
Последовательный
просмотр
записей
данного
типа:
FIND DUPLICATE
<Имя
записи>
RECORD
BY
CALC
KEY
3.
Найти
владельца
текущего
экземпляра набора;
FIND
OWNER
OF
CURRENT
<Иня набора>
SET
4.
Последовательный
просмотр
записей-членов
текущего экземпляра
набора:
FIND
(FIRST
I
NEXT)
<Имя
записи>
RECORD
IN
CURRENT
<Иня
набора*
SET
46
Глава
3.
Теоретике-графовые
модели данных
5.
Просмотр
записей—членов
экземпляра
набора,
специфицированных
рядом
нолей;
FIND
[DUPLICATE]
<Иия
записи>
RECORD
IN
CURRENT <Иия
набора>
SET
USING
<Список
полей>
6.
Сделать
текущей
записью
процесса
текущий
экземпляр
набора:
FIND
CURRENT
OF
<Иня
набора^
SET
7.
Установить
текущую
запись
процесса:
FIND
CURRENT
OF
<Имя
записи*
RECORD
Например,
алгоритм
и
программа печати заказов, сделанных
Петровым,
будут
выглядеть
так:
ФИО
=
"Петров"
FIND
Люди
RECORD
BY
CALC
KEY
FIND FIRST
Заказы
RECORD
IN
CURRENT
Лйди-Заказы
SET
WHILE
NOT
FAIL
DO-
FIND
OWNER
OF
CURRENT
,
Товары-Заказы
SET
GET
Товары
PRINT
НаимТовара
FIND NEXT
Заказы
RECORD
IN
CURRENT
Люди-Заказы
SET
END
ГЛАВА
4
Реляционная
модель
данных
Основные
определения
Появление
теоретико-множественных
моделей
в
системах
баз
данных было пред
определено
настоятельной
потребностью пользователей
п
переходе
от
работы
с
элементами данных,
как это
делается
и
графовых
моделях,
к
работе
с
некоторы-
ми
макрообъсктамн.
Основной
моделью
в
этом классе
является
реляционная
модель
данных.
Простота
и
наглядность
модели
для
пользователей-непрограм-
мистов,
с
одной стороны,
и
серьезное
теоретическое
обоснование,
с
другой сто-
роны,
определили
большую популярность
;УГОН
модели.
Кроме того,
развитие
формального аппарата
представления
и
манипулирования
данными
в
рамках
реляционной
модели
сделали
се
наиболее
перспективной
для
использования
в
системах
представления
знаний,
что
обеспечивает
качественно
иной
подход
к
обработке
данных
в
больших
информационных
системах.
Теоретической
основой
этой
модели
стала
теория
отношений,
основу
которой
заложили
два
логика
американец
Чарльз
Содерс
Пире
(1839-1914)
и
немец
Эрнст
Шредер
(18-11-1902).
В
руководствах
по
теории
отношении
было
показа-'
по,
что
множество
отношений
замкнуто
относительно
некоторых
специальных
операций,
то.есть
образует вместе
с
этими
операциями
абстрактную алгебру.
Это
важнейшее
свойство
отношений
было
использовано
в
реляционной
модели
для
разработки
языка
манипулирования
данными,
связанного
с
исходной
алгеб-
рой,
Американский
математик
Э.
Ф.
Кодд
в
1070
году
впервые
сформулировал
основные
понятия
и
ограничения
реляционной
модели,
ограничив
набор
опера-
ций
в
ней
семью
основными
п
одной
дополнительной
операцией.
Предложения
Кодда
были
настолько
эффективны
для
систем
баз
данных,
что за эту
модель
он
был
удостоен
престижной
премии
Тьюринга
в
области
теоретических
основ
вы-
числительной
техники.
Основной структурой
данных
в
модели
является
отношение,
именно
поэтому
модель
получила
название
реляционной
т
английского
relation
отношение).
N-арным
отношением
R
называют
подмножество
декартова
произведения
D^D-jx
...
xD
n
множеств
D,,
Do
Ц, (п
£
1),
необязательно
различных.
Исход-
ные
множества
D,,
П
а
,
....
D
n
называют
в
модели
доменами.
48
Глава
4.
Реляционная
модель
данных
R
с
DjxD2X...xD,,,
где
DjxD
2
x
...xD
r
,
полное
декартово
произведение.
Полное
декартово
произведение
это
набор
всевозможных
сочетаний
из
п
эле-
ментов каждое,
где
каждый
элемент
берется
из
своего
домена.
Например,
имеем
три
домена:
DJ
содержит
три
фамилии,
D
2
набор
из
двух
учебных
дисциплин
и
D
3
набор
из
трех
оценок.
Допустим,
содержимое доменов
следующее:
Q
DI
"
{Иванов,
Крылов,
Степанов};
U
D2
=
{Теория
автоматов,
Базы
данных};
Q
D
3
-
{3,
4, 5}
Тогда полное декартово
произведение
содержит набор
из 18
троек,
где
первый
элемент
это
одна
из
фамилий, второй
это
название
одной
из
учебных дис-
циплин,
а
третий
одна
из
оценок.
<Иванов,Теория
автоматов.3>:
«Иванов.Теория
автоматов,4>;
<Ивано8,Теория
автоматов.5>
<Крылов,Теория
автоматов,3>:
<Крылов.Теория
автоматов.4>:
<Крылов.Теория
автоматов,5>;
<Степаноз.Теория
автоматов.3>;
<Степанов.Теория
автоматов.4>:
«Степанов.Теория
автоматов,5>:
<Иванов.Базы
данных,3>:
<Иванов,Базы
данных.4>;
<Иеанов.Базы
данных.5>:
<Крылов,Базы
данных.3>:
<Крылов.Базы
данных.4>:
«Крылов.Базы
данных.5>:
<Степанов'.Базы
данных,3>;
<Степанов,Базы
данных.4>:
<Степанов,Базы
данных.5>;
Отношение
R
моделирует реальную
ситуацию
и
оно
может
содержать,
допус-
тим,
только
5
строк, которые соответствуют результатам
сессии
(Крылов экза-
мен
по
«Базам
данных»
еще не
сдавал);
<Иванов.Теория
автоматов,4>:
<Крылов,Теория
автоматов.5>;
«Степанов.Теория
автоматов,5>:
<Иванов.Базы
данных.3>;
-Степанов.Базы
данных,4>;
Отношение
имеет простую графическую
интерпретацию,
оно
может быть пред-
ставлено
в
виде
таблицы,
столбцы которой соответствуют вхождениям
доменов
в
отношение,
а
строки
-
наборам
из п
значений,
взятых
из
исходных доменов,
которые
расположены
в
строго
определенном
порядке
в
соответствии
с
заголов-
ком. Такие наборы
из п
значений
часто
называют
п-ками.
R
~
Фамилия
И
пап
он
Иванов
Крылов
Степанов
Степанов
Дисциплина
Теория
автоматов
Базы
данных
Теория
автоматов
Теория
автоматов
Базы
данных
Оценка
4
3
5
5
4
Данная
таблица обладает рядом
специфических
свойств;
Основные
определения
49
1.
В
таблице
нет
двух
одинаковых
строк,
2.
Таблица
имеет столбцы, соответствующие атрибутам отношения.
3.
Каждый
атрибут
в
отношении
имеет
уникальное
имя.
4.
Порядок
строк
в
таблице
произвольный.
Вхождение
домена
в
отношение
принято
называть
атрибутом.
Строки
отноше-
ния
называются
кортежами.
Количество атрибутов
и
отношении
называется
степенью,
или
рангом,
отно-
шения.
Следует
заметить,
что в
отношении
не
может быть одинаковых кортежей,
это
следует
из
математической модели: отношение
это
подмножество декартова
произведения,
а в
декартовом
произведении
все
и-ки
различны.
В
соответствии
со
свойствами
отношений
два
отношения,
отличающиеся только
порядком
строк
или
порядком
столбцов,
будут интерпретироваться
в
рамках
ре-
ляционной
модели
как
одинаковые,
то
есть отношение
R и
отношение
RI,
изо-
браженное
далее,
одинаковы
с
точки
зрения
реляционной модели данных.
R1
Дисциплина
Теория
автоматов
Теория
автоматов
Теория
автоматов
Базы
данных
Базы
данных
Фамилия
Крылов
Степанов
Иванов
Иванов
Степанов
Оценка
5
5
4
3
4
Любое
отношение
является
динамической
моделью некоторого реального объ-
екта
внешнего
мира.
Поэтому вводится понятие экземпляра отношения, которое
отражает
состояние
данного
объекта
в
текущий
момент
времени,
и
понятие схе-
мы
отношения,
которая определяет структуру
отношения.
Схемой
отношения
R
называется перечень
имен
атрибутов данного отношения
с
указанием
домена,
к
которому
они
относятся;
5л
«
(А|,
А
2
,
Аи),
А, с
D,.
Если
атрибуты
принимают
значения
из
одного
и
того
же
домена,
то они
называ-
ются
^-сравнимыми,
где 9 -
множество
допустимых
операций
сравнения,
задан-
ных
для
данного
домена.
Например,
если домен содержит числовые данные
, то
для
него допустимы
все
операции
сравнения,
тогда
0
~
{=,
<>,>=,<",<,>}.
Одна-
ко
и для
доменов,
содержащих
символьные
данные,
могут быть заданы
не
толь-
ко
операции
сравнения
по
равенству
и
неравенству
значений.
Если
для
данного
домена
задано
лексикографическое
упорядочение,
то он
имеет
также
полный
спектр
операций сравнения.
Схемы
двух
отношений
называются
эквивалентными,
если
они
имеют
одинако-
вую
степень
и
возможно
такое
упорядочение
имен
атрибутов
в
схемах,
что
на
одинаковых
местах
будут
находиться
сравнимые
атрибуты,
то
есть
атрибуты,
принимающие
значения
из
одного
димепа.
50
Глава
4.
Реляционная модель данных
SRI
"
1(
АЗ,
...,
А„)
-
схема отношения
R
t
.
SRS
"
(Вц,
В|2
В
[п
)
схема
отношения
R
2
после
упорядочения
имен
атрибутов.
Тогда
Как
уже
говорилось ранее, реляционная модель представляет базу данных
в
цпде
множества взаимосвязанных
отношений.
В
отличие
от
теоретико-графовых
лю-
делей
в
реляционной модели
связи
между
отношениями
поддерживаются неяв-
ным
образом.
Какие
же
связи
между
отношениями
поддерживаются
в
реляци-
онной
модели?
В
этой
модели,
так же как и в
остальных,
поддерживаются
иерархические
связи между
отношениями.
В
каждой связи одно
отношение
мо-
жет
выступать
как
основное;
а
другое отношение выступает
в
роля
подчиненно-
го. Это
означает,
что
один
кортеж
основного
отношения
может
быть
связан
с
несколькими
кортежами
подчиненного
отношения.
Для
поддержки
этих связей
оба
отношения
должны
содержать
наборы
атрибутов»
по
которым
они
связа-
ны.
В
основном
отношении
это
первичный ключ отношения
(PRIMARY
KEY),
который
однозначно
определяет
кортеж основного
отношения.
В
подчиненном
отношении
для
моделирования
связи должен присутствовать
набор
атрибутов,
соответствующий
первичному
ключу
основного
отношения.
Однако здесь этот
набор
атрибутов
уже
является вторичным ключом,
то
есть
он
определяет мно-
жество
кортежей подчиненного
отношения,
которые связаны
с
единственным
кортежем
основного
отношения.
Данный
набор
атрибутов
в
подчиненном
отно-
шении
принято называть
внешним
ключом (FOREIGN KEY).
Например, рассмотрим ситуацию, когда
надо
описать карьеру
некоторого
инди-
видуума. Каждый человек
в
своей трудовой
деятельности
сменяет несколько мест
работы
в
разных организациях,
где
он
работает
в
разных
должностях. Тогда
мы
должны создать
два
отношения;
одно
для
моделирования
всех
работающих
лю-
дей,
а
другое
для
моделирования записей
в их
трудовых
книжках,
если
для нас
важно
не
только отследить
переход
работника
из
одной
организации
в
другую,
но
п
прохождение
его по
служебной
лестнице
в
рамках
одной
организации
(рис,
4.1).,
Рис, 4.1; Связь
между
основным
и
подчиненным отношениями
I
J
KIMAKY
К1:У
опюшения
Сотрудник
атрибут
Паспорт
являс-п
л
FOREIGN
KEY
f
i
м
отнищсшш
«карьера».