Московский государственный университет печати

Будем придерживаться порядка изложения в соответствии с этапами проектирования (рис 2.5).

В качестве принципов проектирования можно использовать :

1) максимум локализации данных и сокращение количества пересылаемых по кратчайшему пути данных: рекомендуется иметь до 90 процентов ее в локальной БД (ЛБД) узла и около 10 процентов - в ЛБД других узлов;

2) локальность расположения данных следует определять по отношению к наибольшему числу приложений.

В качестве критериев проектирования РБД могут быть :

1) минимум объема пересылаемых данных и сообщений;

2) минимум стоимости трафика;

3) минимум общего времени, необходимого для обслуживания запросов к БД.

В рассмотрении РБД возможно выделить два случая работы: с одним приложением и с системой приложений. Возможно нисходящее и восходящее проектирование.

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

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

В общем случае целостность данных может нарушаться по следующим основным причинам:

1) ошибки в создании структуры локальных БД и их заполнении;

2) просчеты в построении структуры РБД (процедуры фрагментации и локализации);

3) системные ошибки в программном обеспечении взаимодействия локальных БД (одновременный доступ);

4) аварийная ситуация (неисправность технических средств) и восстановление РБД.

Первая позиция подробно освещена ранее и здесь рассматриваться не будет. Специфика остальных трех позиций для РБД может быть зафиксирована в виде совокупности проблем (рис. 13.1). Четвертая позиция исследуется в последующих главах, вторую и третью - подробно изучим здесь.

Иногда к нарушению целостности относят умышленное искажение информации, т.е. несанкционирванный доступ. Эти вопросы будут рассмотрены позднее.

Напомним (рис. 2.5), что общая этапность проектирования РБД напоминает этапность при создании централизованной БД и отличие имеет место лишь в этапах фрагментации (расчленения) и локализации (размещения).

Основными факторами, определяющими методику расчленения, являются допустимый размер каждого раздела; модели и частоты использования приложений; структурная совместимость; факторы производительности БД. Связь между разделом БД и приложениями характеризуется идентификатором типа приложения, идентификатором узла сети, частотой использования приложения и его моделью.

Сложность реализации этапа размещения БД определяется многовариантностью. Поэтому на практике рекомендуется в первую очередь рассмотреть возможность использования определенных допущений, упрощающих функции СУРБД (например, допустимость временного рассогласования БД, осуществление процедуры обновления БД из одного узла).

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

1. Полнота. Все данные глобального отношения R должны быть отображены в его фрагменты.

2. Восстанавливаемость. Всегда возможно восстановить глобальное отношение из фрагментов.

3. Непересечение. Целесообразно, чтобы фрагменты не пересекались (дублирование производится на этапе локализации).

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

Вертикальная фрагментация с помощью проекции делит глобальное отношение (схему R) по приложениям (или по географическому признаку).

Фрагментация корректна, если любой атрибут глобального отношения (схемы R) присутствует в каком-либо подмножестве атрибутов и глобальное отношение восстанавливается естественным соединением.

Фрагментация совместно с локализацией (рис.13.2) определяют в конечном итоге быстроту реакции РБД на запрос.

Обозначим узлы через j (j = 1, J), а приложения - через k (k = 1, K). Если имеется отношение r со схемой R, то в узле j имеется отношение-фрагмент R_j . Если в узле j имеется к тому же копия фрагмента R_i , i = 1, J, то обозначим ее через R_ij . Тогда схема фрагментации и локализации может быть представлена в виде, показанном на рис. 13.2.

Иными словами, при фрагментации декомпозиция глобального отношения должна обладать свойством соединения без потерь.

Возможна смешанная фрагментация, которой соответствует совокупность операций селекции и проекции

,

где R = {a_lj , ..., a_mj }, m - число записей в горизонтальном фрагменте.

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

Воспользуемся обозначениями, введенными в данной главе. Пусть f_kj - частота активизации приложения k в узле j, r_ki - число ссылок поиска приложения k во фрагменте i, u_ki - число ссылок обновления данных приложения k во фрагменте i, n_ki = r_ki + u_ki .

Задача размещения имеет две основные разновидности: без использования и с использованием копий.

