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