Раздел 6. Основы теории РБД
13.
Глава 13. Создание РБД
13.1.
Обеспечение целостности
Будем придерживаться порядка изложения в соответствии с этапами проектирования (рис 2.5
).
В качестве принципов проектирования можно использовать
:
1) максимум локализации данных и сокращение количества пересылаемых по кратчайшему пути данных: рекомендуется иметь до 90 процентов ее в
локальной БД (ЛБД) узла и около 10 процентов - в ЛБД других узлов;
2) локальность расположения данных следует определять по отношению к наибольшему числу приложений.
В качестве критериев проектирования
РБД могут быть
:
1) минимум объема пересылаемых данных и сообщений;
2) минимум стоимости трафика;
3) минимум общего времени, необходимого для обслуживания запросов к БД.
В рассмотрении РБД возможно выделить два случая работы: с одним приложением и с системой приложений. Возможно нисходящее и восходящее проектирование.
Восходящее проектирование используется обычно в случае, когда РБД создается из уже работающих, локальных БД. Эти особенности освещены в проблеме интеграции однородных и неоднородных БД.
Восходящее проектирование может быть этапом нисходящего проектирования, которое в силу того, что оно применяется гораздо чаще, обсудим подробнее.
В общем случае целостность данных может нарушаться по следующим основным причинам:
1) ошибки в создании структуры локальных БД и их заполнении;
2) просчеты в построении структуры РБД (процедуры фрагментации и локализации);
3) системные ошибки в программном обеспечении взаимодействия локальных БД (одновременный доступ);
4) аварийная ситуация (неисправность технических средств) и восстановление РБД.
Первая позиция подробно освещена ранее и здесь рассматриваться не будет. Специфика остальных трех позиций для РБД может быть зафиксирована в виде совокупности проблем (рис. 13.1).
Четвертая позиция исследуется в последующих главах, вторую и третью - подробно изучим здесь.
Иногда к нарушению целостности относят умышленное искажение информации, т.е. несанкционирванный доступ. Эти вопросы будут рассмотрены позднее.
13.2.
Фрагментация и локализация
Напомним (рис. 2.5),
что общая этапность проектирования РБД напоминает этапность при создании централизованной БД и отличие имеет место лишь в этапах
фрагментации (расчленения) и
локализации (размещения).
Основными факторами, определяющими методику расчленения, являются допустимый размер каждого раздела; модели и частоты использования приложений; структурная совместимость; факторы производительности БД. Связь между разделом БД и приложениями характеризуется идентификатором типа приложения, идентификатором узла сети, частотой использования приложения и его моделью.
Сложность реализации этапа размещения БД определяется многовариантностью. Поэтому на практике рекомендуется в первую очередь рассмотреть возможность использования определенных допущений, упрощающих функции СУРБД (например, допустимость временного рассогласования БД, осуществление процедуры обновления БД из одного узла).
Фрагментация
, как отмечалось ранее, может быть горизонтальной и вертикальной.
Фрагмент может быть определен последовательностью операции селекции и проекции реляционной алгебры (раздел 2). При декомпозиции следует выполнить ряд условий.
Полнота. Все данные глобального отношения R должны быть отображены в его фрагменты.
Восстанавливаемость. Всегда возможно восстановить глобальное отношение из фрагментов.
Непересечение. Целесообразно, чтобы фрагменты не пересекались (дублирование производится на этапе локализации).
При
горизонтальной фрагментации с помощью селекции любое подмножество кортежей объединено общностью свойств, определяемых описанием предметной области.
Вертикальная фрагментация с помощью проекции делит глобальное отношение (схему R) по приложениям (или по географическому признаку).
Фрагментация корректна, если любой атрибут глобального отношения (схемы R) присутствует в каком-либо подмножестве атрибутов и глобальное отношение восстанавливается естественным соединением.
Фрагментация совместно с локализацией (рис.13.2) определяют в конечном итоге быстроту реакции РБД на запрос.
Обозначим узлы через j (j = 1, J), а приложения - через k (k = 1, K). Если имеется отношение r со схемой R, то в узле j имеется отношение-фрагмент Rj
. Если в узле j имеется к тому же копия фрагмента Ri
, i = 1, J, то обозначим ее через Rij
. Тогда схема фрагментации и локализации может быть представлена в виде, показанном на рис. 13.2.
Иными словами, при фрагментации декомпозиция глобального отношения должна обладать свойством соединения без потерь.
Возможна смешанная фрагментация, которой соответствует совокупность операций селекции и проекции
,
где R = {alj
, ..., amj
}, m - число записей в горизонтальном фрагменте.
После фрагментации осуществляют локализацию. В качестве критерия локализации
удобно использовать влияние локализации (размещения) на задачу оптимизации запроса при известной его структуре. Для этого необходимы моделирование и оптимизация всех приложений для любого варианта размещения.
Воспользуемся обозначениями, введенными в данной главе. Пусть fkj
- частота активизации приложения k в узле j, rki
- число ссылок поиска приложения k во фрагменте i, uki
- число ссылок обновления данных приложения k во фрагменте i, nki
= rki
+ uki
.
Задача размещения имеет две основные разновидности: без использования и с использованием копий.
Рассмотрим первую разновидность. Здесь возможны эвристические и строго математические алгоритмы.
Обсудим сначала один из эвристических алгоритмов размещения, состоящий из нескольких шагов.
Шаг 1. Используем метод «наиболее подходящего» размещения: фрагмент Ri размещается в узле j, где число ссылок на него максимально. Число локальных ссылок
, (13.1)
Из выражения (13.1) определяется узел j*, где следует разместить фрагмент.
Шаг 2. Применим метод выделения «всех выгодных узлов» для избыточного размещения: помещаем Ri во всех узлах, где стоимость ссылок приложений, осуществляющих поиск, больше стоимости ссылок приложений, обновляющих данные во фрагменте Ri в любом узле: Bij>0 или
, (13.2)
где C - отношение стоимости обновления и поиска.
Шаг 3. Используем метод "добавочного копирования". Пусть di
- степень избыточностиRi
; Fi
- выгодность размещения копии в любом узле РБД и b(di
) = (1 - 2l-d)Fi
. Модифицируя выражение (13.2), получим
. (13.3)
Учтем вертикальную фрагментацию.
Пусть схема Ri
декомпозирована на Rs
и Rt
, где s и t - узлы.
Используем следующие рассуждения.
Если существует два приложения Пs
и Пt
, которые используют только атрибуты Rs
и Rt
, т.е. обращаются только к узлам s и t, то результатом фрагментации и локализации будет отсутствие удаленных ссылок.
Если имеется приложение (множество приложений) Пq1
, локальных для узла w, которые ссылаются на Rs
или Rt
, то появится одна удаленная ссылка.
Если имеется приложение Пq2
, локальное по отношению к w и ссылающееся на атрибуты Rs
и Rt
, то получаются две удаленные ссылки.
Если имеется приложение Пq3
в узлах. отличных от w, s или t и ссылающихся на Rs
и Rt
, то появится еще одна удаленная ссылка.
В общем случае выгодность фрагментации и локализации (при C=1)
,
i≠w, s, t. (13.4)
Описанные эвристические алгоритмы могут не дать рационального решения, поэтому рассмотрим некоторые строгие алгоритмы, базирующиеся на целочисленном программировании
.
Введем обозначения: i (i = 1, I) - независимые файлы-данные; j (j = 1, J) - узлы; Li
- объем файла; bj
- объем памяти узла (для файлов); dsj
- коэффициенты, учитывающие расстояние между узлами s (s = 1, J) и j (dss
= 0); rsj
- стоимость передачи; lij
- интенсивность запросов к файлу i из узла j; l'ij
- интенсивность корректировки сообщений; aij
- объем запросов к файлу i из узла j; bij
- объем запрашиваемых данных при выполнении запроса i из узла j;

