из одного центрального отношения и
n
−
1
терминальных отношений
,
которые соединены только с центральным
.
Полностью соединенный
запрос для
n
отношений состоит из
n
отношений
,
каждое из которых
соединено со всеми другими
n
−
1
отношениями
.
Любой запрос можно
представить в виде полностью соединенного запроса
,
достроив недо
-
стающие связи путем добавления фиктивного предиката соединения
,
который всегда имеет значение
“
истина
”.
Добавленные таким образом
связи
,
очевидно
,
будут представлять собой декартовы произведения со
-
ответствующих отношений
.
Линейная и звездообразная топологии запросов представляют со
-
бой крайние случаи ациклических запросов
[1].
Линейный запрос со
-
держит одну ветвь
,
а звездообразный
—
n
ветвей графа запроса соеди
-
нений
n
таблиц
.
В работе
[1]
показано
,
что количество альтернативных
деревьев поиска для всех остальных топологий ациклических запросов
(
с двумя
,
тремя и т
.
д
.
ветвями при фиксированном числе отношений
—
рис
. 2,
г
)
лежит в интервале от числа деревьев поиска для линейных за
-
просов до числа деревьев поиска для звездообразных запросов
.
Оценка числа альтернативных деревьев поиска
.
Найдем число
возможных деревьев поиска для указанных топологий запросов и ти
-
пов деревьев поиска
.
При этом будем рассматривать только логические
деревья поиска
,
не учитывая различные реализации операции соедине
-
ния
.
Случай
1.
Кустовое дерево
,
полностью соединенный запрос
.
Этот
случай определяет верхнюю границу числа возможных деревьев поис
-
ка
.
В работе
[2]
дана оценка числа деревьев поиска для этого случая
:
x
n
=
(2
n
−
2)!
(
n
−
1)!
.
(
1
)
Предполагается
,
что для каждого дерева поиска корневой узел име
-
ет левый операнд
,
охватывающий
k
отношений
,
и правый операнд
,
охватывающий
(
n
−
k
)
отношений
.
Поэтому число деревьев поиска
определяется с помощью следующего выражения
:
x
n
=
n
−
1
X
k
=1
³
n
k
´
x
k
x
n
−
k
,
(
2
)
где
x
1
= 1
.
Далее путем достаточно сложных математических вычислений из
выражения
(2)
выводится искомая формула
(1).
В настоящей работе
предлагается более простой вывод формулы
(1)
для числа деревьев по
-
иска в рассматриваемом случае
.
ISSN 0236-3933.
Вестник МГТУ им
.
Н
.
Э
.
Баумана
.
Сер
. "
Приборостроение
". 2004.
№
1 93
