На правах рекламы:
ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Авторитетность издания

ВАК - К1
RSCI, ядро РИНЦ

Добавить в закладки

Следующий номер на сайте

4
Ожидается:
09 Сентября 2024

Метод автоматизации проектирования распределенной реляционной базы данных

Статья опубликована в выпуске журнала № 3 за 2008 год.
Аннотация:
Abstract:
Автор: Новосельский В.Б. () -
Ключевые слова: реляционная бд, проектирование, фрагментация, генетические алгоритмы
Keywords: relational database, design, , genetic algorithm
Количество просмотров: 15576
Версия для печати
Выпуск в формате PDF (2.59Мб)

Размер шрифта:       Шрифт:

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

 

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

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

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

Фрагментация описывает разбиение отношений в БД. Разбиение отношений на минимальные, не делимые далее фрагменты позволит разместить их с максимально возможной гибкостью. Для получения такого набора фрагментов для каждого отношения R на основании транзакций определяется набор минтерм предикатов и группы атрибутов. Причем предикаты описывают применение ГФ, а группы атрибутов – ВФ. Группы атрибутов получаются разбиением множества атрибутов, используемых в транзакциях.

В [1] доказано, что набор минтерм предикатов обладает свойствами полноты и достаточности. По определению, для групп атрибутов эти свойства очевидны. Таким образом, описанная фрагментация обладает свойствами полноты и восстанавливаемости.

Схема размещения указывает местоположение фрагментов. Она описывается матрицей D, строками которой являются узлы ВС, а столбцами – сформированный набор фрагментов. Единица в ячейке матрицы Di,j означает наличие фрагмента i в узле j. Для удовлетворения свойства полноты схемы размещения каждый фрагмент должен находиться хотя бы в одном узле (в каждой колонке должна быть хотя бы одна единица).

При исполнении реляционного запроса необходимо принять следующие решения.

1.   В какой последовательности производить операции соединения.

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

3.   Применять ли технику semi-join при соединении. Идея semi-join состоит в отправке на узел 2 колонок отношения A, по которым осуществляются соединение, нахождение и отправка на узел 1 только тех записей из B, которые удовлетворяют условию соединения. Как правило, техника semi-join позволяет получить выигрыш в случае, когда отношение B содержит «тяжелые» колонки, например, мультимедийную информацию.

4.   Применять ли технику double-pipelined hash join. Идея double-pipelined hash-join состоит в формировании двух хэш-таблиц Ha и Hb, после чего записи из A и B обрабатываются по одной в каждый момент. Для записи из A в Hb ищутся соответствующие записи, после чего запись из A и найденные записи из B возвращаются как результаты соединения и запись из A помещается в хэш-таблицу Ha. Далее берется запись из B и обрабатывается аналогичным образом.

5.   Какие узлы, имеющие необходимые фрагменты, использовать при внутриоператорном параллелизме.

Все задачи, входящие в процесс проектирования РаБД, NP-полные. Во многих работах отмечается, что для решения задач кластеризации и компоновки наиболее успешно применяются генетические алгоритмы (ГА), в основу которых положены идеи естественного отбора в биологических популяциях. В ГА любое решение задачи синтеза представляется хромосомой, состоящей из генов. Значениями генов являются значения проектных параметров. Направленный перебор решений осуществляется с помощью генетических операторов выбора родителей, скрещивания, мутации, селекции, переупорядочения. Помимо NP-полноты, задачи проектирования РаБД обладают свойством взаимозависимости, то есть входными данными для следующей задачи является решение предыдущей. Таким образом, для получения проекта РаБД, близкого к оптимальному, целесообразно применять вложенные ГА.

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

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

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

Для оценки качества предложенного алгоритма был проведен эксперимент, в котором решения, найденные с помощью ГА, сравнивались с оптимальными решениями, полученными полным перебором. Использовался следующий критерий эффективности:

где k – количество узлов ВС; n – количество запросов; fij – частота возникновения j-го запроса в i-м узле; Qij – временной коэффициент j-го запроса, порожденного в i-м узле; Wij – коэффициент использования ресурсов при обработке j-го запроса, порожденного в i-м узле; ct и ca – коэффициенты важности времени ответа и готовности транзакции, лежат в пределах от 0 до 1. Значения коэффициентов определяются проектировщиком на основании требований к РаБД.

Временной коэффициент j-го запроса определяется как Qij=Tijd/Tijl, то есть равен отношению времени ответа на запрос, исполненный в РаБД, к расчетному времени ответа на запрос, исполненный локально в узле i при условии наличия в нем всех необходимых фрагментов. Коэффициент использования ресурсов равен сумме коэффициентов использования ЦП и ВЗУ узлов, вовлеченных в операцию, и коэффициента использования СР.

