Рис. 2. Иллюстрация пе-
ресечения
В параллельных БД нефрагментированная
по атрибуту соединения таблица пересылает-
ся другим узлам и используется во внешнем
цикле. Поскольку оператор exchange работа-
ет покортежно [15], передавать битовые мас-
ки нельзя и для обоих отношений необходимо
использовать раннюю материализацию.
Если оба отношения фрагментированы по
атрибуту соединения, то для внешнего отношения возможны поздняя
материализация и обработка с помощью битовых масок.
Преобразование Лапласа–Стилтьеса времени соединения двух
таблиц.
Ниже получены преобразования Лапласа–Стилтьеса (ПЛС)
времени соединения таблиц
A
и
B
в параллельной системе баз дан-
ных в соответствии с планом
π
A
(
σ
F
A
(
A
))
. / π
B
(
σ
F
B
(
B
))
и услови-
ями поиска (фильтрации) в исходных таблицах
F
A
=
f
A
0
∩
|
K
AF
|
T
i
=1
f
Ai
,
F
B
=
f
B
0
∩
|
K
BF
|
T
i
=1
f
Bi
, где
π
— операция проекции,
σ
— операция селек-
ции,
./
— операция естественного соединения подзапросов;
f
А
i
(
f
В
i
)
— элементарное условие поиска по
i
-му атрибуту таблицы
A
(
B
),
например
a
i
>
5
;
K
AF
(
K
BF
) — множество таких атрибутов таблицы
A
(
B
)
, на которые накладываются элементарные условия поиска;
f
А
0
(
f
В
0
) — условие поиска, которое включает в себя сравнение разных
атрибутов таблицы
A
(
B
)
, например
a
i
> a
j
.
Преобразования Лапласа–Стилтьеса позволяют оценивать не толь-
ко математические ожидания случайных величин, но и моменты более
высоких порядков, например дисперсию. Предполагается, что записи
таблиц фильтруются и соединяются по неиндексированным атрибу-
там (т.е. рассматривается наихудший случай). Также предполагается,
что таблица
B
фрагментирована по атрибуту соединения, а таблица
A
— нет. Преобразование Лапласа–Стилтьеса получено для метода
NLJ (соединение с помощью вложенных циклов). Введем следующую
функцию для
i
-го узла:
V
Ai
(
s, Z
) =
G
A
i
(
χ
1
(
s, r
1
, m
1
)
∙
Ψ
A
1
(
s, Z
))
,
(1)
где
G
A
i
(
z
) =
z
V
A
n
(2)
— производящая функция числа записей исходной фрагментированной
таблицы
A
(не по атрибуту соединения), обрабатываемых в
i
-м про-
цессоре (узле);
V
A
/n
— число записей таблицы
A
, которые хранятся
в
i
-м узле;
n
— число узлов; функция
Ψ
A
1
(
s, Z
)
учитывает, что чита-
ются кортежи колонок по позициям, которые удовлетворяют условиям
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012. № 4 85
