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

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

      Проблема оптимизации распределения данных получила достаточно широкое развитие. Этому вопросы посвящена диссертация моего руководителя Телятникова А.О. Он разработал объектную модель динамической оптимизации распределения данных. Идея основана на совместном использовании аппарата генетических алгоритмов и объектной модели РБД. Схема распределения фрагментов данных по узлам РБД кодируется в виде набора хромосом. В процессе оптимизации с помощью операторов ГА генерируются хромосомы, то есть схемы распределения данных. Полученные схемы являются исходной информацией для объектной модели, с помощью которой вычисляются оценки критерия эффективности РБД. Эти оценки, в свою очередь являются значениями целевой функции ГА для данного варианта решения. Входными данными для моделирования и оптимизации является статистика использования запросов и распространения обновлений, а результатом – модифицированная схема распределения данных. В качестве критерия эффективности выбрано минимальное суммарное среднее время выполнения запросов и распространения обновлений.
      Пусть рассматриваемая РБД представляет собой множество фрагментов данных Ф={ф_i,i=1..n}, где n – количество фрагментов данных в системе, которые при помощи репликации и фрагментации распределены на множестве узлов У={У_i,j=1..m}, соединенных множеством каналов передачи данных C={c_k,k=1..N_c}. На узлах функционирует множество приложений П={п_r,r=1..N_п}, которые инициируют выполнение запросов и распространение обновлений. Схема распределения данных в РБД определяется матрицей А, элементы которой принимают следующие значения:

      В процессе функционирования РБД со схемой распределения, представленной матрицей А, порождается множество запросов Q={q_s,s=1..N_q} и множество обновлений U={u_e,e=1..N_u} для элементов которых определенны функции t’(q_s,A) – время выполнения запроса q_i (s=1,,N_s) и t’’(u_e,A) – время распространения обновления u_e (e=1..N_u).
Задача оптимизации РБД сформулирована следующим образом: необходимо найти схему распределения данных, при которой суммарное среднее время выполнения запросов и распространения обновлений, порожденных функционированием системы, минимально:
     Времена выполнения запросов и распространения обновлений вычисляются с помощью объектной модели РБД. Для ее реализации разработаны классы, характеризующие типовые компоненты РБД: узел, канал передачи данных, приложение, запрос. При вычислении критерия оптимальности необходимо учитывать следующие ограничения:

1. В РБД должны присутствовать хотя бы одна копия данных:
   
2. Суммарный объем данных, хранящихся на узле, не должен превышать общее дисковое пространство данного узла:
   где L_i – объем i-гo фрагмента данных, i=1..n; D_j – дисковое пространство j-го узла, j=1..m.
3. Максимальное время выполнения запросов не должно превышать заданного предельного значения:
   где t_пр – предельно допустимое время выполнения запросов.

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

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

      Рассмотрим распределенную базу данных, состоящую из m узлов S_i (i = 0..m-1), каждый из узлов имеет свою производительность, объем памяти, и локальную базу данных. Соединение между двумя узлами S_i и S_i' характеризуется целочисленной положительной переменной c_ii’ которая ассоциируется с затратами на передачу данных от узла S_i к узлу S_i'. Пусть существуют q = {q₀, q₁, … q_n-1} – наиболее часто применяемые запросы. a_ix – частота, с которой запрос qx_x выполняется на узле S_i. Частота выполнения n запросов с m узлов может быть представлена с помощью матрицы А размером (m*n). В РБД существует k фрагментов данных {O₀, O₁, .. O_k-1}.

      В модели рассмотрены два вида затрат на передачу данных. Первый тип затрат основан на перемещении данных из узла размещения на узел, инициирующий запрос. В этом случае размер фрагмента данных, запрощиваемых с каждого узла, не изменяется с расположением фрагментов данных и нет зависимости между доступными запросу фрагментами данных. r_xj - размер фрагмента данных O_j которые нужно передать на узел, где запрос q_x инициирован, в результате получим матрицу R размером (n*k). Запрос q_x инициируется на сайте S_i a_ix раз за определенный временной интервал. ТОгда U – матрица размером (m*k), где u_ij – количество данных, которые нужно передать с узла, где расположен фрагмент данных O_j на узел S_i где запрос был инициирован:

      Второй тип затрат появляется когда данные с узла, где расположен один из фрагментов, передаются туда, где расположен второй фрагмент. Данные передаются в порядке выполнения бинарных операций, объединяющих два или более фрагментов данных. В данном случае количество данных фрагмента, запрошщиваемых с каждого сайта, зависит от расположения остальных фрагментов данных. Пусть d_jj' определяется как размер данных из фрагмента O_j который нужно передать на узел, где расположен фрагмент O_j', чтобы выполнить определенную бинарную операцию, получим матрицу передачи D размером (k*k). Она зависит от запроса, который должен быть обработан, то есть для каждого запроса мы должны знать информацию о том, какое количество данных нужно передать от узла, где расположен один фрагмент, на узел с другим фрагментом, при этом оба фрагмента данных должны быть доступны для выполнения запроса. Пусть z_jj’^x – размер данных узла Oj_j, которые нужно передать на узел O_j’ для выполнения запроса q_x, получим матрицу Z^x. Количество данных, которые нужно передать с узла O_j на узел O_j' равно:

      Пусть site(O_j) – это узел где расположен фрагмент данных O_j. Тогда, общие затраты на передачу равны:

