поиска по предыдущим атрибутам, она рекуррентно определяется сле-
дующим образом:
Ψ
A
1
(
s,
Z) = Ω(
P
Af
1
, χ
2
(
s, r
2
, m
2
)
∙
Ψ
A
2
(
s, Z
))
,
(3)
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Ψ
A
i
(
s,
Z) = Ω(
P
Af
i
, χ
i
+1
(
s, r
i
+1
, m
i
+1
)
∙
Ψ
A
(
i
+1)
(
s,
Z))
,
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Ψ
A
b
(
s, Z
) = Ω(
P
Af
b
, φ
u
A
P
(
s
)
∙
Ω(
P
AT
,
Ψ
Aπσ
(
s
)
∙
q
Ain
(Z)));
Z
= (
z
1
, . . . , z
n
);
(4)
Ω(
P, z
) = 1
−
P
(1
−
z
)
;
(5)
b
=
|
K
AF
|
— число атрибутов отношения
A
, по которым происходит
фильтрация кортежей по условию
|
K
A F
|
T
i
=1
f
A
i
;
Ψ
Aπσ
(
s
) =
|
K
A F
|
+
|
K
Aπ
|
+
|
K
Aσ
|
Y
j
=
|
K
A F
|
+1
χ
j
(
s,
1
, m
j
)
(6)
— ПЛС времени чтения значений из колонок по значениям позий (т.е.
по смещению);
K
Aπ
— подмножество атрибутов отношения
А
, которые
участвуют в операции проекции и не присутствуют в множестве
K
A
F
;
K
A
σ
— подмножество атрибутов отношения
А
, которые участвуют в
операции соединения и не присутствуют в множестве
K
A
π
;
χ
i
(
s, r, m
) =
φ
Di
(
s
)
φ
mν
i
M
(
s
)
φ
r
P
(
s
);
(7)
φ
D
i
(
s
)
— ПЛС времени чтения кортежа
i
-го столбца с диска;
φ
mν
i
M
(
s
)
—
ПЛС времени сохранения атрибута в оперативной памяти (ОП) и его
чтения в кэш процессора;
ν
i
— размер атрибута;
m
— число циклов
чтения/записи в ОП (на байт), необходимых для проверки условия по
соответствующему атрибуту (для
i
-го столбца вводится аргумент
m
i
—
см. (1), (3));
φ
r
P
(
s
)
— ПЛС времени обработки кортежа столбца в про-
цессоре,
r
— число логических операций, необходимых для проверки
условия по соответствующему атрибуту (для
i
-го столбца вводится
аргумент
r
i
— см. (1), (3));
χ
j
(
s,
1
, m
j
)
— ПЛС времени чтения корте-
жа
j
-го столбца проекции (или селекции) с диска в кэш процессора
и обработки в нем (см. (6)); 1 означает, что в процессоре проверяет-
ся только значение битовой маски в соответствующей позиции;
u
A
—
число логических операций процессора, необходимых для проверки
условия
f
A
0
;
P
AT
— вероятность того, что сформированный кортеж
удовлетворяет условию
f
A
0
;
q
Ain
(
z
1
, . . . , z
n
)
— производящая функция,
86 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012. № 4
