A theory of redo recovery

ABSTRACT

Our goal is to understand redo recovery. We define an installation graph of operations in an execution, an ordering significantly weaker than conflict ordering from concurrency control. The installation graph explains recoverable system state in terms of which operations are considered installed. This explanation and the set of operations replayed during recovery form an invariant that is the contract between normal operation and recovery. It prescribes how to coordinate changes to system components such as the state, the log, and the cache. We also describe how widely used recovery techniques are modeled in our theory, and why they succeed in providing redo recovery.

REFERENCES

• 1: Philip A. Bernstein , Vassco Hadzilacos , Nathan Goodman, Concurrency control and recovery in database systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 2: R. Crus. Data recovery in IBM Database 2. IBM Systems Journal, 23(2):178--188, 1984.
• 3: Klaus Elhardt , Rudolf Bayer, A database cache for high performance and fast restart in database systems, ACM Transactions on Database Systems (TODS), v.9 n.4, p.503-525, Dec. 1984 [doi>10.1145/1994.1995]
• 4: Jim Gray, Notes on Data Base Operating Systems, Operating Systems, An Advanced Course, p.393-481, January 1978
• 5: Jim Gray , Paul McJones , Mike Blasgen , Bruce Lindsay , Raymond Lorie , Tom Price , Franco Putzolu , Irving Traiger, The Recovery Manager of the System R Database Manager, ACM Computing Surveys (CSUR), v.13 n.2, p.223-242, June 1981 [doi>10.1145/356842.356847]
• 6: Jim Gray , Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992
• 7: Theo Haerder , Andreas Reuter, Principles of transaction-oriented database recovery, ACM Computing Surveys (CSUR), v.15 n.4, p.287-317, December 1983 [doi>10.1145/289.291]
• 8: Vijay Kumar , Meichun Hsu, Recovery mechanisms in database systems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1998
• 9: Dean Kuo, Model and Verification of a Data Manager Based on ARIES, Proceedings of the 4th International Conference on Database Theory, p.231-245, October 14-16, 1992
• 10: David B. Lomet, Persistent Applications Using Generalized Redo Recovery, Proceedings of the Fourteenth International Conference on Data Engineering, p.154-163, February 23-27, 1998
• 11: D. Lomet. Advanced Recovery Techniques in Practice. in Recovery Mechanisms in Database Systems Prentice Hall, 1998
• 12: David B. Lomet , Mark R. Tuttle, Redo Recovery after System Crashes, Proceedings of the 21th International Conference on Very Large Data Bases, p.457-468, September 11-15, 1995
• 13: David Lomet , Mark Tuttle, Logical logging to extend recovery to new domains, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.73-84, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 14: C. Mohan , Don Haderle , Bruce Lindsay , Hamid Pirahesh , Peter Schwarz, ARIES: a transaction recovery method supporting fine-granularity locking and partial rollbacks using write-ahead logging, ACM Transactions on Database Systems (TODS), v.17 n.1, p.94-162, March 1992 [doi>10.1145/128765.128770]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.7 Database Administration
          Subjects: Logging and recovery

Additional Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.1 Systems and Information Theory
          Subjects: General systems theory

General Terms:
Algorithms, Design, Experimentation