1.      Аннотация программы

Целью курса является введение в проблематику обработки и оптимизации запросов в системах баз данных.

2.      Содержание программы

1.     Обзор этапов обработки запроса

Компилятор запросов. Синтаксический анализ и деревья разбора. Грамматика для простого подмножества SQL. Препроцессор.

2.     Преобразование дерева разбора в логический план запроса

Конверсия в реляционную алгебру. Удаление подзапросов из условий. Улучшение логического плана запроса. Группировка ассоциативных/коммутативных операторов.

3.     Оценка стоимости операций

Оценка размеров промежуточных отношений. Оценка размеров проекции. Оценка размеров селекции. Оценка размеров соединения. Естественное соединение с несколькими атрибутами соединения. Соединение нескольких отношений. Оценка размеров для других операций.

4.     Выбор плана на основе стоимостной функции

Получение оценок для параметров, задающих размеры отношений. Накопление статистической информации. Эвристики для уменьшения стоимости планов логических запросов. Подходы к перебору физических планов.

5.     Алгоритмы реализации операторов физической алгебры

Сканирование и сортировка. Стоимостная модель для физических операторов. Итераторная и потоковая модели для организации выполнения операторов физической алгебры. Однопроходные и многопроходные алгоритмы реализации операций над базой данных. Двухпроходные алгоритмы на базе сортировки и хеширования. Алгоритмы, базирующиеся на использовании индексов.

6.     Генерация физического плана запроса

Выбор методов для селекции. Выбор методов для соединения. Конвейеризация против материализации. Конвейеризация унарных операций. Конвейеризация бинарных операций. Нотация для физических планов запроса. Упорядочивание физических операций.

7.     Управление буферным пулом

Архитектура менеджера буферного пула. Стратегии вытеснения страниц. Связь между выбором физических операторов и управлением буферным пулом.

3.      Распределение часов

4.      Основная литература

1.     Aho A.V., Sethi R., Ullman J.D. Compilers : Principles, Techniques, and Tools. Addison-Wesley, 1986. 500 p.

2.     Effelsberg W., Harder T. Principles of Database Buffer Management // ACM Trans. on Database Systems. Dec. 1984.Vol. 9. No. 4. P. 560‑595.

3.     Garcia-Molina H., Ullman J.D., Widom J. Database System Implementation. Prentice Hall, 2000.653 p.

4.     Graefe G. Query evaluation techniques for large databases // ACM Computing Surveys. June 1993.Vol. 25. No. 2. P. 73‑169.

5.     Jarke M., Koch J. Query optimization in database systems // ACM Computing Surveys. June 1984.Vol. 16. No. 2. P. 111‑152.

6.     Sokolinsky L.B. Operating System Support for a Parallel DBMS with an Hierarchical Shared-Nothing Architecture // Proc. of the Third East-European Conf. on Advances in Databases and Information Systems ( ADBIS'99), Maribor, Slovenia, September 13-16, 1999. Maribor University Publishing. 1999. P. 38‑45.
http://sok.susu.ru/papers/abstracts/99-ADBIS.html

7.     SQL2 Grammar. ftp://jerry.ece.umassd.edu/isowg3/dbl/BASEdocs/public/sql-92.bnf.

8.     Кузнецов С. Методы оптимизации выполнения запросов в реляционных СУБД // http://www.citforum.ru/database/articles/art_26.shtml

9.     Чаудхари С. Методы оптимизации запросов в реляционных системах // СУБД. 1998. №3. C. 22‑36. http://www.osp.ru/dbms/1998/03/22.htm