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

Чертовской В.Д.


         

Базы и банки данных

Учебное пособие


Чертовской В.Д.
Базы и банки данных
Начало
Печатный оригинал
Об электронном издании
Оглавление

Введение

Часть 1. ОСНОВНЫЕ ПОЛОЖЕНИЯ

Раздел 1. Основные понятия

1.

Глава 1. Общие сведения

1.1.

Данные, информация, знания

1.2.

Основные понятия и определения

1.3.

Классификация БД и СУБД

1.4.

Состав СУБД и работа БД

2.

Глава 2. Концепция баз данных

2.1.

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

2.2.

Концепция построения БД

2.3.

Методология проектирования баз данных

2.4.

Методология использования баз данных

Раздел 2. Теория баз данных

3.

Глава 3. Общая теория

3.1.

Модели представления данных

3.2.

CASE-технология

3.3.

CASE-средства

4.

Глава 4. Теория реляционных баз данных

4.1.

Математические основы теории

4.2.

Построение БД

4.3.

Использование БД

4.3.1.

Запросы к данным

4.3.2.

Синхронизация процессов доступа

Часть 2. Централизованные базы данных

Раздел 3. Реализация бд (модели БД)

5.

Глава 5. Реляционные БД SQL

5.1.

Логическая структура

5.2.

Создание БД

5.3.

Использование БД

5.3.1.

Язык SQL

5.3.2.

Язык QBE

6.

Глава 6. Сетевые БД

6.1.

Логическая структура

6.2.

Программная реализация

6.2.1.

Создание БД (ЯОД)

6.2.2.

Использование БД (ЯМД)

7.

Глава 7. Иерархические БД

7.1.

Логическая структура

7.2.

Программная реализация

7.2.1.

Создание БД (ЯОД)

7.2.2.

Использование БД (ЯМД)

8.

Глава 8. Взаимосвязь МД

8.1.

Сравнительная характеристика моделей данных

8.2.

Преобразование моделей данных

8.3.

Выбор моделей данных

9.

Глава 9. Физическая БД

9.1.

Вопросы программной реализации БД

9.2.

Организация хранения и доступ

9.3.

Доступ к данным и их обновление

Раздел 4. Современные направления развития БД

10.

Глава 10. Автоматизация проектирования

10.1.

Классический подход к проектированию

10.1.1.

Однопользовательский режим

10.1.2.

Многопользовательский режим

10.2.

Современный подход к проектированию

10.3.

Автоматизация проектирования

11.

Глава 11. Объектно-ориентированные базы данных

11.1.

Недостатки реляционных баз данных

11.2.

Состояние развития ООБД

11.3.

Сущность ООБД

11.4.

Недостатки и перспективы развития ООБД

Часть 3. Распределенные базы данных (РБД)

Раздел 5. Основы теории РБД

12.

Глава 12. Общая характеристика РБД

12.1.

Новые требования, предъявляемые к БД

12.2.

Состав и работа РБД

12.3.

Система клиент/сервер

Раздел 6. Основы теории РБД

13.

Глава 13. Создание РБД

13.1.

Обеспечение целостности

13.2.

Фрагментация и локализация

13.3.

Процесс интеграции

13.4.

Преобразование структуры и данных

13.5.

Однородные и неоднородные РБД

14.

Глава 14. Использование РБД

14.1.

Одновременный доступ

14.2.

Защита

14.3.

Восстановление РБД

14.4.

Запросы

Заключение

Контрольные вопросы

Литература

Указатели
11  именной указатель
360  предметный указатель
163  указатель иллюстраций
25  указатель компаний

Раздел 6. Основы теории РБД

13.
Глава 13. Создание РБД

13.1.
Обеспечение целостности

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

13.2.
Фрагментация и локализация

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

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

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

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

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

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

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

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

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

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

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

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

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

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

,

где 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 - узлы.

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

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

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

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

  4. Если имеется приложение П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, аРис. 13.03. Интеграция однородных (а) и неоднородных (б) локальных БД) и неоднородными (рис. 13.3, бРис. 13.03. Интеграция однородных (а) и неоднородных (б) локальных БД).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пусть A1 и B1 - состояния системы (например, в прямоугольных координатах), а f1 - функция преобразования состояния системы. Пусть A2 , B2 и f2 описывают ту же систему (например, в полярных координатах). Пусть j - правило преобразования одной системы координат в другую. Для этого случая в строгих алгебраических исследованиях показано, что преобразование верно, если диаграмма на рис. 13.4Рис. 13.04. Коммутативная диаграмма коммутативна, т.е. выполняется условие

f2 ґj=ґjf1 , (13.5)

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

Можем полагать, что A1 и A2 - исходные таблицы Система управления базы данныхСУБД с разными в общем случае моделями данных, к которым осуществляется запрос; B1 и B2 - результаты операций обновления или запроса; f1 и f2 - правила получения данных (Язык описания данныхЯОД или Язык манипулирования даннымиЯМД или Язык запроса); j - правила перехода (по данным) из одной БД в другую.

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

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

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

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

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

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

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

