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

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