ИНФОРМАТИКА И ВЫЧИСЛИТЕЛЬНАЯ
ТЕХНИКА
УДК
004.65
Ю
.
А
.
Г р и г о р ь е в
,
Н
.
А
.
Г р е б е н н и к о в
ОЦЕНКА РАЗМЕРОВ ПРОСТРАНСТВА ПОИСКА
В ОПТИМИЗАТОРАХ ЗАПРОСОВ СИСТЕМ
УПРАВЛЕНИЯ БАЗАМИ ДАННЫХ
Рассмотрена задача оценки размера пространства поиска
,
кото
-
рое просматривается системами управления базами данных при
оптимизации запросов
,
включающих соединения таблиц базы дан
-
ных
.
Проанализированы различные типы деревьев поиска и тополо
-
гий исходных запросов
.
Оценена величина выигрыша от использова
-
ния
memo-
структуры и мультивыражений для представления дере
-
вьев поиска в пространстве поиска
.
Системы управления базами данных
(
СУБД
)
являются основным
компонентом современных систем обработки информации
.
С целью
уменьшения времени выполнения запросов в состав СУБД включается
оптимизатор запросов
,
задачей которого является анализ множества
альтернативных планов выполнения запросов и выбор оптимально
-
го плана
.
Время поиска оптимального плана определяется размером
пространства поиска
,
которое
,
в свою очередь
,
зависит от количества
альтернативных деревьев поиска для исходного запроса
.
Поэтому пред
-
ставляется важной задача оценки объема вычислений для различных
типов деревьев поиска и топологий запросов
.
Деревья поиска и топологии запросов
.
Количество альтернатив
-
ных деревьев поиска для запросов
,
содержащих только операторы со
-
единения и доступа к файлам
,
представляет собой число альтернатив
-
ных порядков соединения
,
или деревьев соединений
.
Дерево соедине
-
ний
—
это регулярное бинарное дерево
, “
листья
”
которого представля
-
ют собой базовые таблицы
,
указанные в исходном запросе
,
а промежу
-
точными узлами моделируются операторы соединения
.
Эти операторы
получают со входа таблицы через входные дуги и пересылают таблицу
результата операции по выходной дуге к следующему оператору
. “
Ко
-
рень
”
дерева определяет результат всего запроса
.
Дерево соединений
является бинарным
,
так как реляционный оператор соединения имеет
два входа
.
ISSN 0236-3933.
Вестник МГТУ им
.
Н
.
Э
.
Баумана
.
Сер
. "
Приборостроение
". 2004.
№
1 91
