Оценка размеров пространства поиска в оптимизаторах запросов систем управления базами данных - page 10

Доказательство. Число групп, которые связывают k базовых от-
ношений, для звездообразного запроса определяется как µ n − 1
k − 1 ¶, по -
скольку центральное отношение включается во все соединения и, сле -
довательно, во все группы, а оставшиеся k − 1 отношения выбирают-
ся из n − 1 терминальных базовых отношений. В каждой группе, где
соединяются три и более базовых отношения, существует k − 1 муль -
тивыражений, так как для каждого мультивыражения в группе правый
вход является базовым отношением и центральное отношение не может
быть правым входом, иначе левый вход будет представлять собой сово -
купность декартовых произведений. Таким образом, каждое из k − 1
терминальных отношений используется в качестве правого входа од-
ного из мультивыражений группы. В каждой группе, которая связывает
два базовых отношения, существует два мультивыражения, так как эти
группы представляют собой оператор соединения нижнего уровня в де-
реве поиска, для которого перестановка входов не нарушает структуры
левоглубокого дерева.
Таким образом, общее число операторов в memo-структуре в силу
равенств (3) и (4) составляет
n Xk=3 µ n − 1
k − 1 ¶( k − 1) + 2 µ n − 1
1 ¶ + n =
=
n Xk =0 µ n − 1
k − 1 ¶ − µ n − 1
k − 1 ¶¯ ¯ ¯ ¯k =0 −
− µ n − 1
k − 1 ¶¯ ¯ ¯ ¯k =1 − µ n − 1
k − 1 ¶¯ ¯ ¯ ¯k =2
+ 2(n − 1) + n =
= (n − 1)
n Xk=0
( n − 2)!
( k − 2)!(n − 2 − ( k − 2))! − (n − 1) + 3n − 2 =
= 2 n−2 ( n − 1) + 2n − 1. (12)
Доказательство теоремы 5 завершено.
В работе [1] рассмотрены указанные типы деревьев поиска и топо -
логии запросов для оценки числа операторов соединения, генерируе -
мых оптимизатором Starburst. Полученные в настоящей работе резуль-
таты соотносятся с результатами, представленными в работе [1], одна -
ко существует различие, обусловленное тем, что в настоящей работе
рассматриваются упорядоченные деревья соединения и учитываются
n операторов для доступа к базовым отношениям.
Полученные результаты оценки числа мультивыражений в memo-
структуре представлены в табл. 2.
100 ISSN 0236-3933. Вестник МГТУ им. Н .Э. Баумана . Сер. "Приборостроение". 2004. № 1