Лекция 11. Создание РБД

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

РБД состоит из связанных локальных баз данных (ЛБД). Возможны два варианта создания РБД: проектирование РБД "с нуля"; объединение (интеграция) уже готовых ЛБД. В первом варианте модели данных ЛБД, как правило, одинаковы (однородные ЛБД), во втором модели данных могут быть различны (неоднородные ЛБД).

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

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

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

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

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

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

В качестве критериев проектирования РБД могут быть [16]: 1) минимум объема пересылаемых данных и сообщений; 2) минимум стоимости трафика; 3) минимум общего времени, необходимого для обслуживания запросов к БД.

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

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

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

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

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

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

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

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

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

Рис. 11.1. Проблемы РБД

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис. 11.2. Схема фрагментации и локализации данных

Обозначим узлы через, а приложения – через . Если имеется отношение г со схемой R, то в узле j имеется отношение-фрагмент. Если в узле j имеется к тому же копия фрагмента,, то обозначим ее через. Тогда схема фрагментации и локализации может быть представлена в виде, показанном на рис. 11.2.

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

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

где ; m – число записей в горизонтальном фрагменте.

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

Воспользуемся обозначениями, введенными в данной главе. Пусть – частота активизации приложения к в узле); rкi. – число ссылок поиска приложения k во фрагменте i;– число ссылок обновления данных приложения к во фрагменте i;

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

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

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

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

(11.1)

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

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

(11.2)

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

Шаг 3. Используем метод "добавочного копирования". Пусть dj – степень избыточности Ri; Fi – выгодность размещения копии в любом узле РБД иМодифицируя выражение

(11.2), получим

(11.3)

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

Пусть схема Rs декомпозирована на 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, то появится еще одна удаленная ссылка.

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

(11.4)

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

Введем обозначения:– независимые файлы-данные; – узлы; L. – объем файла; Ь. – объем памяти узла (для файлов); dsj– коэффициенты, учитывающие расстояние между узламии;– стоимость передачи;– интенсивность запросов к файлу i из узла j;– интенсивность корректировки сообщений;– объем запросов к файлу i из узла j;– объем запрашиваемых данных при выполнении запроса i из узла j;

Тогда объем данных, поступающих в узел), содержащий файл i, при выполнении запроса к этому файлу с учетом интенсивности равен, а объем данных, составляющих запросы и ответы,

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

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

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

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

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