Рассмотрим первую разновидность. Здесь возможны эвристические и строго математические алгоритмы.

Обсудим сначала один из эвристических алгоритмов размещения, состоящий из нескольких шагов.

Шаг 1. Используем метод «наиболее подходящего» размещения: фрагмент Ri размещается в узле j, где число ссылок на него максимально. Число локальных ссылок

, (13.1)

Из выражения (13.1) определяется узел j*, где следует разместить фрагмент.

Шаг 2. Применим метод выделения «всех выгодных узлов» для избыточного размещения: помещаем Ri во всех узлах, где стоимость ссылок приложений, осуществляющих поиск, больше стоимости ссылок приложений, обновляющих данные во фрагменте Ri в любом узле: Bij>0 или

, (13.2)

где C - отношение стоимости обновления и поиска.

Шаг 3. Используем метод "добавочного копирования". Пусть d_i - степень избыточностиR_i ; F_i - выгодность размещения копии в любом узле РБД и b(d_i ) = (1 - 2^l-d)F_i . Модифицируя выражение (13.2), получим

. (13.3)

Учтем вертикальную фрагментацию.

Пусть схема R_i декомпозирована на R_s и R_t , где s и t - узлы.

Используем следующие рассуждения.

1. Если существует два приложения П_s и П_t , которые используют только атрибуты R_s и R_t , т.е. обращаются только к узлам s и t, то результатом фрагментации и локализации будет отсутствие удаленных ссылок.

2. Если имеется приложение (множество приложений) П_q1 , локальных для узла w, которые ссылаются на R_s или R_t , то появится одна удаленная ссылка.

3. Если имеется приложение П_q2 , локальное по отношению к w и ссылающееся на атрибуты R_s и R_t , то получаются две удаленные ссылки.

4. Если имеется приложение П_q3 в узлах. отличных от w, s или t и ссылающихся на R_s и R_t , то появится еще одна удаленная ссылка.

В общем случае выгодность фрагментации и локализации (при C=1)

,

i≠w, s, t. (13.4)

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

Введем обозначения: i (i = 1, I) - независимые файлы-данные; j (j = 1, J) - узлы; L_i - объем файла; b_j - объем памяти узла (для файлов); d_sj - коэффициенты, учитывающие расстояние между узлами s (s = 1, J) и j (d_ss = 0); r_sj - стоимость передачи; l_ij - интенсивность запросов к файлу i из узла j; l'_ij - интенсивность корректировки сообщений; a_ij - объем запросов к файлу i из узла j; b_ij - объем запрашиваемых данных при выполнении запроса i из узла j;

Тогда объем данных, поступающих в узел j, содержащий файл i, при выполнении запроса к этому файлу с учетом интенсивности равен l_ij (a_ij + b_ij )(1 - x_ij ), а объем данных, составляющих запросы и ответы, l_ij (a_ij + b_ij )(1 - x_ij ) x_ij .

Возможны следующие критерии: объем передаваемых данных; общая стоимость трафика.

При использовании первого критерия получаем следующую задачу целочисленного программирования:

,

,

.

Аналогичное выражение получается при использовании второго критерия.

«Суммируя» представленные задачи, можно решить задачу размещения и определить количество копий.

Более детальные результаты получены с помощью теории массового обслуживания с. 23 и целочисленного программирования - работы и особенно .

РБД могут быть однородными (рис. 13.3, а) и неоднородными (рис. 13.3, б).

Неоднородность определяется следующими обстоятельствами:

1) использование разных моделей данных;

2) отличие в синтаксисе и семантике даже одного вида моделей (например, реляционных);

3) различие методов управления БД (резервирования и восстановления, синхронизации, блокировки).

Независимо от однородности в общем случае данные из (любой) локальной БД (ЛБД) с одной моделью данных могут быть переданы в (любую) ЛБД с другой моделью данных (МД).

В связи с этим следует обсудить общую постановку задачи взаимного преобразования данных.

Первоначально [ с. 72] для построения неоднородных БД использовались процедуры выгрузки-загрузки фактически на физическом уровне. Информация:

1) выгружалась из исходной аппаратно-программной среды;

2) запоминалась в общем для исходной и объектной сред формата (например, ASCII);

3) загружалась в объектную среду.

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

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

