Теорема 2.
ПЛС
T
i
(
s
)
времени обработки записей
i
-го уровня вло-
женности и ниже для каждой записи (
i
−
1)
-го уровня равно
T
i
(
s
) =
G
i
(1
−
p
i
(1
−
δ
i
(
s
)
T
i
+1
(
s
)
ξ
i
(
s
)))
, i
= 1
, n,
(6)
где
G
i
(
z
)
и
p
i
определяются выражениями (2) и (3);
δ
i
(
s
)
— ПЛС-
времени поиска/чтения одной записи
i
-го уровня вложенности из
БД;
ξ
i
(
s
)
— ПЛС-времени сравнения в соответствии с условием
Ai1
τ
i fi+1(Ai+1,2) для
i
= 1
, n
−
1
и/или определения текущего зна-
чения функции агрегирования fi(Ai2) при успешном сравнении для
i
= 2
, n
(см. рис. 2,
а
),
T
n
+1
(
s
)
≡
1
.
Доказательство
. При доказательстве
теоремы 1
была получена
производящая функция
H
∗
i
(
z
)
числа записей, обработанных только
на
i
-м уровне вложенности для каждой записи (
i
−
1)
-го уровня (см.
уравнение (4)). ПЛС-времени обработки такой записи и связанных с
ней записей нижних уровней определяется следующим выражением:
T
∼
i
(
s
) =
δ
i
(
s
)
T
i
+1
(
s
)
ξ
i
(
s
)
.
(7)
Для доказательства (7) воспользуемся методом дополнительного
события [5], трактуя ПЛС как вероятность того, что за случайное вре-
мя не наступит “катастрофы” (
s
— интенсивность “катастроф”). Тогда
вероятность
T
∼
i
(
s
)
равна вероятности того, что “катастрофа” не насту-
пит за время:
1) поиска/чтения записи
i
-го уровня (
δ
i
(
s
))
;
2) обработки связанных с ней записей нижних уровней (
T
i
+1
(
s
))
;
3) сравнения атрибута Ai1 и агрегирования значения атрибута Ai2
(
ξ
i
(
s
))
.
Это доказывает выражение (7). Подставляя (7) в (4) и учи-
тывая свойства ПФ и ПЛС, получим утверждение теоремы, т.е.
T
i
(
s
) =
H
∗
i
(
δ
i
(
s
)
T
i
+1
(
s
)
ξ
i
(
s
))
. Выражение (6) доказано.
Следствие 2
. ПЛС-времени выполнения запроса в соответствии с
исходным планом (см. рис. 2,
а
) равно
T
(
s
) =
T
1
(
s
)
.
(8)
Это утверждение следует из определения ПЛС
T
1
(
s
)
(см. форму-
лу (6)).
Альтернативный план (в виде
SQL
-запросов
— см. рис. 3
)
.
Теорема 3
. Производящая функция
W
i
(
z
)
числа записей, обрабо-
танных при выполнении
i
-го
SQL
-запроса, определяется следующей
формулой:
W
i
(
z
) =
Q
i
+1
(
z
)
G
i
(
z
)
Q
i
(
z
)
, i
=
n,
1
,
(9)
104 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2006. № 1
