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

Рис
. 1.
Типы деревьев поиска
:
а
левоглубокое дерево
;
б
кустовое упорядоченное дерево
Рис
. 2.
Типы топологий запросов
:
а
линейная
;
б
звездообразная
;
в
полностью соединенная
;
г
с четырьмя
ветвями
При поиске оптимального плана оптимизатор обычно строит дере
-
вья поиска одного из двух типов
(
рис
. 1).
Левоглубокое
(
левосторон
-
нее
,
левонаправленное
,
леволинейное
,
линейное
)
дерево поиска
это
дерево поиска
,
в котором для каждого оператора соединения
(
проме
-
жуточного узла
)
хотя бы один из входов является базовой таблицей
;
в
противном случае дерево соединений называется кустовым
.
Кроме типа деревьев поиска
,
на построение которых настроен опти
-
мизатор
,
размер генерируемого им пространства поиска зависит также
от топологии графа исходного запроса
(
далее просто
топологии за
-
проса
).
Существуют три типовые топологии запросов
(
рис
. 2,
а
в
).
Линей
-
ный
(
строковый
)
запрос для
n
отношений состоит из двух терминаль
-
ных
(
крайних
)
отношений
,
каждое из которых соединено только с од
-
ним отношением
,
и
n
2
внутренних отношений
,
каждое из которых
соединено с двумя соседними отношениями
.
Связь между двумя отно
-
шениями означает наличие в исходном запросе предиката соединения
для этих отношений
.
Звездообразный запрос для
n
отношений состоит
92 ISSN 0236-3933.
Вестник МГТУ им
.
Н
.
Э
.
Баумана
.
Сер
. "
Приборостроение
". 2004.
1
1 3,4,5,6,7,8,9,10,11,12,...14
Powered by FlippingBook