Реализация оказалась сложной, к тому же терялось свойство физической независимости.

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

1. Построение схем «попарного» взаимодействия моделей данных. При наличии n локальных БД требуется n(n-1) таких схем, что чрезвычайно неудобно.

2. Использование универсальной виртуальной промежуточной модели. Данные преобразуются в эту глобальную модель и обратно. В качестве такой модели сначала использовали ER-диаграммы [ с. 72].

В дальнейшем более перспективным и успешным оказался современный вариант применения (глобальной) реляционной модели [], о котором поговорим детальнее.

Для формального описания этого варианта возможно [] использовать аппарат коммутативной алгебры (рис. 13.4).

Пусть A₁ и B₁ - состояния системы (например, в прямоугольных координатах), а f₁ - функция преобразования состояния системы. Пусть A₂ , B₂ и f₂ описывают ту же систему (например, в полярных координатах). Пусть j - правило преобразования одной системы координат в другую. Для этого случая в строгих алгебраических исследованиях показано, что преобразование верно, если диаграмма на рис. 13.4 коммутативна, т.е. выполняется условие

f₂ ґj=ґjf₁ , (13.5)

где ґ - некоторая алгебраическая операция.

Можем полагать, что A₁ и A₂ - исходные таблицы СУБД с разными в общем случае моделями данных, к которым осуществляется запрос; B₁ и B₂ - результаты операций обновления или запроса; f₁ и f₂ - правила получения данных (ЯОД или ЯМД или Язык запроса); j - правила перехода (по данным) из одной БД в другую.

Для «точечных», физических систем математические выкладки коммутативной алгебры выполнены детально.

Использование условия (13.5) для БД значительно труднее. Дело в том, что физические системы оперируют однородными, бесструктурными множествами состояний A_i и B_i , i = 1, 2.

В РБД осложнения вызываются следующими обстоятельствами [].

1. Множества A₁ и A₂ структуризованы, при этом структура определяется принятой моделью данных. Даже при использовании различных СУБД с одной и той же моделью данных (например, реляционной) возможны различия в форматах данных, в командах ЯОД.

2. ЯМД и языки запросов могут быть различны даже для однородных РБД с разными типами ЛБД.

Часть этих трудностей уже преодолена. Так, проблема различия в ЯОД и ЯМД при использовании реляционных БД азличного типа фактически снята при использовании "стандартного"языка SQL2 [] или приложения [] Open DataBase Connectivity (ODBC). Сложнее обстоит дело с другими моделями данных, еще труднее, если в РБД используются различные модели данных ЛБД.

Перечисленные проблемы интеграции ЛБД [] обсудим в самом общем виде.

В общем случае преобразование данных модели M_i в данные модели M_j возможно двумя путями:

1) «попарное» преобразование, обычно с помощью драйверов: здесь при наличии n локальных БД требуется n (n-1) драйверов; этот путь широко используется в приложении ODBC;

2) построение универсальной промежуточной, виртуальной модели M_в с преобразованием по схеме

M_i –>M_в –>M_j ,

при этом в качестве M_в может выступать ER-диаграмма [ c. 72] или реляционная модель [].

Для анализа сути преобразования данных рассмотрим процессы построения БД и работы с ней.

1. Первоначально на этапе концептуального проектирования задается некоторая схема проектируемой БД и на ЯОД ЯО_i создается структура БД. Эта структура определяется множеством V_i БД, где элементы v_i εV_i есть типы данных; I_d - множество идентификаторов (имен) полей. Тогда состояние B_i = (I_d –>V_i ).

2. Общая схема S_i БД определяется набором Ms_i состояний

   Ms_i : S_i –>B_i .

   Исходное состояние B_i обозначим E_i .

3. Каждому значению V_i ставится в соответствие значение поля данных, что будет подразумеваться при дальнейших рассуждениях.

4. При работе с БД используется ЯМД ЯМ_i . Оператор oi этого языка осуществляет преобразование E_i –>B_i или B_i –>B_i ". Множество операторов o_i через Mo_i . Тогда

   Mo_i : B_i –>B_i " или E_i –>B_i ,

   где E_i - начальное состояние. Тогда модель данных (МД)

   M_i = <S_i , Ms_i , o_i , Mo_i >.