Эксперимент проводился для следующей конфигурации: ВС состоит из 3 узлов, равноудаленных друг от друга; логическая схема БД имеет 2 отношения; производится 3 запроса на выборку и 2 запроса на обновление данных, которые формируют 4 группы атрибутов и 5 предикатов.

Измерения показали, что оптимальные зна- чения для параметров ГА лежат в пределах, приведенных в таблице 1. Запуск алгоритма с другими значениями параметров ухудшает качество результата или увеличивает время работы.

Таблица 1

Оптимальные параметры ГА

Параметр

Внешний алгоритм

Внутренний алгоритм

Размер популяции

25¸35

100¸110

Вероятность скрещивания

0,45¸0,70

0,55¸0,65

Вероятность мутации

0,0075¸0,0100

0,0075¸0,0100

Схождение популяций, при котором 90 % лучших особей имеют расхождение в значении функции приспособленности не более 10 %, наблюдалось примерно после 500¸700 поколений внешнего ГА и 2500¸3000 поколений внутреннего ГА. Были промоделированы различные соотношения скорости передачи данных по сети (R) к скорости чтения данных в узле (S) и различные коэффициенты важности времени ответа и готовности транзакции в целевой функции. В таблице 2 приведены результаты моделирования.

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

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

Таблица 2

Зависимость эффективности проекта и степени репликации от физических характеристик ВС и коэффициентов целевой функции

ct

ca

R/S

Коэффициент эффективности

Коэффициент репликации, %

0,8

0,2

0,02

11,8906

11,1

0,20

4,7802

40,7

0,50

3,0189

62,9

0,5

0,5

0,02

10,0965

7,4

0,20

8,1905

25,9

0,50

5,4902

48,1

0,2

0,8

0,02

6,1310

3,7

0,20

7,0896

7,4

0,50

8,5664

11,1

Алгоритм был реализован на языке C#. Время работы алгоритма на компьютере Intel Pentium Core2 2Ггц приведено в таблице 3. Для 3 узлов и 9 фрагментов был произведен поиск оптимального решения методом полного перебора, для большего числа узлов и фрагментов время полного перебора значительно возрастает, поэтому оно было оценено аналитически.

Таблица 3

Время работы ГА и поиска полным перебором

Количество узлов

Количество атрибутов и предикатов

Время поиска полным перебором (Tf)

Время работы ГА (Tg)

Ускорение (Tf/Tg)

3

9

2 часа 9 мин.

13 мин. 2 сек.

8

10

14 часов 5 мин.

14 мин. 6 сек.

58

11

4 дня 15 часов

17 мин. 12 сек.

391

4

9

16 часов 2 мин.

22 мин. 12 сек.

43

10

5 дней 12 часов

25 мин. 3 сек.

313

11

1 месяц 19 дней

28 мин. 5 сек.

2564

5

9

11 дней 5 часов

35 мин. 43 сек.

456

10

2 месяца 25 дней

40 мин. 18 сек.

3087

11

1 год 5 месяцев

44 мин. 8 сек.

16949

Время поиска оптимального решения полным перебором с увеличением числа фрагментов растет экспоненциально, в то время как время работы ГА увеличивается квадратично.

Таким образом, предложенный ГА позволяет получить оптимальное или близкое к оптимальному решение задачи в рамках используемой модели, обеспечивая квадратичный рост времени работы с увеличением пространства возможных решений.

В дальнейшем возможно расширение модели РаБД за счет интеграции различных способов распространения обновлений [2], что позволит проектировщику приблизить модель к реальной вычислительной среде. Также необходимо дальнейшее исследование зависимости скорости схождения популяций от параметров ГА.

Список литературы

1.  Ceri S., Negri M., Pelagatti G. Horizontal data partitioning in database design. // ACM SIGMOD international conference on Management of data. Orlando, Florida. – 1982. – pp. 128–136.

2.  Стеен М., Тенебаум Э. Распределенные системы. Принципы и парадигмы. – СПб: Питер, 2003. – 880 с.


Постоянный адрес статьи:
http://swsys.ru/index.php?page=article&id=1578
Версия для печати
Выпуск в формате PDF (2.59Мб)
Статья опубликована в выпуске журнала № 3 за 2008 год.
Статья находится в категориях: Система автоматизированного проектирования (САПР), Системы управления базами данных (СУБД)
Статья относится к отраслям: Вычисления

Возможно, Вас заинтересуют следующие статьи схожих тематик: