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

отношений представляет собой некоторый промежуточный результат,
то число групп в пространстве поиска равно
n Xk=1 ³ n
k ´ = 2n − 1. Груп -
па, соответствующая k базовым отношениям, описывает все возмож -
ные операторы верхнего уровня для этих k отношений. Каждое разде -
ление на левое и правое непустые подмножества множества k отноше-
ний соответствует оператору в группе. Таким образом , число операто -
ров в группе, соответствующей k базовым отношениям , равно 2k − 2
для k > 1. При k = 1 группа содержит единственный оператор до -
ступа к базовому отношению. По условию существует n таких групп.
Число операторов в memo-структуре — это число всех операторов во
всех группах memo-структуры, следовательно , в силу бинома Ньютона
имеем
n X
k =2 µ n
k ¶ (2 k − 2) + n =
n Xk =2 µ n
k ¶ · 2k − 2
n Xk =2 µ n
k ¶ + n =
= 3n − 1 − 2n − 2 · 2n + 2 + 2n + n = 3n − 2n+1 + n + 1. (8)
Теорема 2. Количество мультивыражений (операторов соедине -
ния), необходимых для представления всех кустовых деревьев соедине-
ния, для линейных запросов с числом отношений n равно (n3 + 2n) /3.
Доказательство. Для строкового запроса , выполняющего соедине-
ние n отношений, существует n − k + 1 возможных “подстрок”, связы-
вающих k базовых отношений . Для каждой их этих “ подстрок” суще-
ствует группа, содержащая все операторы верхнего уровня этой груп -
пы. Если левый и правый входы различаются, то имеется 2(k − 1) опе-
раторов в группе, которая описывает “ подстроку” из k отношений для
k > 1. При k = 1 группа содержит единственный оператор . Таким
образом, на основании выражений [6]
n Xk =1
k =
n(n + 1)
2
,
n Xk=1
k2 =
n( n + 1)(2 n + 1)
6
получим, что общее число операторов в memo-структуре равно
2 ·
n Xk =2
(n − k + 1)(k − 1) + n =2 ·
n Xk =2
( −n − 1 − k 2 + k( n + 2))+ n =
= − 2(n − 1)(n +1) − 2µ 2n3 +3n2 + n
6 − 1¶+2(n + 2)(
n2 +n
2 − 1) + n =
= −2n2 + 2 −
2n3 + 3n 2 + n − 6
3
+ n3 + 3n2 − 4 + n =
n3 + 2n
3
. (9)
98 ISSN 0236-3933. Вестник МГТУ им. Н .Э. Баумана . Сер. "Приборостроение". 2004. № 1