38
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
4.
Алгоритм Лемпеля — Зива — Велча.
Данный алгоритм при
сжатии (кодировании) динамически создает таблицу преобразования
строк: определенным последовательностям символов (словам) ста-
вятся в соответствие группы бит фиксированной длины (обычно 12-
битные).
В работе [17] предлагается полученный эмпирическим путем ал-
горитм выбора типа компрессии данных в столбцах.
Преобразования Лапласа
—
Стилтьеса (ПЛС) времени вы-
полнения запроса к одной таблице в строчной и колоночной си-
стеме баз данных.
В работе [8] приведено ПЛС времени выполнения
запроса к строчной базе данных с планом
π
A
(
σ
F
(
R
)),
π
—
операция
проекции,
σ
—
операция селекции:
1/
2
( )
(
( ) ( )(1 (1 ( ))) ( )),
L
D M
F
N
P
s G s
s
P
s
s
ϕ
ϕ
ϕ
ϕ
ϕ
=
− −
(1)
где
/
V n
G z
=
—
производящая функция числа записей фрагментной
таблицы
R
,
обрабатываемых на одном процессоре;
V
—
общее число
записей в таблице
R
;
n
—
число процессоров (или персональных
компьютеров в кластере);
( )
D
s
ϕ
—
ПЛС времени чтения блока БД
фрагментированной таблицы с диска (с учетом очереди к дисковому
массиву);
L
—
число записей таблицы в блоке БД;
( )
M
s
ϕ
—
ПЛС
времени чтения/сохранения записи фрагментированной таблицы в
оперативной памяти (с учетом очереди к шине памяти);
( )
N
s
ϕ
–
ПЛС
времени межпроцессорного обмена при передаче результирующей
записи по сети
N
;
( )
P
s
ϕ
—
ПЛС времени обработки записи в процес-
соре, который является неразделяемым ресурсом;
P
F
—
вероятность,
что запись удовлетворяет условию поиска
F
(
эту вероятность рассчи-
тывают по формулам [6]).
В работе [8] приведены формулы для
( )
D
s
ϕ
,
( )
M
s
ϕ
,
( )
N
s
ϕ
(
т. е.
для ПЛС времени обработки кортежей в ресурсах) для различных
режимов функционирования системы баз данных и различных архи-
тектурных решений.
Используя подход, предложенный в работе [4], в работе [12] ав-
торами получено ПЛС времени выполнения запроса к колоночной
базе данных с планом
π
A
(
σ
F
(
R)) и условием
0
1
,
F
K
i
i
F f
f
=
= ∩
∩
где
f
i
—
элементарное условие поиска по
i
-
му атрибуту таблицы
R
,
например
a
i
> 5;
K
F
—
множество таких атрибутов таблицы
R
,
на ко-
торые накладываются элементарные условия поиска;
f
0
—
условие
поиска, которое включает сравнение разных атрибутов таблицы
R
,
например
a
i
>
a
j
.