отношение поступает на вход операции
γ
после выполнения операций,
расположенных по дереву ниже. fi+1(Ai+1, 2) — это операция агреги-
рования атрибута Ai+1, 2, которая выполняется для каждой группы.
Идентификаторы ri+1 и qi+1 — это псевдонимы значений, указанных
слева от них, т.е. Ai+1, 4 и fi+1(Ai+1, 2) соответственно.
3. Операцию селекции
σ
без индекса и условие «condition» заме-
нить на селекцию
σ
Ai1
τ
i qi+1
над декартовым произведением Ri и
γ
.
4. Каскад селекций
σ
Ai3 = Ai + 1, 4
и
σ
Ai1
τ
i qi+1
заменить на одиночную
селекцию
σ
Ai3=ri+1
∩
Ai1
τ
i qi+1
.
Последовательно применяя процедуру 1–4 для каждого уровня вло-
женности (
i
меняется от (
n
−
1
) до 1, селекция
σ
A03 = A14
считается
пустой), план (см. рис. 2,
а
, исходный план) можно преобразовать к
дереву, приведенному на рис. 2,
б
(альтернативный план). Используя
законы реляционной алгебры, можно доказать, что преобразования 1–
4 являются корректными, т.е. после выполнения снизу вверх процесса,
представленного на рис. 2,
б
, будет получен правильный результат по-
иска данных.
В некоторых СУБД, например
Oracle
, план (см. рис. 2,
б
) вы-
полняется неэффективно на физическом уровне (здесь соединение
σ
Ai3=ri+1
∩
Ai1
τ
i qi+1
реализуется путем фильтрации всех записей уров-
ня
i
)
. Далее приведены
n
SQL
-операторов (рис. 3), совокупность кото-
рых соответствует плану на рис. 2,
б
. В каждом запросе выполняется
соединение двух таблиц, кроме самого первого. Практически во всех
СУБД предусмотрены эффективные методы соединения. Поэтому эти
n
SQL
-операторов часто выполняются быстрее, чем один исходный
запрос (см. рис. 1) в соответствии с планом на рис. 2,
б
.
Оценка времени выполнения запроса для исходного и альтер-
нативного планов.
В настоящей работе доказаны приведенные ниже
четыре теоремы о производящих функциях (ПФ) числа обработанных
записей и преобразованиях Лапласа–Стилтьеса (ПЛС) времени выпол-
нения запроса для исходного и альтернативного планов. Это важно, так
как на этапе проектирования ИС конкретные значения полей записей
базы данных и некоторые параметры запросов неизвестны, и поэтому
можно говорить об их случайном характере.
Исходный план.
Теорема 1.
Производящая функция
H
i
(
z
)
числа записей, обработан-
ных на
i
-м уровне вложенности и ниже, для каждой записи (
i
−
1)
-го
уровня определяется следующей рекуррентной формулой:
H
i
(
z
) =
G
i
(1
−
p
i
(1
−
zH
i
+1
(
z
)))
, i
= 1
, n,
(1)
где
G
i
(
z
) =
z
V
i
—
(2)
102 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2006. № 1