Тогда объем данных, поступающих в узел j, содержащий файл i, при выполнении запроса к этому файлу с учетом интенсивности равен lij
(aij
+ bij
)(1 - xij
), а объем данных, составляющих запросы и ответы, lij
(aij
+ bij
)(1 - xij
) xij
.
Возможны следующие критерии: объем передаваемых данных; общая стоимость трафика.
При использовании первого критерия получаем следующую задачу целочисленного программирования:
,
,
.
Аналогичное выражение получается при использовании второго критерия.
«Суммируя» представленные задачи, можно решить задачу размещения и определить количество копий.
Более детальные результаты получены с помощью теории массового обслуживания
с. 23 и целочисленного программирования - работы
и особенно
.
РБД могут быть
однородными (рис. 13.3, а
) и неоднородными (рис. 13.3, б
).
Неоднородность определяется следующими обстоятельствами:
1) использование разных моделей данных;
2) отличие в синтаксисе и семантике даже одного вида моделей (например, реляционных);
3) различие методов управления БД (резервирования и восстановления, синхронизации, блокировки).
Независимо от однородности в общем случае данные из (любой) локальной БД (ЛБД) с одной моделью данных могут быть переданы в (любую) ЛБД с другой моделью данных (МД).
В связи с этим следует обсудить общую постановку задачи взаимного преобразования данных.
Первоначально [
с. 72] для построения неоднородных БД использовались процедуры выгрузки-загрузки фактически на физическом уровне. Информация:
1) выгружалась из исходной аппаратно-программной среды;
2) запоминалась в общем для исходной и объектной сред формата (например, ASCII);
3) загружалась в объектную среду.
На этом пути встретились серьезные трудности. Если преобразование файлов с последовательной физической организацией достаточно просто, то хуже обстоит дело при использовании произвольной выборки. Применение индексно-последовательных файлов практически исключает возможность автоматизации процедуры преобразования.
В этом случае необходимо сначала перейти к произвольному или последовательному способу доступа с уничтожением всех указателей и вспомогательных программных средств, осуществить преобразование, а затем ввести новую систему указателей.
Реализация оказалась сложной, к тому же терялось свойство физической независимости.
Дальнейшие работы пошли по пути преобразований на логическом уровне, при этом выявились два направления.
Построение схем «попарного» взаимодействия моделей данных. При наличии n локальных БД требуется n(n-1) таких схем, что чрезвычайно неудобно.
Использование универсальной виртуальной промежуточной модели. Данные преобразуются в эту глобальную модель и обратно. В качестве такой модели сначала использовали ER-диаграммы [
с. 72].
В дальнейшем более перспективным и успешным оказался современный вариант применения (глобальной) реляционной модели [
], о котором поговорим детальнее.
Для формального описания этого варианта возможно [
] использовать аппарат коммутативной алгебры (рис. 13.4).
Пусть A1
и B1
- состояния системы (например, в прямоугольных координатах), а f1
- функция преобразования состояния системы. Пусть A2
, B2
и f2
описывают ту же систему (например, в полярных координатах). Пусть j - правило преобразования одной системы координат в другую. Для этого случая в строгих алгебраических исследованиях показано, что преобразование верно, если диаграмма на рис. 13.4
коммутативна, т.е. выполняется условие
f2
ґj=ґjf1
, (13.5)
где ґ - некоторая алгебраическая операция.
Можем полагать, что A1
и A2
- исходные таблицы
СУБД с разными в общем случае моделями данных, к которым осуществляется запрос; B1
и B2
- результаты операций обновления или запроса; f1
и f2
- правила получения данных (
ЯОД или
ЯМД или Язык запроса); j - правила перехода (по данным) из одной БД в другую.
Для «точечных», физических систем математические выкладки коммутативной алгебры выполнены детально.
Использование условия (13.5) для БД значительно труднее. Дело в том, что физические системы оперируют однородными, бесструктурными множествами состояний Ai
и Bi
, i = 1, 2.
В РБД осложнения вызываются следующими обстоятельствами [
].
Множества A1
и A2
структуризованы, при этом структура определяется принятой моделью данных. Даже при использовании различных СУБД с одной и той же моделью данных (например, реляционной) возможны различия в форматах данных, в командах ЯОД.
ЯМД и языки запросов могут быть различны даже для однородных РБД с разными типами ЛБД.
Часть этих трудностей уже преодолена. Так, проблема различия в ЯОД и ЯМД при использовании
реляционных БД азличного типа фактически снята при использовании "стандартного"языка SQL2 [
] или приложения [
] Open DataBase Connectivity (ODBC). Сложнее обстоит дело с другими моделями данных, еще труднее, если в РБД используются различные модели данных ЛБД.
Перечисленные проблемы интеграции ЛБД [
] обсудим в самом общем виде.
13.4.
Преобразование структуры и данных
В общем случае преобразование данных модели Mi
в данные модели Mj
возможно двумя путями:
1) «попарное» преобразование, обычно с помощью драйверов: здесь при наличии n локальных БД требуется n (n-1) драйверов; этот путь широко используется в приложении ODBC;
2) построение универсальной промежуточной, виртуальной модели Mв
с преобразованием по схеме
Mi
–>Mв
–>Mj
,
при этом в качестве Mв
может выступать ER-диаграмма [
c. 72] или реляционная модель [
].
Для анализа сути преобразования данных рассмотрим процессы построения БД и работы с ней.
Первоначально на этапе концептуального проектирования задается некоторая схема проектируемой БД и на ЯОД ЯОi
создается структура БД. Эта структура определяется множеством Vi
БД, где элементы vi
εVi
есть типы данных; Id
- множество идентификаторов (имен) полей. Тогда состояние Bi
= (Id
–>Vi
).
Общая схема Si
БД определяется набором Msi
состояний
Msi
: Si
–>Bi
.
Исходное состояние Bi
обозначим Ei
.
Каждому значению Vi
ставится в соответствие значение поля данных, что будет подразумеваться при дальнейших рассуждениях.
При работе с БД используется ЯМД ЯМi
. Оператор oi этого языка осуществляет преобразование Ei
–>Bi
или Bi
–>Bi
". Множество операторов oi
через Moi
. Тогда
Moi
: Bi
–>Bi
" или Ei
–>Bi
,
где Ei
- начальное состояние. Тогда модель данных (МД)
Mi
= <Si
, Msi
, oi
, Moi
>.
Ее необходимо преобразовать в модель Mj
, обладающую отмеченными ранее характеристиками.
Преобразование назовем правильным, если справедливы свойства:
1) полная определенность, т.е. любое состояние модели Mi
представимо в модели Mj
;
2) интерпретируемость: любой оператор ЯМД в Mi
имеет интерпретацию в ЯМД Mj
;
3) воспроизводимость: любое изменение БД в Mi
выполняется некоторым оператором изменения, воспроизводимого средствами Mj
.
Рассмотрим эти свойства детальнее.
Введем операторы σ: Si
–> ; Ψ: Bi
–>Bj
. Тогда должна быть коммутативна диаграмма на рис. 13.5, a,b
или
Msi
.σ = Ψ.Msj
.
Отметим, что Bi
и Bj
в конечном счете характеризуются множествами Vi
(Si
)={
, ...,
} и Vj
(Sj
) = {
, ...,
}. В простейшем случае k = m и говорят о подобных типах данных. Однако он встречается редко, о чем свидетельствует [
] пример СУБД Access и «подобных» реляционных СУБД (табл. 13.1 - 13.4).
Таблица 13.1.
Тип данных СУБД Access
Тип данных |
Характеристика |
Текстовый
Memo
Числовой
Дата/Время
Денежный
Счетчик
Логический
Объект OLE |
255 байт
64 Кб
1, 2, 4, 8 байт
8 байт
8 байт
4 байт
1 байт
до 1 Гб |
Таблица 13.2.
Соотношение типов данных СУБД Paradox
и Access
Paradox |
Access |
Alpfanumeric Number
Short Number Currency
Date |
Текстовой
Числовой, с плавающей точкой, размер поля 8 байт
Числовой, Целое
Числовой, с плавающей точкой, размер поля 8 байт
Дата/Время |
Таблица 13.3.
Соотношение типов данных СУБД BTrieve
и Access
Paradox |
Access |
String, lstring, zstring
Integer 1 byte
2 byte
4 byte
Float, bifloat
4 byte
8 byte
Decimal, numeric
Money
Logical
Lvar |
Текстовой
Числовой, с плавающей точкой, размер поля Байт
Числовой, с плавающей точкой, размер поля
Целое
Числовой, с плавающей точкой, размер поля
Длинное целое
Числовой, с плавающей точкой, размер поля 4 байт
Числовой, с плавающей точкой, размер поля 8 байт
Числовой, с плавающей точкой, размер поля 8 байт
Денежный
Да/Нет
Объект OLE |
Таблица 13.4.
Соотношение типов данных СУБД SQL и
Access
Paradox |
Access |
Char
Varchar
Tinint
Smallint
Int
Real
Float
Double
Data
Time
Timestamp
Image |
Текстовой
Текстовой
Числовой, с плавающей точкой, размер поля 8 байт
Числовой, с плавающей точкой, размер поля Целое
Числовой, с плавающей точкой, размер поля Длинное
целое
Числовой, с плавающей точкой, размер поля 8 байт
Числовой, с плавающей точкой, размер поля 8 байт
Числовой, с плавающей точкой, размер поля 8 байт
Дата/Время
Дата/Время
Да/Нет
Объект OLE |
Здесь лучше говорить не о первичных типах данных, а о некоторых классах (табл. 13.3, 13.4) производных типов данных и построении отображения этих классов.
Иными словами, речь идет о непересекающихся множествах вида Ci
(Vi
)={
},
εVi
, r = 1, R и Cj
(Vj
) = {
}, s = 1, S, при этом
–>
без потери информации. Тогда имеет место посредством оператора Ψ отображение Ci
(Vi
(Si
)) –>Cj
(Vj
(Sj
)), где Sj
= s(Si
), при этом отображение s (преобразование типов) должно быть биективно.
Обеспечение интерпретируемости предполагает, что реализация программы PROGi
(или оператора oi
) на ЯМД Mi
эквивалентна реализации программы PROGj
на ЯМД Mj
, т.е. коммутативна диаграмма на рис. 13.5, c.
Тогда общая связь ЯОД и ЯМД различных моделей данных может быть представлена в виде схемы, показанной на рис. 13.5, d,
где pj
- процедура.
Говорят, что функция s сохраняет операторы, если для любого oi
eMoi
процедура pj
= s(oi
) такова, что:
а) исходные состояния bi
Bi
и bj
Bj
связаны зависимостью bi
= Y(bj
);
б) оператор oi
переводит состояние bi
в состояние bi
", а pj
- состояниеbj
в bj
" и bi
"=Y(bj
").
Оператор oi
и композиция операторов pj
, удовлетворяющая данному требованию, называются эквивалентными относительно отображения Y. Именно такое отображение Y нас будет интересовать.
Функция x - верификационная функция: если исходные состояния ei
и ej
, когда начинают функционировать программы, связаны соотношением ei
= x(ej
), то действия, произведенные программой progi
PROGi
, переводят систему Mi
в состояние bi
, а действия t.progi
PROGj
переводят БД Mj
в состояние bj
и bi
= Y(bj
), t - функция отображения программ.
Возможные соотношения операторов и процедур показаны на рис. 13.6.
Назовем набор операторов oi
в ЯМД Mi
функционально полным (ФП), если для любого начального состояния bi
"
Bi
произвольной БД со схемой Si
можно задать последовательность операций progi
, переводящую БД в произвольное заданное состояние bi
"
Bi
, удовлетворяющее схеме Si
.
Между этим понятием и свойством воспроизводимости действий существует связь. Если есть ФП набор операторов Mi
в Mj
, то Mj
–>Mi
обладает свойством полной определенности и является воспроизводимым.
Далее предполагаем, что свойства 1) - 3) и функциональная полнота имеют место.
13.5.
Однородные и неоднородные РБД
Рассмотрим случай
однородных локальных БД (s
1). В этом случае чаще всего говорят о
реляционных БД. Однако даже при выполнении всех сделанных ранее предположений имеются затруднения.
Пусть имеет место строгое соответствие Msi
.s = Ψ.Msj
. При переходе к произвольной модели Mk
(рис. 13.7)
из-за Ψ≠ 1 должно быть Msi
.s = Ψ.Msk
. Если сохранить y (что желательно), то семантика
ЯОД Mi
должна быть очень богатой.
Это условие выполнить трудно, поэтому действуют иначе. Изменяют функцию y для ЯОД и для
ЯМД путем построения в ODBC соответствующих (попарных) драйверов. С позиций языков полезно использование стандартного
языка SQL, многочисленные диалекты которого хорошо «понимают»друг друга. Поскольку разновидностей однотипных СУБД немного (для реляционных БД это обычно Paradox, dBASE, FoxPro, BTrieve, Access, Oralce), то немного и используемых в ODBC драйверов, что служит серьезным аргументом в пользу данного направления.
Рассматриваемая процедура существенно усложняется для случая разных моделей данных (σ
1).
Построение
неоднородных РБД возможно двумя способами.
Пользователю в каждом узле предоставляется интерфейс от пользователей других локальных БД, т.е. n (n-1) схем преобразования данных.
Создаются единый стандартный пользовательский интерфейс и стандартная внутренняя форма запроса: одна схема РБД, но каждому типу локальных БД должен соответствовать свой тип преобразователя схемы в общую форму (n типов преобразования для n локальных СУБД). Пользователь должен в этом случае изучить новую схему - сетевой стандарт. Оба способа имеют свои достоинства и недостатки.
В общем случае возникает необходимость в построении промежуточной, универсальной, виртуальной модели данных [
], для реализации которой можно использовать, например, реляционную модель.
Сложность здесь не только, как отмечалось ранее, в необходимости богатства семантики ЯОД и ЯМД.
Действительно, коммутативные диаграммы операторов ЯМД предполагают сохранение инвариантности в Mi
логических зависимостей данных, имеющих место в Mj
. Напрямую этому требованию семантика исходных операторов не удовлетворяет: разным внутренним моделям Mi
будут соответствовать различные требования к семантике модели Mj
, в том числе и для состава функционального полного набора операций. Отобразить произвольную модель Mi
в Mj
без изменения семантики данных и операций над ними в Mi
не представляется возможным.
Тогда в общем случае и следует строить (рис. 13.8)
промежуточную модель Mj
такую, чтобы Mj
= ядро Mj
+ Mji
, где модель Mji
отображает логические зависимости, присутствующие в Mi
. Назовем Mji
интерпретациейMi
в Mj
: она имеет все свойства моделей данных.
При конструировании Mji
полезно использовать следующие принципы.
Ориентация на начальные типы данных Mj
при построении в Mji
более сложных типов , отражающих зависимости в Mi
, при этом основой Mji
является Mj
-ядро.
Совмещение синтаксиса операторов Oji
ЯМД Mji
с синтаксисом операторов Oj
путем изменения семантики.
Ядро Mj
должно обладать максимальным разнообразием первичных типов данных с минимумом ограничений.
Принципы построения ядра должны обеспечить его простое расширение введением аксиоматических типов данных и конструированием декларативно заданных семантических ограничений на первичные типы данных.
В этом случае процедура преобразования может иметь такую последовательность.
Определяются начальная Mi
и целевая (конечная) Mj
модели данных.
Отображается ЯОД Mi
в Mj
при инъективных операторах Ψ: Bi
–>Bj
и проверяется коммутативность диаграмм описания схем.
Расширяется модель Mj
до Mji
, включая выбор схем аксиом σji
, определения семантики операторов Oji, расширения Mji
модели Mj
и формальной проверки логической и операторной полноты.
Строятся отображения ЯОД Mi
в ЯОД Mji
, ЯМД Mi
в ЯМД Mji
, включая проверку коммутативности диаграмм отображения схем и операторов.
Истинность системы аксиом должна быть инвариантна к изменениям, осуществляемым оператором ЯМД в Mji
. Аксиома aji
Mji
является инвариантом модели данных Mj
по отношению к операторам Oji
, если из истинности aji
(R), где R - реализация составного типа данных, на котором определяется aji
, следует истинность aji
(oji
(R)/R) для любой oji
Oji
и произвольной R. Такая система аксиом должна быть логически и операторно полна.
Перечисленным требованиям расширяемой модели удовлетворяют
ER-диаграммы [
c. 72] и реляционные модели [
]. В последнем случае язык логики предикатов может служить основой построения аксиоматических типов данных.
Как показал опыт работ [
] и особенно [
], универсальная модель достаточно объемна и сложна, а требование универсальности (в частности, для включаемых моделей бинарных отношений, семантических сетей, фреймов) излишне жестко и в практике необходимо редко.
Чаще используют (наряду с реляционными МД) только сетевые и иерархические модели данных. Их реализаций немного и потому представляется более резонным строить соответствующие драйверы («попарный» метод - рис. 13.5 d).
Такой подход является к тому же элементом построения универсальной модели.
В связи с этим рассмотрим взаимопреобразования иерархическая - реляционная и сетевая - реляционная МД (соотношение сетевой и иерархической моделей данных достаточно просто и к тому же обсуждалось в главе 7).
При описании реляционной БД используем стандартный вариант языка SQL, полагая, что все нестандартности могут быть устранены путем использования приложения ODBC.
При преобразовании МД предполагается (рис. 13.5, а),
что отображение множеств типов данных (форматов данных) проведено. Речь пойдет об отображении структур данных и (рис. 13.5, b)
соответствующих команд (ЯМД).
Возможны различные сочетания МД. Обсудим лишь преобразование сетевых моделей данных в реляционные.
Из многочисленных вариантов преобразования сетевой МД в реляционную рассмотрим только два.
Вся сетевая МД считается совокупностью элементов-пар записей владелец - член [
], а структура записей предполагается простой (без агрегатов), без обратных связей.
В структуре записей разрешаются агрегаты, структура наборов иерархическая и не имеет циклов [
]. Фактически идет преобразование системы наборов в систему таблиц (файлов).
Напомним важнейшие характеристики (табл. 13.5), определяющие структуру сетевой МД.
Таблица 13.5.
Команды сетевой МД
Размещение |
Пояснение |
Отключение |
Включение |
CALC <ключ>
VIA <имя><имя> SET
DIRECT
SYSTEM
INDEX |
Хеширование
Хранение записей рядом
Работа программиста
По умолчанию, сингулярные записи
Используется редко |
МANDATORY - обязательное уничтожение
OPTIONAL - необязательное уничтожение, передача SYSTEM |
AUTOMATIC - автоматическое
MANUAL - ручное, от SYSTEM
|
А. Рассмотрим отдельно [
] две процедуры преобразования: сетевая - реляционная МД, реляционная - сетевая МД. В [
] такое преобразование (без операций) названо трансляцией.
Обозначим через N и R записи и отношения в сетевой и реляционной БД соответственно. Проделаем следующие действия.
Для любого типа записи Ni
определяется такое отношение:
а) Ri
содержит один атрибут для любого элемента данных Ni
;
б) если Ni
имеет ключ, то ключ Ri
соответствует ключу Ni
, иначе ключ Ri
соответствует ключу БД Ni
, который появляется в Ri
как явный атрибут.
Для любой связи Lij
, где Ni
- запись-владелец, Nj
- запись-член, определить реляционное ограничение и изменить существующее отношение так, чтобы:
а) ключ Ni
появился как внешний ключ в Ri
;
б) ввести ограничения в зависимости от типа членства.
Пусть X - внешний ключ (foreign key) FK(Ri
) отношения Ri
в отношении Rj
. Это ограничение обозначим FCij
. Ключ X может быть и не определен (запись сетевой МД передается системе). Это факт обозначим NFCij
.
Результат преобразования сетевой модели в реляционную показан в табл. 13.6
Таблица 13.6.
Преобразование сетевой МД в
реляционную
MANDATORY AUTOMATIC |
MANDATORY MANUAL |
OPTIONAL AUTOMATIC |
OPTIONAL MANUAL |
Добавить FCij.
1. Кортеж отношения Rj включается только при
существовании кортежа отношения Ri со
значением ключа, соответствующего значению FK (Ri)
в добавляемом кортеже Rj.
|
Добавить NFCij.
1. Кортеж отношения Rj включается только при
существовании кортежа отношения Ri со
значением ключа, соответствующего значению FK (Ri)
в добавляемом кортеже Rj.
|
Добавить NFCij.
1. Кортеж отношения Rj включается только при
существовании кортежа отношения Ri со
значением ключа, соответствующего значению FK (Ri)
в добавляемом кортеже Rj: значение FK (Ri)
не может быть не определено. |
|
2. При удалении кортежа Ri
необходимо удалить все кортежи Rj, где FK (Ri)
равно значению в удаляемом отношении Ri.
|
2. При удалении кортежа Ri
необходимо удалить все кортежи Rj, где FK (Ri)
равно значению в удаляемом отношении Ri.
|
2. При удалении кортежа Ri
необходимо удалить все кортежи Rj, где FK (Ri)
равно значению в удаляемом отношении Ri, а
значение FK (Ri) должно быть заменено на «не
определено». |
2. При удалении кортежа Ri
необходимо удалить все кортежи Rj, где FK (Ri)
равно значению в удаляемом отношении Ri, а
значение FK (Ri) должно быть заменено на «не
определено». |
3. При обновлении кортежа Rj
значение FK (Ri) не может заменяться на
значение, которое не соответствует ключу
какого-либо кортежа Ri.
|
3. При обновлении кортежа Rj
значение FK (Ri) не может заменяться на значение «не
определено» и на значение, которое не
соответствует ключу какого-либо кортежа Ri. |
|
|
для четырех случаев:
1) MANDATORY AUTOMATIC (MA);
2) MANDATORY MANUAL (MM);
3) OPTIONAL AUTOMATIC (OA);
4) OPTIONAL MANUAL (OM).
Преобразование реляционной модели в сетевую ведется по следующим правилам.
Необходимо, чтобы все атрибуты реляционной МД имели уникальные имена. В реляционной модели следует выявить внешние ключи, используемые для функциональных зависимостей, отображаемые связями между записями в сетевой схеме, и типы связей M:N. Предполагается, что связям соответствуют отдельные отношения, первичные ключи которых составлены из внешних ключей, участвующих в связях M:N.
Пусть имеются реляционная схема ρ = {R1
, ..., Rn
}, первичные ключи любого отношения и считается, что функциональные типы связей представлены внешними ключами, а тип M:N - отдельным отношением связи.
Тогда процедура перехода может иметь такой вид.
С помощью первичных ключей выявляются все отношения «связи» и получается множество отношений α.
Для любого отношения Ri
в ρ - α:
а) сформировать тип связи Ni
с ключом, соответствующим первичному ключу Ri
, при этом имя отношения становится именем типа записи, атрибуты отношения - элементами данных в типе записи;
б) для любого подмножества атрибутов (исключая первичный ключ в Ri
), если это подмножество представляет собой в Ri
первичный ключ, принадлежащий ρ - α (подмножество является внешним ключом), добавить связь Lij
между типами записи Ni
, соответствующей Ri
, и Nj
, соответствующей Rj
, где внешний ключ есть первичный ключ.
При этом Ni
становится типом записи-члена, а Nj
- записи-владельца. Удалить атрибуты, соответствующие ключу Rj
из Nj
.
Присвоить связи Lij
уникальное имя и установить для связи тип членства:
а) сформировать тип записи Ni
аналогично пункту 2а;
б) добавить по одной связи между типом записи Ni
, соответствующим Ri
, и любому из n других типов записей, участвовавших в связи, что определяется внешним ключом в Ri
; Ni
- общий тип записи-члена, а записи n - записи-владельцы в добавляемых связях (обычно n = 2).
Б. В этом случае имеет место взаимооднозначность преобразования, поэтому рассмотрим только отображение сетевой МД в реляционную.
В сетевой МД выделяются записи-группы gi
Gi
типов Tgi
и групповых отношений sk
типов Tsk
, заданные на множестве записей-групп. Типу записей Tgi
соответствует много записей. В записи-группе могут быть значения элементов данных (ЭД: целые, вещественные, символьные, логические, неопределенные, ссылочные) и агрегатов данных (векторы, повторяющиеся группы). Допускаются только иерархические групповые отношения sk
Gi
×Gj
, характерной особенностью которых является обратное отношение sk
Gj
×Gi
. Унарные групповые отношения - сингулярный набор sk
SG×Gi
, где SG - фиктивный набор из одной записи sg в БД.
Введем ряд определений. gi
Gi
- родительская, gj
- подчиненная группы.
Внутренний идентификаторKgi
- неизбыточная совокупность элементов данных группы Gi
.
ПсевдоключомPsk
подчиненной группы gj
Gj
в групповом отношении sk
при заданной родительской группе gi
Gj
называется неизбыточная совокупность ЭД, входящих в Gj, набор которых позволяет однозначно идентифицировать определенную группу gj
, <
gi
, gj
>
sk
среди других групп - образов gi
.
Селектирующий путь Ws в схеме БД - последовательность групповых отношений Ws = <
sa
, sa+1
, ..., sa+n
>, 0≤i≤n-1, в которой любой второй домен отношения sa+i
совпадает с первым доменом sa+i+1
. Первый тип группы в селектирующем пути Gf
(sa
Gf
×Gn
) должен быть типом группы с внутренней идентификацией.
Селектирующий ключ родительской группы gi
Gi
в отношении sk
посредством селектирующего пути Ws = <sa
, sa+1
, ... , sk-1
> называется совокупностью элементов Csk
= <Kgf
, Psa
, ... , Psk-1
>, где Gf
- первый домен отношения sa
. Селектирующий ключ подчиненной группы gj
Gj
в групповом отношении sk
посредством селектирующего пути WS = <
sa
, ... , sk-1
, sk
> называется совокупностью элементов данных Esk
= <
Csk
, Psk
>.
Иногда селектирующий ключ родительской группы называют
внешним идентификатором подчиненной группы gj
Gj
, который в совокупности с псевдоключом Psk
составляет полный идентификатор группы Gj
. Внутренней идентификации может и не быть. Идентификация таких групп возможна введением нескольких внешних идентификаторов.
По виду функции
выделяют классы членства:
Селектирующим ключом родительской записи Tgi
в групповом отношении sk
является неизбыточная совокупность ЭД, входящих в состав Tgi
и таких, что конкретный набор их значений позволяет однозначно идентифицировать gi
среди всех других множеств Gi
в БД. Селектирующий ключ связывается с типом группового отношения Tsk
и обозначается Csk
. Для псевдоключа Psk
, селектирующего пути Ws селектирующих ключей Csk
, Esk
в групповом отношении sk
, имеются ограничения.
Одно и то же групповое отношение Sl
может входить в состав различных селектирующих путей (использование различных Ps, Sl
в различных Cs). Для этого вводится надстрочный, указывающий индекс j подчиненной записи, для которой строится селекторный ключ
<
>.
Если селектирующий путь включает только полные групповые отношения, то соответствующий селектирующий ключ называется
полным, в противном случае -
частичным.
Если в состав пути Ws = <
s1
, sk
> входит часть группового отношения si
Gm
×Gn
(0≤i≤k-1), то в БД должен существовать подпуть <
si+1
, si+2
, ..., sk
>. Для идентификации таких подпутей селектирующий ключ Csk
расширяется введением в его состав селектирующих ключей Csk+1
1 родительских записей всех групп отношений si+1
≤Ws - дополнительные входы в селектирующий путь Ws. В схему сетевой БД вводится совокупность типов записей Tgi
, Tsk
, типов Ts групповых отношений с заданным для каждого группового отношения классом, селектирующим ключом вместе с соответствующим селектирующим путем и псевдоключом. Это есть ориентированный граф
Tsk
Tgi
–>Tgj
.
Селектирующие пути совпадают с некоторыми путями S-графа - несвязного графа с компонентами связности.
Семантика ЯМД, выполняемая над записью Tgi
, является функцией:
1) схемы БД, Tgi
, типа наборов, в которых записи Tgi
участвуют в качестве владельца, и определения селектирующего пути, в состав которых входит Tgi
;
2) текущего состояния Д.
Введем необходимые соответствия.
Каждому Tgi
ставится во взаимнооднозначное соответствие тип отношения Tri
реляционной схемы, так что домены Tgi
взаимнооднозначно соответствуют элементам данных и агрегатам Tgi
. Допускаются домены, которые снова являются отношениями (Tri
- реляционное отношение).
Любой тип записи Tgi
рассматривается как составной тип совместно со всеми наборами, в которых Tgi
объявлен в качестве члена-набора, а также совместно с селектирующими путями таких наборов, в которых участвует Tgi
.
Схема для любого типа Tri
расширяется дополнительными доменами, позволяющими отобразить информацию об участии Tgi
в наборах: в схему Tri
включаются домены, соответствующие элементам данных, входящих в состав селектирующих ключей всех наборов, в которых Tgi
объявлен членом, и селектирующих ключей путей, проходящих через Tgi
. Для Tri
тип записи Tgi
- базовый.
Пример 13.1.Rj
соответствует множеству записей Gj
и существует полное групповое отношение sk
Gi
×Gj
, <
gi
, gj
>, на реляционном уровне - включение в кортеж rj
Rj
, соответствующий gj
, атрибутов, содержащих селектирующий ключ, однозначно идентифицированный кортеж ri
Ri
, соответствующий записи gi
.
Атрибуты, составляющие селектирующий ключ в rj
, взаимно однозначно соответствуют атрибутам одного из ключей (главного, вторичного) ri
. Для частичных отношений отсутствия связи gi
–>gj
в кортеже rj
Rj
значения атрибутов, соответствующих селектирующему ключу, становятся неопределенными.
При отображении схем будут использоваться такие понятия.
Скалярные типы данных.
Биективное отображение имен типов записей в имена типов отношений.
Вводится соответствие имен доменов отношений именам элементов и агрегатов типов записей:
- первый индекс реляционной схемы - тип отношения;
- 2 - (m-1) индексы - имена иерархически вложенных отношений;
- последний индекс - положение простого или составного домена в идентифицированном предшествующей последовательностью индексов отношении. Результат отображения - кортеж целых индексов, определенных компонентами сетевой схемы (имена иерархически вложенных групп, элемент (агрегат) данных).
Соответствие каждому типу сетевой записи множества селектирующих путей и селектирующих ключей.
Первичный (главный) ключ для каждого типа отношений:
а) если тип записи имеет CALC-ключ без дубликатов, то первичный ключ отношения r составляют атрибуты, соответствующие элементам данных, входящих в CALC-ключ;
б) если тип записи не имеет такого ключа, но объявлен членом набора sk
с MANDATORY AUTOMATIC (MA), причем в наборе существует расширенный селектирующий ключ, то первичный ключ отношения r составляют атрибуты, соответствующие элементам данных, входящих в расширенный селектирующий ключ;
в) если правила а) - б) неприменимы, но тип записи n объявлен членом нескольких наборов с классом членства MA, однозначно идентифицируемой по совокупности владельцев, то первичный ключ для отношения r составляют атрибуты, соответствующие элементам данных, входящим в селектирующие ключи в такой совокупности наборов;
г) если правила а) - б) неприменимы, то первичный ключ отношения r составляют атрибуты, соответствующие неизбыточной совокупности элементов данных типа n, по значениям которой должны быть однозначно идентифицированы экземпляры записей этого типа. Затем все типы получают первичный ключ.
Соответствие имен атрибутов селектирующего ключа именам атрибутов вторичного ключа в парах взаимосвязанных типов отношений. Для каждой пары типов отношений Tri
и Trj
, соответствующей типам записей Tgi
и Tgj
таких, что sk
Gi
×Gj
определяется состав атрибутов, интерпретирующих селектирующий ключ в Tri
. Этим атрибутам должны быть поставлены во взаимно однозначное соответствие атрибуты вторичного ключа Tri
.
Покажем процесс преобразования для сетевой БД, показанной на рис. 13.9.
Ее характеристики представлены в табл. 13.7 и 13.8
.
Таблица 13.7.
Схема типов записи
Имя типа записи |
Идентификатор |
Имена ЭД |
Фраза LOCATION |
A
B
C
D
E
F
G |
H
M
S
V
E
Ж
- |
L, M
O, P, R
T, V
W, Z, Y
Х, Ф
З, И |
DIRECT
CALC P, R*
DIRECT
VIA γ SET
CALC X*
DIRECT2
SYSTEM |
* - DUPLICATES NOT ALLCWED
Результат преобразования по описанным ранее правилам для доменов отношений D и E дан в табл. 13.9
и 13.10
.
Схема отношения D участвует в 8 селектирующих путях и имеет атрибуты V, W, Z, Y, P, R, T, H, T1, P1, R1, T2, H1, U, U1.
Соответственно схема отношения E участвует в 4 селектирующих путях и имеет атрибуты K, X, Ф, H, U, Z, H1, P, R, T, W.
В [
] подробно проанализировано преобразование команд ЯМД (рис. 13.5, b)
. Поскольку эта процедура достаточно трудоемка в изложении, она здесь не приводится.
Преобразование иерархических моделей данных в реляционные проще и из-за ограниченного объема данной работы не приводится.