Ее необходимо преобразовать в модель M_j , обладающую отмеченными ранее характеристиками.

Преобразование назовем правильным, если справедливы свойства:

1) полная определенность, т.е. любое состояние модели M_i представимо в модели M_j ;

2) интерпретируемость: любой оператор ЯМД в M_i имеет интерпретацию в ЯМД M_j ;

3) воспроизводимость: любое изменение БД в M_i выполняется некоторым оператором изменения, воспроизводимого средствами M_j .

Рассмотрим эти свойства детальнее.

1. Введем операторы σ: S_i –> ; Ψ: B_i –>B_j . Тогда должна быть коммутативна диаграмма на рис. 13.5, a,b или

   Ms_i .σ = Ψ.Ms_j .

   Отметим, что B_i и B_j в конечном счете характеризуются множествами V_i (S_i )={, ..., } и V_j (S_j ) = {, ..., }. В простейшем случае 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) производных типов данных и построении отображения этих классов.

   Иными словами, речь идет о непересекающихся множествах вида C_i (V_i )={}, εV_i , r = 1, R и C_j (V_j ) = {}, s = 1, S, при этом –> без потери информации. Тогда имеет место посредством оператора Ψ отображение C_i (V_i (S_i )) –>C_j (V_j (S_j )), где S_j = s(S_i ), при этом отображение s (преобразование типов) должно быть биективно.

2. Обеспечение интерпретируемости предполагает, что реализация программы PROG_i (или оператора o_i ) на ЯМД M_i эквивалентна реализации программы PROG_j на ЯМД M_j , т.е. коммутативна диаграмма на рис. 13.5, c.

   Тогда общая связь ЯОД и ЯМД различных моделей данных может быть представлена в виде схемы, показанной на рис. 13.5, d, где p_j - процедура.

3. Говорят, что функция s сохраняет операторы, если для любого o_i eMo_i процедура p_j = s(o_i ) такова, что:

   а) исходные состояния b_i B_i и b_j B_j связаны зависимостью b_i = Y(b_j );

   б) оператор o_i переводит состояние b_i в состояние b_i ", а p_j - состояниеb_j в b_j " и b_i "=Y(b_j ").

Оператор o_i и композиция операторов p_j , удовлетворяющая данному требованию, называются эквивалентными относительно отображения Y. Именно такое отображение Y нас будет интересовать.

Функция x - верификационная функция: если исходные состояния e_i и e_j , когда начинают функционировать программы, связаны соотношением e_i = x(e_j ), то действия, произведенные программой prog_i PROG_i , переводят систему M_i в состояние b_i , а действия t.prog_i PROG_j переводят БД M_j в состояние b_j и b_i = Y(b_j ), t - функция отображения программ.

Возможные соотношения операторов и процедур показаны на рис. 13.6.

Назовем набор операторов o_i в ЯМД M_i функционально полным (ФП), если для любого начального состояния b_i "B_i произвольной БД со схемой S_i можно задать последовательность операций prog_i , переводящую БД в произвольное заданное состояние b_i "B_i , удовлетворяющее схеме S_i .

Между этим понятием и свойством воспроизводимости действий существует связь. Если есть ФП набор операторов M_i в M_j , то M_j –>M_i обладает свойством полной определенности и является воспроизводимым.

Далее предполагаем, что свойства 1) - 3) и функциональная полнота имеют место.

Рассмотрим случай однородных локальных БД (s1). В этом случае чаще всего говорят о реляционных БД. Однако даже при выполнении всех сделанных ранее предположений имеются затруднения.

Пусть имеет место строгое соответствие Ms_i .s = Ψ.Ms_j . При переходе к произвольной модели M_k (рис. 13.7) из-за Ψ≠ 1 должно быть Ms_i .s = Ψ.Ms_k . Если сохранить y (что желательно), то семантика ЯОД M_i должна быть очень богатой.

Это условие выполнить трудно, поэтому действуют иначе. Изменяют функцию y для ЯОД и для ЯМД путем построения в ODBC соответствующих (попарных) драйверов. С позиций языков полезно использование стандартного языка SQL, многочисленные диалекты которого хорошо «понимают»друг друга. Поскольку разновидностей однотипных СУБД немного (для реляционных БД это обычно Paradox, dBASE, FoxPro, BTrieve, Access, Oralce), то немного и используемых в ODBC драйверов, что служит серьезным аргументом в пользу данного направления.

