Главная страница « Спецкурсы «

Аннотация

Курс знакомит слушателей с различными аспектами хранения и обработки данных в современных СУБД. Рассматриваются принципы построения реляционных, объектно-ориентированных и XML систем управления базами данных с позиции разработчика СУБД. Особое внимание уделяется структурам представления данных во внешней памяти, индексации этих данных и эффективному выполнению запросов над ними, включая выбор оптимального плана выполнения запроса на основе оценки стоимости плана выполнения. Помимо сложившихся алгоритмов хранения реляционных данных в курсе рассматривается и сравнительно новая область — хранение и индексация XML-данных.

Данный курс будет полезен тем, кто хочет представлять себе, каким образом устроена система управления базами данных изнутри. Также курс будет полезен прикладным программистам баз данных, так как позволит более полно понимать происходящие внутри базы данных процессы.

Программа курса

Введение

• Простейшая СУБД: проблемы реализации
  

• Иерархия памяти: классические СУБД и main memory СУБД
  

• Дисковая память и ее эффективное использование

1. Реляционные и объектно-ориентированные СУБД

   • Представление данных во внешней памяти

     • Блоки внешней памяти
       

     • Записи фиксированного размера
       

     • Записи переменного размера
       

     • Адресация на диске и в оперативной памяти: техника "подмены указателей" (pointer swizzling)

   • Индексные структуры

     • B-деревья
       

     • Индексы на основе хеш-таблиц
       

     • Многомерные индексы

   • Выполнение запросов

     • Физические операции и план выполнения запроса (итераторная модель)
       

     • Внешняя сортировка
       

     • Алгоритмы выполнения операции соединения

       • Вложенные циклы
         

       • Сортировка и слияние
         

       • Хеш-соединение

   • Оптимизация запросов

     • Оценка стоимости выполнения физической операции
       

     • Понятие оптимального плана выполнения запроса. Стоимостной (cost based) оптимизатор
       

     • Порядок выполнения операций соединения

2. XML-ориентированные СУБД

   • Почему хранение XML-данных в реляционных СУБД малоэффективно?

     • Хранение XML-документов в виде BLOB- или CLOB-объектов
       

     • Декомпозиция XML-документов на отношения (shredding)

   • Методы хранения XML-данных в прирожденных XML СУБД

     • Структурные индексы и индексы по значению
       

     • Нумерующая схема
       

     • Поддержка изменений XML-документов

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

1. Гектор Гарсиа-Молина, Джеффри Ульман, Дженнифер Уидом: Системы баз данных. Полный курс, "Вильямс", 2003
   

2. Priti Mishra, Margaret H. Eich: Join processing in relational databases, ACM Computing Surveys, Volume 24, Issue 1 (March 1992)
   

3. Goetz Graefe: Query Evaluation Techniques for Large Databases, Volume 25, Issue 2 (June 1993)

4. Hong-Tai Chou, David J. DeWitt: An Evaluation of Buffer Management Strategies for Relational Database Systems. VLDB 1985
   

5. Seth J. White, David J. DeWitt: QuickStore: A High Performance Mapped Object Store. SIGMOD Conference, 1994
   

6. Seth J. White, David J. DeWitt: A Performance Study of Alternative Object Faulting and Pointer Swizzling Strategies. VLDB 1992
   

7. Goetz Graefe, William J. McKenna: The Volcano Optimizer Generator: Extensibility and Efficient Search. ICDE 1993
   

8. Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price: Access Path Selection in a Relational Database Management System. SIGMOD Conference 1979
   

9. Gregory Piatetsky-Shapiro, Charles Connell: Accurate Estimation of the Number of Tuples Satisfying a Condition. SIGMOD Conference, 1984
   

10. Tian, F., DeWit, D., Chen, J., Zhang, C.: The Design and Performance Evaluation of Alternative XML Storage Strategies. SIGMOD Record 31(1): 5-10 (2002)
    

11. Igor Tatarinov, Stratis Viglas, Kevin S. Beyer, Jayavel Shanmugasundaram, Eugene J. Shekita, Chun Zhang: Storing and querying ordered XML using a relational database system. SIGMOD Conference 2002: 204-215
    

12. Jagadish, H., Al-Khalifa, S., Chapman, A., Lakshmanan, L., Nierman, A., Paparizos S., Patel, J., Srivastava D., Wiwatwattana N., Wu, Y. and Yu, C.: TIMBER: A Native XML Database, The VLDB Journal, Volume 11, Issue 4 (2002)