Модификация запросов в распределенных БД.

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

Например, запрос: должен вычисляться на рабочей станции 1, хранится там же, а хранится на рабочей станции 2. Из п.1 в п.2 можно послать требование передать всё отношение или, что более разумно, если велико, передать в п.2 условие выбора ; а результат выбора передать в п.1.

В распределенных БД используют:

1) операцию полусоединение;

2) фрагментирование отношения, т.е. отношение, разбитое на фрагменты, хранящиеся в разных местах.

 

Пусть и – два отношения. Полусоединением и назовем отношение , которое будем обозначать . Таким образом, – это часть , которая соединена с .

Они используются для эффективного выполнения запроса.

 

Пример:

хранится в п.1, – в п.2. Нужно вычислить в п.1.

1-й способ: передать в п.1 – всего 24 значения.

2-й способ: сначала вычислить в п.1 и послать в п.2; затем вычислить и послать в п.1. Затем вычислить как .

Итого 6+9=15 значений вместо 24.

 

Воспользуемся свойствами операций РА:

Т.е. для вычисления нужно знать только .

Свойство полусоединения:

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

Пример: Вычислить: в п.3.

распределены по трем п. 1,2,3.

1) п.1: ;

2) п.2;

3) п.2: ;

4) п.3;

5) п.3:

.

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

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

.

Пример:

 

Пусть задана БД . Последовательностью полусоединений SP для называется отношение , которое получено в результате выполнения операций: .

Пусть означает конечное значение после применения SP к .

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

Независимо от того, производит SP полную редукцию или нет, .

 

Фрагменты отношений.

Отношения в распределенных БД не обязательно хранятся полностью в одном пункте. Кортежи любого отношения могут быть разбросаны по разным пунктам. Иногда один и тот же кортеж хранится в нескольких местах.

Фрагментами отношения называются кортежи отношения, размещенные в каждом из пунктов.

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

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

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

Знание схемы фрагментации может помочь при обработке запроса. Пусть необходимо вычислить в заданном пункте. Можно выслать требование на для каждого фрагмента , который не хранится в данном пункте. Однако при – назад ничего не вернется. Поэтому нужно требовать только те , для которых .

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

Пример:

– данная схема фрагментации является допустимой.

Предположим, что нужно вычислить , где . Какие фрагменты нужно вызывать?

Фрагмент вызывать не нужно, т.к.

– нет

– нет

– да остается и .

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