An algorithm for minimizing roll back cost

Vassos Hadzilacos

Most automatic crash recovery mechanisms for database systems are based on the concept of transaction commitment. Should a crash occur after a transaction has become committed, the transaction may not be restarted. If, however, a crash occurs before a transaction has become committed, that transaction must be restarted. Several mechanisms that achieve this behavior have been proposed by database system designers. In most of these mechanisms, when a transaction is restarted, it is ``rolled back'' all the way to the beginning. One exception is System-R which allows to roll an uncommitted transaction back to an earlier ``savepoint'', which is not necessarily its beginning. In this paper we investigate the problem of finding the optimal set of savepoints (one per transaction) to which uncommitted transactions executing concurrently must be rolled back after a crash, so that the recovery cost is minimized.