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

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