Рассматриваемая процедура существенно усложняется для случая разных моделей данных (σ1).

Построение неоднородных РБД возможно двумя способами.

1. Пользователю в каждом узле предоставляется интерфейс от пользователей других локальных БД, т.е. n (n-1) схем преобразования данных.

2. Создаются единый стандартный пользовательский интерфейс и стандартная внутренняя форма запроса: одна схема РБД, но каждому типу локальных БД должен соответствовать свой тип преобразователя схемы в общую форму (n типов преобразования для n локальных СУБД). Пользователь должен в этом случае изучить новую схему - сетевой стандарт. Оба способа имеют свои достоинства и недостатки.

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

Сложность здесь не только, как отмечалось ранее, в необходимости богатства семантики ЯОД и ЯМД.

Действительно, коммутативные диаграммы операторов ЯМД предполагают сохранение инвариантности в M_i логических зависимостей данных, имеющих место в M_j . Напрямую этому требованию семантика исходных операторов не удовлетворяет: разным внутренним моделям M_i будут соответствовать различные требования к семантике модели M_j , в том числе и для состава функционального полного набора операций. Отобразить произвольную модель M_i в M_j без изменения семантики данных и операций над ними в M_i не представляется возможным.

Тогда в общем случае и следует строить (рис. 13.8) промежуточную модель M_j такую, чтобы M_j = ядро M_j + M_ji , где модель M_ji отображает логические зависимости, присутствующие в M_i . Назовем M_ji интерпретациейM_i в M_j : она имеет все свойства моделей данных.

При конструировании M_ji полезно использовать следующие принципы.

1. Ориентация на начальные типы данных M_j при построении в M_ji более сложных типов , отражающих зависимости в M_i , при этом основой M_ji является M_j -ядро.

2. Совмещение синтаксиса операторов O_ji ЯМД M_ji с синтаксисом операторов O_j путем изменения семантики.

3. Ядро M_j должно обладать максимальным разнообразием первичных типов данных с минимумом ограничений.

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

В этом случае процедура преобразования может иметь такую последовательность.

1. Определяются начальная M_i и целевая (конечная) M_j модели данных.

2. Отображается ЯОД M_i в M_j при инъективных операторах Ψ: B_i –>B_j и проверяется коммутативность диаграмм описания схем.

3. Расширяется модель M_j до M_ji , включая выбор схем аксиом σ_ji , определения семантики операторов Oji, расширения M_ji модели M_j и формальной проверки логической и операторной полноты.

4. Строятся отображения ЯОД M_i в ЯОД M_ji , ЯМД M_i в ЯМД M_ji , включая проверку коммутативности диаграмм отображения схем и операторов.

Истинность системы аксиом должна быть инвариантна к изменениям, осуществляемым оператором ЯМД в M_ji . Аксиома a_ji M_ji является инвариантом модели данных M_j по отношению к операторам O_ji , если из истинности a_ji (R), где R - реализация составного типа данных, на котором определяется a_ji , следует истинность a_ji (o_ji (R)/R) для любой o_ji O_ji и произвольной R. Такая система аксиом должна быть логически и операторно полна.

Перечисленным требованиям расширяемой модели удовлетворяют ER-диаграммы [ c. 72] и реляционные модели []. В последнем случае язык логики предикатов может служить основой построения аксиоматических типов данных.

Как показал опыт работ [] и особенно [], универсальная модель достаточно объемна и сложна, а требование универсальности (в частности, для включаемых моделей бинарных отношений, семантических сетей, фреймов) излишне жестко и в практике необходимо редко.

Чаще используют (наряду с реляционными МД) только сетевые и иерархические модели данных. Их реализаций немного и потому представляется более резонным строить соответствующие драйверы («попарный» метод - рис. 13.5 d).

Такой подход является к тому же элементом построения универсальной модели.

В связи с этим рассмотрим взаимопреобразования иерархическая - реляционная и сетевая - реляционная МД (соотношение сетевой и иерархической моделей данных достаточно просто и к тому же обсуждалось в главе 7).

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

