Таким образом
,
можно сделать вывод
,
что использование
memo-
структуры и мультивыражений для представления деревьев поиска в
пространстве поиска позволяет получить значительный выигрыш как
в объеме оперативной памяти
,
так и в быстродействии оптимизатора
запросов СУБД
.
Заключение
.
Получены формулы для оценки числа альтернатив
-
ных деревьев поиска и необходимых для их представления мультивы
-
ражений в
memo-
структуре для кустовых и левоглубоких деревьев по
-
иска и полностью соединенных
,
линейных и звездообразных тополо
-
гий исходных запросов
.
На основе полученных формул оценена эффективность использо
-
вания
memo-
структуры для представления пространства поиска
,
и сде
-
лан вывод
,
что использование
memo-
структуры и мультивыражений
позволяет получить значительный выигрыш в объеме оперативной па
-
мяти и быстродействии оптимизатора СУБД для запросов соединений
,
включающих более пяти таблиц базы данных
.
СПИСОК ЛИТЕРАТУРЫ
1. O n o K., L o h m a n G. Measuring the Complexity of Join Enumeration in
Query Optimization // Proc. of the 16th International Conf. on Very Large Data Bases
(Brisbane, Australia, August 1990). – P. 314–325.
2. L a n z e l o t t e R., V a l d u r i e z P., Z a i t M. On the effectiveness of
optimization search strategies for parallel execution spaces // Proc. of the 19th VLDB
Conf. (Dublin, 1993). – P. 493–504.
3. H i l t o n P., P e d e r s e n J. Catalan numbers, their generalizations and their uses
// The Mathematical Intelligencer. – 1991. –
№
13. – P. 64–75.
4. G r a e f e G., M c K e n n a W. The Volcano Optimizer Generator: Extensibility and
Efficient Search // Proc. of the 12th International Conf. on Data Engineering. – 1993.
– P. 209–218.
5. G r a e f e G. The Cascades Framework for Query Optimization // Bulletin of the
IEEE Technical Committee on Data Engineering. – 1995. – V. 18. –
№
3. – P. 19–29.
6.
К о р н Г
.,
К о р н Т
.
Справочник по математике
. –
М
.:
Наука
, 1984.
Статья поступила в редакцию
21.03.2003
Юрий Александрович Григорьев родился в
1951
г
.,
окончил
в
1975
г
.
МВТУ им
.
Н
.
Э
.
Баумана
.
Д
-
р техн
.
наук
,
профес
-
сор кафедры
“
Системы обработки информации и управления
"
МГТУ им
.
Н
.
Э
.
Баумана
.
Автор
60
научных работ в области
систем обработки информации
.
Yu.A. Grigoriev (b. 1951) graduated from the Bauman Moscow
Higher Technical School in 1975. Ph.D. (Eng.), professor of
“Systems of Data Processing and Control” department of the
Bauman Moscow State Technical University. Author of 60
publications in the field of data processing systems.
104 ISSN 0236-3933.
Вестник МГТУ им
.
Н
.
Э
.
Баумана
.
Сер
. "
Приборостроение
". 2004.
№
1
