производящая функция числа записей в таблице
R
i
,
V
i
— прогнозиру-
емое число записей в этой таблице,
p
i
=
⎧⎪⎨
⎪⎩
1
,
для
i
= 1;
1
I
i
4
,
для
i
= 2
, n,
,
(3)
I
i
4
— прогнозируемая мощность атрибута Ai4 (число разных значе-
ний),
H
n
+1
(
z
)
≡
1
.
Доказательство.
Из описания процесса реализации плана (см.
рис. 2,
а
) следует, что число записей, обработанных на
i
-м уровне вло-
женности, определяется селекцией
σ
A
i
4
=
a
, где
a
— значение атрибута
A
i
−
1
,
3
записи (
i
−
1)
-го уровня (
i
= 2
, n
)
. Для
i
= 1
селекция отсут-
ствует. Из работы [2] (см. формулу (2.25)) следует, что вероятность
записи таблицы, удовлетворяющей условию
σ
A
i
4
=
a
, равна
p
i
=
1
I
i
4
,
i
= 2
, n
; для
i
= 1
p
1
= 1
, так как селекция отсутствует.
Используя формулу (2.20) из работы [2], получим, что ПФ
H
∗
i
(
z
)
числа записей, обработанных только на
i
-м уровне вложенности для
каждой записи (
i
−
1)
-го уровня равна
H
∗
i
(
z
) =
G
i
(1
−
p
i
(1
−
z
))
.
(4)
Используя дополнительное событие [5], ПФ
H
∗
i
(
z
)
можно тракто-
вать как вероятность, что записи, обработанные только на
i
-м уровне
вложенности для каждой записи (
i
−
1)
-го уровня, являются “крас-
ными” (вероятность этого дополнительного события равна
z
). Выра-
жение
zH
i
+1
(
z
)
можно интерпретировать как вероятность того, что
запись
i
-го уровня вложенности является “красной” (
z
) и все связан-
ные с ней записи более нижнего уровня также являются “красными”
(
H
i
+1
(
z
))
. Подставляя
zH
i
+1
(
z
)
в выражение (4) вместо
z
, получим
вероятность, что записи, обработанные на
i
-м уровне вложенности и
ниже, для каждой записи (
i
−
1)
-го уровня, являются “красными”. А
эта вероятность и есть
H
i
(
z
)
, т.е.
H
i
(
z
) =
H
∗
i
(
zH
i
+1
(
z
))
.
Выражение (1) доказано.
Следствие 1
. Производящая функция числа записей базы данных,
обработанных при выполнении запроса в соответствии с исходным
планом (см. рис. 2,
а
), равна
H
(
z
) =
H
1
(
z
)
.
(5)
Это следует из определения ПФ
H
1
(
z
)
(см. (1)).
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2006. № 1 103