13.4.
Преобразование структуры и данных

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

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

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

    Mi –>Mв –>Mj ,

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

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

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

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

    Msi : Si –>Bi .

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

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

  4. При работе с БД используется ЯМД ЯМ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 .

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

  1. Введем операторы σ: Si –> ; Ψ: Bi –>Bj . Тогда должна быть коммутативна диаграмма на рис. 13.5, a,b Рис. 13.05. 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 (преобразование типов) должно быть биективно.

  2. Обеспечение интерпретируемости предполагает, что реализация программы PROGi (или оператора oi ) на ЯМД Mi эквивалентна реализации программы PROGj на ЯМД Mj , т.е. коммутативна диаграмма на рис. 13.5, c.Рис. 13.05. c) Коммутативные диаграммы ЯОД и ЯМД

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

  3. Говорят, что функция 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.Рис. 13.06. Соотношение операторов и процедур моделей данных

Назовем набор операторов oi в ЯМД Mi функционально полным (ФП), если для любого начального состояния bi "Bi произвольной БД со схемой Si можно задать последовательность операций progi , переводящую БД в произвольное заданное состояние bi "Bi , удовлетворяющее схеме Si .

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

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

13.5.
Однородные и неоднородные РБД

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

Пусть имеет место строгое соответствие Msi .s = Ψ.Msj . При переходе к произвольной модели Mk (рис. 13.7)Рис. 13.07. Соотношение локальных баз данных из-за Ψ≠ 1 должно быть Msi .s = Ψ.Msk . Если сохранить y (что желательно), то семантика Язык описания данныхЯОД Mi должна быть очень богатой.

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

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

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

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

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

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

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

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

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

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

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

  2. Совмещение синтаксиса операторов Oji ЯМД Mji с синтаксисом операторов Oj путем изменения семантики.

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

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

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

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

  2. Отображается ЯОД Mi в Mj при инъективных операторах Ψ: Bi –>Bj и проверяется коммутативность диаграмм описания схем.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблица 13.5.

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

Размещение Пояснение Отключение Включение
CALC <ключ>
VIA <имя><имя> SET
DIRECT
SYSTEM

INDEX
Хеширование
Хранение записей рядом
Работа программиста
По умолчанию, сингулярные записи
Используется редко
МANDATORY - обязательное уничтожение

OPTIONAL - необязательное уничтожение, передача SYSTEM
AUTOMATIC - автоматическое


MANUAL - ручное, от SYSTEM

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

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

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

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

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

  2. Для любой связи 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 - отдельным отношением связи.

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

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

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

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

    б) для любого подмножества атрибутов (исключая первичный ключ в Ri ), если это подмножество представляет собой в Ri первичный ключ, принадлежащий ρ - α (подмножество является внешним ключом), добавить связь Lij между типами записи Ni , соответствующей Ri , и Nj , соответствующей Rj , где внешний ключ есть первичный ключ.

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

  3. Присвоить связи 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 . Внутренней идентификации может и не быть. Идентификация таких групп возможна введением нескольких внешних идентификаторов.

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

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

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

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

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

Селектирующим ключом родительской записи Tgi в групповом отношении sk является неизбыточная совокупность ЭД, входящих в состав Tgi и таких, что конкретный набор их значений позволяет однозначно идентифицировать gi среди всех других множеств Gi в БД. Селектирующий ключ связывается с типом группового отношения Tsk и обозначается Csk . Для псевдоключа Psk , селектирующего пути Ws селектирующих ключей Csk , Esk в групповом отношении sk , имеются ограничения.

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

    < >.

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

Если в состав пути 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) текущего состояния Д.

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

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

  2. Любой тип записи 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 значения атрибутов, соответствующих селектирующему ключу, становятся неопределенными.

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

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

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

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

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

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

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

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

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

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

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

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

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

  6. Соответствие имен атрибутов селектирующего ключа именам атрибутов вторичного ключа в парах взаимосвязанных типов отношений. Для каждой пары типов отношений Tri и Trj , соответствующей типам записей Tgi и Tgj таких, что sk Gi ×Gj определяется состав атрибутов, интерпретирующих селектирующий ключ в Tri . Этим атрибутам должны быть поставлены во взаимно однозначное соответствие атрибуты вторичного ключа Tri .

Покажем процесс преобразования для сетевой БД, показанной на рис. 13.9.Рис. 13.09. Сетевая база данных Ее характеристики представлены в табл. 13.7 и 13.8Таблица 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.9 и 13.10Таблица 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)Рис. 13.05. a), b) Коммутативные диаграммы ЯОД и ЯМД. Поскольку эта процедура достаточно трудоемка в изложении, она здесь не приводится.

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

© Центр дистанционного образования МГУП