При преобразовании МД предполагается (рис. 13.5, а), что отображение множеств типов данных (форматов данных) проведено. Речь пойдет об отображении структур данных и (рис. 13.5, b) соответствующих команд (ЯМД).

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

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

1. Вся сетевая МД считается совокупностью элементов-пар записей владелец - член [], а структура записей предполагается простой (без агрегатов), без обратных связей.

2. В структуре записей разрешаются агрегаты, структура наборов иерархическая и не имеет циклов []. Фактически идет преобразование системы наборов в систему таблиц (файлов).

Напомним важнейшие характеристики (табл. 13.5), определяющие структуру сетевой МД.

Таблица 13.5.

Команды сетевой МД

Размещение	Пояснение	Отключение	Включение
CALC <ключ> VIA <имя><имя> SET DIRECT SYSTEM INDEX	Хеширование Хранение записей рядом Работа программиста По умолчанию, сингулярные записи Используется редко	МANDATORY - обязательное уничтожение OPTIONAL - необязательное уничтожение, передача SYSTEM	AUTOMATIC - автоматическое MANUAL - ручное, от SYSTEM

А. Рассмотрим отдельно [] две процедуры преобразования: сетевая - реляционная МД, реляционная - сетевая МД. В [] такое преобразование (без операций) названо трансляцией.

Обозначим через N и R записи и отношения в сетевой и реляционной БД соответственно. Проделаем следующие действия.

1. Для любого типа записи N_i определяется такое отношение:

   а) R_i содержит один атрибут для любого элемента данных N_i ;

   б) если N_i имеет ключ, то ключ R_i соответствует ключу N_i , иначе ключ R_i соответствует ключу БД N_i , который появляется в R_i как явный атрибут.

2. Для любой связи L_ij , где N_i - запись-владелец, N_j - запись-член, определить реляционное ограничение и изменить существующее отношение так, чтобы:

   а) ключ N_i появился как внешний ключ в R_i ;

   б) ввести ограничения в зависимости от типа членства.

Пусть X - внешний ключ (foreign key) FK(R_i ) отношения R_i в отношении R_j . Это ограничение обозначим FC_ij . Ключ X может быть и не определен (запись сетевой МД передается системе). Это факт обозначим NFC_ij .

Результат преобразования сетевой модели в реляционную показан в табл. 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.

Пусть имеются реляционная схема ρ = {R₁ , ..., R_n }, первичные ключи любого отношения и считается, что функциональные типы связей представлены внешними ключами, а тип M:N - отдельным отношением связи.

Тогда процедура перехода может иметь такой вид.

1. С помощью первичных ключей выявляются все отношения «связи» и получается множество отношений α.

2. Для любого отношения R_i в ρ - α:

   а) сформировать тип связи N_i с ключом, соответствующим первичному ключу R_i , при этом имя отношения становится именем типа записи, атрибуты отношения - элементами данных в типе записи;

   б) для любого подмножества атрибутов (исключая первичный ключ в R_i ), если это подмножество представляет собой в R_i первичный ключ, принадлежащий ρ - α (подмножество является внешним ключом), добавить связь L_ij между типами записи N_i , соответствующей R_i , и N_j , соответствующей R_j , где внешний ключ есть первичный ключ.

   При этом N_i становится типом записи-члена, а N_j - записи-владельца. Удалить атрибуты, соответствующие ключу R_j из N_j .

3. Присвоить связи L_ij уникальное имя и установить для связи тип членства:

   а) сформировать тип записи N_i аналогично пункту 2а;

   б) добавить по одной связи между типом записи N_i , соответствующим R_i , и любому из n других типов записей, участвовавших в связи, что определяется внешним ключом в R_i ; N_i - общий тип записи-члена, а записи n - записи-владельцы в добавляемых связях (обычно n = 2).

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

В сетевой МД выделяются записи-группы g_i G_i типов Tg_i и групповых отношений s_k типов Ts_k , заданные на множестве записей-групп. Типу записей Tg_i соответствует много записей. В записи-группе могут быть значения элементов данных (ЭД: целые, вещественные, символьные, логические, неопределенные, ссылочные) и агрегатов данных (векторы, повторяющиеся группы). Допускаются только иерархические групповые отношения s_k G_i ×G_j , характерной особенностью которых является обратное отношение s_k G_j ×G_i . Унарные групповые отношения - сингулярный набор s_k SG×G_i , где SG - фиктивный набор из одной записи sg в БД.

