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