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