В этой формуле первое слагаемое означает затраты на передачу данных чтобы обработать бинарные операции между фрагментами данных, расположенными на различных узлах. Второе слагаемое представляет собой затраты на передачу данных чтобы передать результаты бинарных операций фрагментов данных на узел, где запрос был инициирован. Задача распределения данных состоит в минимизации t, изменяя значение site(O_j).

      Итак, в модели учитываются два вида затрат на передачу данных. Это связано с применением в СУБД разных стратегий оптимизации распределенных запросов. Таким образом, в зависимости от особенностей конкретной СУБД можно учитывать тот или иной вид затрат. Но модель имеет и недостатки: она не учитывает наличие механизма обновлений. Однако то, что она рассматривает особенности функционирования конкретной СУРБД, позволит получить схему распределения данных, более точно соответствующую реальной среде. Таким образом, для исследвоания была выбрана модель, предложенную И.Ахматом. Применение этой модели, учитывающей особенности функционирования конкретной СУБД, позволит получить оптимальную схему распределения. В качестве среды выбираем СУБД Oracle. Для адаптации исходной модели к выбранной СУБД требуется изучить особенности реализации распределенных запросов и распространения обновлений в СУРБД Oracle.

1. Модели обладают рядом допущений и ограничений, которые делают невозможным их применение при анализе и оптимизации работы реальной РБД.
2. Ранее применявшиеся методы оптимизации РБД – метод ветвей и границ, метод последовательных и пороговых улучшений и др., также не могут дать положительных результатов при оптимизации, так как их использование ограничено в связи с большой размерностью задачи распределения множества фрагментов данных по узлам компьютерной сети.
3. Целесообразно применение эволюционных методов для решения задачи оптимизации распределения данных.
4. Для решения задачи в модели оптимизации нужно учесть наличие механизма обновлений и фрагментации в РБД, а также особенности реализации распределенных запросов в конкретной СУБД.

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

1. Изучить особенности реализации РБД с использованием СУБД Oracle.
2. Модифицировать модели распределенной базы данных.
3. Модифицировать генетический алгоритм для решения задачи оптимизации
4. Провести эксперименатальные исследования

1. Цегелик Г.Г. Системы распределенных баз данных. – Львов: Свит, 1990. – 168 с.
2. Т.Коннолли, К.Бегг. Базы данных: проектирование, реализация и сопровождение. Теория и практика. – М., 2000. – 1120 с.
3. Телятников А.О. Разработка объектной модели распределенной базы данных// Наукові праці ДонНТУ. Випуск 74. – Донецьк, ДонНТУ, 2004. – с. 192 – 200.
4. I. Ahmad, K. Karlapaem. Evolutionary Algorithms for Allocating Data in Distributed Database Systems//
   http://ranger.uta.edu/~iahmad/journal-papers/[J39]%20Evolutionary%20algorithms%20for%20allocating%20data.pdf
5. Распределенные и параллельные системы баз данных. Системы управления базами данных, #04/1996 - http://www.osp.ru/dbms/1996/04/4.htm