Введем ряд определений. g_i G_i - родительская, g_j - подчиненная группы. Внутренний идентификаторKg_i - неизбыточная совокупность элементов данных группы G_i . ПсевдоключомPs_k подчиненной группы g_j G_j в групповом отношении s_k при заданной родительской группе g_i G_j называется неизбыточная совокупность ЭД, входящих в Gj, набор которых позволяет однозначно идентифицировать определенную группу g_j , < g_i , g_j >s_k среди других групп - образов g_i . Селектирующий путь Ws в схеме БД - последовательность групповых отношений Ws = < s_a , s_a+1 , ..., s_a+n >, 0≤i≤n-1, в которой любой второй домен отношения s_a+i совпадает с первым доменом s_a+i+1 . Первый тип группы в селектирующем пути G_f (s_a G_f ×G_n ) должен быть типом группы с внутренней идентификацией. Селектирующий ключ родительской группы g_i G_i в отношении s_k посредством селектирующего пути Ws = <s_a , s_a+1 , ... , s_k-1 > называется совокупностью элементов Cs_k = <Kg_f , Ps_a , ... , Ps_k-1 >, где G_f - первый домен отношения s_a . Селектирующий ключ подчиненной группы g_j G_j в групповом отношении s_k посредством селектирующего пути WS = < s_a , ... , s_k-1 , s_k > называется совокупностью элементов данных Es_k = < Cs_k , Ps_k >.

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

По виду функции выделяют классы членства:

1) групповые отношения с полной функциональной зависимостью (групповыми отношениями): s_k G_i ×G_j , в которых для любой записи g_j G_j в базе данных всегда существует единственная запись g_i G_i , что < g_i , g_j >s_k ; иначе названная функция является полной функцией и исключение g_i влечет исключение g_j - MANDATORY AUTOMATIC (MA);

2) с частично слабой фукциональной зависимостью - OPTIONAL MANUAL (OM);

3) с частично сильной функциональной зависмостью, если имеется класс 1) и после образования < g_i , g_j >s_k запись g_j G_j не может существовать без этой связи - MANDATORY MANUAL (MM);

4) отношение с первоначальной связью, если имеется класс 2) и запись g_j G_j может быть помещена в БД только тогда, когда существует g_i G_i и непосредственно после помещения g_j устанавливается связь < g_i , g_j >s_k - OPTIONAL AUTOMATIC (OA).

Селектирующим ключом родительской записи Tg_i в групповом отношении s_k является неизбыточная совокупность ЭД, входящих в состав Tg_i и таких, что конкретный набор их значений позволяет однозначно идентифицировать g_i среди всех других множеств G_i в БД. Селектирующий ключ связывается с типом группового отношения Ts_k и обозначается Cs_k . Для псевдоключа Ps_k , селектирующего пути Ws селектирующих ключей Cs_k , Es_k в групповом отношении s_k , имеются ограничения.

1. Одно и то же групповое отношение S_l может входить в состав различных селектирующих путей (использование различных Ps, S_l в различных Cs). Для этого вводится надстрочный, указывающий индекс j подчиненной записи, для которой строится селекторный ключ

   < >.

2. Если селектирующий путь включает только полные групповые отношения, то соответствующий селектирующий ключ называется полным, в противном случае - частичным.

Если в состав пути Ws = < s₁ , s_k > входит часть группового отношения s_i G_m ×G_n (0≤i≤k-1), то в БД должен существовать подпуть < s_i+1 , s_i+2 , ..., s_k >. Для идентификации таких подпутей селектирующий ключ Cs_k расширяется введением в его состав селектирующих ключей Cs_k+1 1 родительских записей всех групп отношений s_i+1 ≤Ws - дополнительные входы в селектирующий путь Ws. В схему сетевой БД вводится совокупность типов записей Tg_i , Ts_k , типов Ts групповых отношений с заданным для каждого группового отношения классом, селектирующим ключом вместе с соответствующим селектирующим путем и псевдоключом. Это есть ориентированный граф

