Случай
2.
Левоглубокие деревья поиска
.
Теорема
3.
Количество мультивыражений
(
операторов соедине
-
ния
),
необходимых для представления всех левоглубоких деревьев со
-
единения
,
для полностью соединенных запросов с числом отношений
n
равно
2
n
−
1
n
.
Доказательство
.
Число групп
,
соответствующих
k
базовым отно
-
шениям
,
для полностью соединенных запросов определяется как
µ
n
k
¶
.
Число мультивыражений в группе
,
соответствующих
k
базовым отно
-
шениям
,
равно
k
,
так как для каждого мультивыражения в группе пра
-
вый вход является базовым отношением
.
При
k
= 1
группа содержит
единственный оператор доступа к базовому отношению
.
Таким обра
-
зом
,
на основании выражения
n
X
k
=0
µ
n
k
¶
k
=
n
X
k
=0
kn
!
k
!(
n
−
k
)!
=
n
X
k
=0
n
(
n
−
1)!
(
k
−
1)!(
n
−
1
−
(
k
−
1))!
= 2
n
−
1
n
получим
,
что общее число операторов в
memo-
структуре составляет
n
X
k
=2
µ
n
k
¶
k
+
n
= 2
n
−
1
n
−
n
+
n
= 2
n
−
1
n.
(
10
)
Теорема
4.
Количество мультивыражений
(
операторов соедине
-
ния
),
необходимых для представления всех левоглубоких деревьев со
-
единения
,
для линейных запросов с числом отношений
n
равно
n
2
.
Доказательство
.
Для строкового запроса
,
выполняющего соедине
-
ние
n
отношений
,
существует
n
−
k
+1
возможных
“
подстрок
”,
связыва
-
ющих
k
базовых отношений
.
Для каждой их этих
"
подстрок
"
существу
-
ет группа
,
содержащая все операторы верхнего уровня этой группы
.
В
каждой группе
,
включающей два и более отношения
,
существует всего
два мультивыражения
,
так как для каждого мультивыражения в группе
правый вход является базовым отношением и для каждой
“
подстроки
”
размера
k >
1
существует только два терминальных отношения
,
кото
-
рые могут быть правым входом
.
При
k
= 1
каждая группа содержит
единственный оператор доступа к базовому отношению
.
Таким обра
-
зом
,
общее число операторов в
memo-
структуре составляет
n
X
k
=2
2(
n
−
k
+ 1) +
n
= 2(
n
+ 1)(
n
−
1)
−
2
µ
n
2
+
n
2
−
1
¶
+
n
=
n
2
.
(
11
)
Теорема
5.
Количество мультивыражений
(
операторов соедине
-
ния
),
необходимых для представления всех левоглубоких деревьев со
-
единения
,
для звездообразных запросов с числом отношений
n
равно
2
n
−
2
(
n
−
1) + 2
n
−
1
.
ISSN 0236-3933.
Вестник МГТУ им
.
Н
.
Э
.
Баумана
.
Сер
. "
Приборостроение
". 2004.
№
1 99
