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

Аннотация

Курс знакомит слушателей с различными аспектам управления транзакциями в централизованных и распределенных СУБД. Рассматриваются основные методы контроля параллельного выполнения транзакций, их особенности и применимость на практике. Кроме того обсуждаются методы восстановления состояния базы данных после программных и аппаратных сбоев, применяемые в таких популярных системах как DB2, Microsoft SQL Server, Lotus Domino, IBM MQSeries, NT file system и многих других. В курсе подробно рассматриваются методы эффективной архивации (online backup) баз данных и их реализация в существующих СУБД.

Особое внимание в курсе уделяется нестандартным приложениям баз данных (CAD/CAM, SDE), обсуждаются их особенности, требования к транзакционным механизмам и методы их поддержки в современных коммерческих системах.

Содержание курса

Введение

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

• Классическое определение транзакций и их основные свойства
  

• Понятие модели транзакций
  

• Централизованные и распределенные транзакции
  

Глава 1. Механизмы контроля параллельного выполнения транзакций (concurrency control)

• Понятие сериализуемости транзакций
  

• Основные критерии сериализуемости транзакций
  

• Методы сериализации транзакций

  • Алгоритмы, основанные на блокировках (двухфазный протокол, древовидный протокол, гранулированные блокировки, предикатные блокировки)
    

  • Метод временных меток
    

  • Алгоритмы, основанные на версиях
    

  • Оптимистические протоколы
    

  • Алгоритмы сериализации на дополнительных древовидных структурах типа B-дерево

• Методы управления deadlocks (способы их обнаружения, разрушения и предотвращения)

Глава 2. Методы восстановления сосотояния БД после сбоев (recovery)

• Виды сбоев и их особенности
  

• Основные способы восстановления (журнализация, WAL протокол, shadows)
  

• Логическая и физическая журнализация
  

• Алгоритмы восстановления в System R
  

• ARIES — алгоритм эффективного восстановления после сбоев
  

• ARIES/IM — алгоритм эффективного восстановления после сбоев для индексных структур
  

• Алгоритмы эффективного архивирования состояния БД (online backup)

Глава 3. Распределенные транзакции

• Понятие распределенной транзакции, основные особенности и характеристики
  

• Методы управления распределенными транзакциями в R*

Глава 4. Механизмы контроля параллельного выполнения транзакций в нестандартных приложениях

• Особенности нестандартных приложений и их требования к транзакциям
  

• Расширенные модели транзакций
  

• «Длинные» транзакции и методы их поддержки
  

• Методы поддержки кооперации транзакций

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

1. P. Bernstein, V. Hadzilacos, N. Goodman, "Concurrency Control and Recovery in Database Systems", Addison Wesley, Reading, Mass, 1987, http://research.microsoft.com/~philbe/
   

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

3. C. Mohan, D. Haderle, P. Schwarz, "ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging", ACM Transactions on Database Systems, Vol. 17, No. 1, March 1992, http://www.almaden.ibm.com/u/mohan/RJ6649Rev.pdf
   

4. C. Mohan, F. Levine, "ARIES/IM: An efficient and high concurrency index management method using write-ahead logging", ACM SIGMOD 1992, http://www.almaden.ibm.com/u/mohan/RJ6846.pdf
   

5. C. Mohan, Inderpal Narang, "An Efficient and Flexible Method for Archiving a Data Base", ACM SIGMOD, 1993, http://www.almaden.ibm.com/u/mohan/RJ9733.pdf
   

6. N. Barghouti, G. Kaiser, "Concurrency Control in Advanced Database Applications", ACM Computing Surveys, 1991.

Дополнительная литература

1. J. Gray, A. Reuter, "Transaction Processing: Concepts and Techniques", Morgan Kaufmann, 1993.
   

2. G. Weikum, G. Vossen, "Transactional Information Systems", Morgan Kaufmann, 2002, ISBN: 1-55860-508-8.
   

3. H. Garcia-Molina, J. D. Ullman, J. Wodom, "Database systems: the complete book", Prentice Hall, 2002.
   

4. K. Eswaran, J. Gray, R. Lorie, I. Traiger, "The notions of consistency and predicate locks in a database system", Communications of the ACM, 1976.
   

5. J. Gray, A. Lorie, et al, "Granularity of locks in a large shared data base", In Proceedings of the International Conference on Very Large Data Bases, Framingham, Massachusetts, 1975.
   

6. H. T. Kung, J. T. Robinson, "On optimistic concurrency control methods", ACM Trans. Database Syst., 1981.
   

7. J. Gray, P. McJones, M. Blasgen, B. Lindsay, R. Lorie, T. Price, F. Putzolu, I. Traiger, "The recovery manager of the System R database manager", ACM Comput. Surv. 1981.
   

8. R. Bayer, H. Heller, A. Reiser, "Parallelism and Recovery in Database Systems", ACM Transactions on Database Systems, Vol. 5, No. 2, 1980.
   

9. C. Mohan, H. Pirahesh, R. Lorie, "Efficient and Flexible Methods for Transient Versioning of Records to Avoid Locking by Read-only Transactions", ACM SIGMOD 1992.
   

10. C. Mohan, "A Cost-Effective Method for Providing Improved Data Availability During DBMS Restart Recovery After a Failure", ", In Proceedings of the International Conference on Very Large Data Bases, 1993.
    

11. C. Mohan, B. Lindsay, R. Obermarck, "Transaction Management in the R* Distributed Database Management System", ACM Trans. Database Systems, 1986.
    

12. C. Mohan, "Interactions Between Query Optimization and Concurrency Control", RIDE-TPQ, 1992.
    

13. C. Mohan, "Less Optimism About Optimistic Concurrency Control", RIDE-TPQ, 1992.
    

14. P. Lehman, B. Yao, "Efficient locking for concurrent operations on B-trees", ACM Transactions on Database Systems, Vol. 6, Issue 4, 1981.
    

15. T. Harder, K. Rothermel, "Concurrency Control Issues in Nested Transactions", VLDB Journal, 1993.
    

16. H. Garcia-Molina, K. Salem, "Sagas", ACM SIGMOD, 1987.
    

17. K. Salem, H. Garcia-Molina, R. Alonso, "Altruistic locking: a strategy for coping with long-lived transactions", In Proceedings of the 2nd International Workshop on High Performance Transaction Systems, 1987.

Ссылки

1. Страничка C. Mohan, посвященная семейству алгоритмов ARIES, очень много интересной информации, почти все статьи в открытом доступе: http://www.almaden.ibm.com/u/mohan/ARIES_Impact.html#papers
   

2. Личная страничка Phil. Bernstein http://research.microsoft.com/~philbe/
   

3. Личная страничка Jim Gray http://research.microsoft.com/~gray/