Рис
. 6.
Величина выигрыша от использования
memo-
структуры и мультивыра
-
жений для представления деревьев поиска в пространстве поиска
:
1
—
кустовое дерево
,
полностью соединенный запрос
;
2
—
кустовое дерево
,
линей
-
ный запрос
;
3
—
левоглубокое дерево
,
полностью соединенный запрос
;
4
—
левоглу
-
бокое дерево
,
линейный запрос
;
5
—
левоглубокое дерево
,
звездообразный запрос
ка и топологии исходного запроса можно оценить
,
сравнив значение
,
соответствующее числу деревьев
,
со значением
,
соответствующим чи
-
слу мультивыражений
.
Например
,
для случая кустового дерева поиска
и полностью соединенного исходного запроса соединения четырех от
-
ношений существует
120
альтернативных деревьев поиска и требуется
54
мультивыражения
(
оператора соединения
)
для их представления
.
Следовательно
,
получаемый выигрыш равен
(120
−
54)
/
120
,
т
.
е
. 55 %.
На рис
. 6
представлены диаграммы величин выигрыша для запро
-
сов
,
включающих от
3
до
13
соединяемых отношений
.
Из рисунка вид
-
но
,
что наибольший выигрыш достигается для кустовых деревьев по
-
иска
,
для которых при любой топологии исходного запроса соединения
шести отношений выигрыш составляет более
95 %.
Выигрыш для лево
-
глубоких деревьев поиска менее значителен
,
однако и в этом случае для
полностью соединенных и звездообразных запросов выигрыш прибли
-
жается к
90 %
начиная с
7–8
отношений
.
Медленнее всего возрастает
величина выигрыша для линейных запросов при построении левоглу
-
боких деревьев поиска
.
Это объясняется малым числом деревьев для
данного случая
,
поэтому выигрыш от использования
memo-
структуры
начинает ощущаться только для запросов соединения шести отноше
-
ний и достигает величины
90 %
только для запросов с
11
отношения
-
ми
.
Отсутствие выигрыша в некоторых случаях для запросов
,
включа
-
ющих малое число отношений
(
от
3
до
5),
объясняется малым числом
деревьев поиска для этих случаев
,
а также тем
,
что при подсчете учи
-
тывается число мультивыражений
n
операторов доступа к базовым от
-
ношениям
,
которые не являются операторами соединения
.
ISSN 0236-3933.
Вестник МГТУ им
.
Н
.
Э
.
Баумана
.
Сер
. "
Приборостроение
". 2004.
№
1 103