Ts_k

Tg_i –>Tg_j .

Селектирующие пути совпадают с некоторыми путями S-графа - несвязного графа с компонентами связности.

Семантика ЯМД, выполняемая над записью Tg_i , является функцией:

1) схемы БД, Tg_i , типа наборов, в которых записи Tg_i участвуют в качестве владельца, и определения селектирующего пути, в состав которых входит Tg_i ;

2) текущего состояния Д.

Введем необходимые соответствия.

1. Каждому Tg_i ставится во взаимнооднозначное соответствие тип отношения Tr_i реляционной схемы, так что домены Tg_i взаимнооднозначно соответствуют элементам данных и агрегатам Tg_i . Допускаются домены, которые снова являются отношениями (Tr_i - реляционное отношение).

2. Любой тип записи Tg_i рассматривается как составной тип совместно со всеми наборами, в которых Tg_i объявлен в качестве члена-набора, а также совместно с селектирующими путями таких наборов, в которых участвует Tg_i .

Схема для любого типа Tr_i расширяется дополнительными доменами, позволяющими отобразить информацию об участии Tg_i в наборах: в схему Tr_i включаются домены, соответствующие элементам данных, входящих в состав селектирующих ключей всех наборов, в которых Tg_i объявлен членом, и селектирующих ключей путей, проходящих через Tg_i . Для Tr_i тип записи Tg_i - базовый.

Пример 13.1.R_j соответствует множеству записей G_j и существует полное групповое отношение s_k G_i ×G_j , < g_i , g_j >, на реляционном уровне - включение в кортеж r_j R_j , соответствующий g_j , атрибутов, содержащих селектирующий ключ, однозначно идентифицированный кортеж r_i R_i , соответствующий записи g_i .

Атрибуты, составляющие селектирующий ключ в r_j , взаимно однозначно соответствуют атрибутам одного из ключей (главного, вторичного) r_i . Для частичных отношений отсутствия связи g_i –>g_j в кортеже r_j R_j значения атрибутов, соответствующих селектирующему ключу, становятся неопределенными.

При отображении схем будут использоваться такие понятия.

1. Скалярные типы данных.

2. Биективное отображение имен типов записей в имена типов отношений.

3. Вводится соответствие имен доменов отношений именам элементов и агрегатов типов записей:

   - первый индекс реляционной схемы - тип отношения;

   - 2 - (m-1) индексы - имена иерархически вложенных отношений;

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

4. Соответствие каждому типу сетевой записи множества селектирующих путей и селектирующих ключей.

5. Первичный (главный) ключ для каждого типа отношений:

   а) если тип записи имеет CALC-ключ без дубликатов, то первичный ключ отношения r составляют атрибуты, соответствующие элементам данных, входящих в CALC-ключ;

   б) если тип записи не имеет такого ключа, но объявлен членом набора s_k с MANDATORY AUTOMATIC (MA), причем в наборе существует расширенный селектирующий ключ, то первичный ключ отношения r составляют атрибуты, соответствующие элементам данных, входящих в расширенный селектирующий ключ;

   в) если правила а) - б) неприменимы, но тип записи n объявлен членом нескольких наборов с классом членства MA, однозначно идентифицируемой по совокупности владельцев, то первичный ключ для отношения r составляют атрибуты, соответствующие элементам данных, входящим в селектирующие ключи в такой совокупности наборов;

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

6. Соответствие имен атрибутов селектирующего ключа именам атрибутов вторичного ключа в парах взаимосвязанных типов отношений. Для каждой пары типов отношений Tr_i и Tr_j , соответствующей типам записей Tg_i и Tg_j таких, что s_k G_i ×G_j определяется состав атрибутов, интерпретирующих селектирующий ключ в Tr_i . Этим атрибутам должны быть поставлены во взаимно однозначное соответствие атрибуты вторичного ключа Tr_i .

Покажем процесс преобразования для сетевой БД, показанной на рис. 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). Поскольку эта процедура достаточно трудоемка в изложении, она здесь не приводится.

Преобразование иерархических моделей данных в реляционные проще и из-за ограниченного объема данной работы не приводится.