Рис
. 1.
Типы деревьев поиска
:
а
—
левоглубокое дерево
;
б
—
кустовое упорядоченное дерево
Рис
. 2.
Типы топологий запросов
:
а
—
линейная
;
б
—
звездообразная
;
в
—
полностью соединенная
;
г
—
с четырьмя
ветвями
При поиске оптимального плана оптимизатор обычно строит дере
-
вья поиска одного из двух типов
(
рис
. 1).
Левоглубокое
(
левосторон
-
нее
,
левонаправленное
,
леволинейное
,
линейное
)
дерево поиска
—
это
дерево поиска
,
в котором для каждого оператора соединения
(
проме
-
жуточного узла
)
хотя бы один из входов является базовой таблицей
;
в
противном случае дерево соединений называется кустовым
.
Кроме типа деревьев поиска
,
на построение которых настроен опти
-
мизатор
,
размер генерируемого им пространства поиска зависит также
от топологии графа исходного запроса
(
далее просто
—
топологии за
-
проса
).
Существуют три типовые топологии запросов
(
рис
. 2,
а
–
в
).
Линей
-
ный
(
строковый
)
запрос для
n
отношений состоит из двух терминаль
-
ных
(
крайних
)
отношений
,
каждое из которых соединено только с од
-
ним отношением
,
и
n
−
2
внутренних отношений
,
каждое из которых
соединено с двумя соседними отношениями
.
Связь между двумя отно
-
шениями означает наличие в исходном запросе предиката соединения
для этих отношений
.
Звездообразный запрос для
n
отношений состоит
92 ISSN 0236-3933.
Вестник МГТУ им
.
Н
.
Э
.
Баумана
.
Сер
. "
Приборостроение
". 2004.
№
1
