This paper describes the implementation level design of an integrated concurrency control and recovery scheme based on the maintenance of multiple versions of data objects in a database. The concurrency control mechanism enhances parallelism by eliminating interference between retrieval and update transactions. The recovery mechanism permits efficient transaction and system recovery by keeping before-images of data objects at the page (block) level. This paper addresses the key technical problems in the implementation of such an integrated scheme. We present an efficient garbage collection algorithm for reclaiming storage space used by old versions of data objects that will no longer be accessed. We also propose an on-line backup algorithm that will permit the backup procedure to run in parallel with regular transactions. This integrated concurrency control and recovery scheme is being implemented in the LDM: the local database manager component of a distributed database management system, now being developed by Computer Corporation of America, that will support the ADAPLEX database application programming language [Chan81a, Smith81].

Two concurrency control mechanisms, the SDD-1 system and Dynamic Timestamping Method, are evaluated in terms of protocol synchronization delays and average transaction response time by using simulation. Relationship among average protocol synchronization delay, average transaction response time, average 10 service delay, communication delay, and other system parameters is analyzed by using regression analysis. The statistical distribution functions of transaction response times and synchronization delays are then examined to see if they fit exponential, erlangian, or some other distribution functions.