We describe a reliability algorithm being considered for DDM, a distributed database system under development at Computer Corporation of America. The algorithm is designed to tolerate clean site failures in which sites simply stop running. The algorithm allows the system to reconfigure itself to run correctly as sites fail and recover. The algorithm solves the subproblems of atomic commit and replicated data handling in an integrated manner.

Adaplex is an integrated language for programming database applications. It results from the embedding of the database sublanguage DAPLEX in the general purpose programming language Ada. This paper provides an overview of the DDM: a distributed database manager (DDM) that supports the use of Adaplex as an interface language. The important technical innovations we have incorporated in the design of this system include:1. An advanced data model that captures more application semantics than conventional data models.2. Support for flexible data distribution options that improve locality of reference and efficiency of query processing.3. Extensive query optimization that combines compile time access path optimization with run time site selection.4. Efficient transaction management that reduces transaction conflicts and improves the resiliency of replicated data.5. Robust, incremental recovery management that provides for automatic recovery from certain "catastrophic" failure conditions.

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].

In database management systems and operating systems, transactions are used as units of consistency, serializability, recovery, and for deadlock control. Normally, the transactions for each of these systems are considered independently. In this paper we describe nested transactions where the transactions from one system interact with the transactions from another system. Such nested transactions can expect to become more important with the introduction of network operating systems and heterogeneous distributed database systems.

Locking granularity refers to the size and hence the number of locks used to ensure the consistency of a database during multiple concurrent updates. In an earlier simulation study we concluded that coarse granularity, such as area or file locking, is to be preferred to fine granularity such as individual page or record locking. However, alternate assumptions than those used in the original paper can change that conclusion. First, we modified the assumptions concerning the placement of the locks on the database with respect to the accessing transactions. In the original model the locks were assumed to be well placed. Under worse case and random placement assumptions when only very small transactions access the database, fine granularity is preferable. Second, we extended the simulation to model a lock hierarchy where large transactions use large locks and small transactions use small locks. In this scenario, again under the random and worse case lock placement assumptions, fine granularity is preferable if all transactions accessing more than 1 percent of the database use large locks. Finally, the simulation was extended to model a “claim as needed” locking strategy together with the resultant possibility of deadlock. In the original study all locks were claimed in one atomic operation at the beginning of a transaction. The claim as needed strategy does not change the conclusions concerning the desired granularity.

Many data base systems guarantee some form of integrity control upon multiple concurrent updates by some form of locking. Some "granule" of the data base is chosen as the unit which is individually locked, and a lock management algorithm is used to ensure integrity. By a simulation model this paper explores the desired size of a "granule". Under a wide variety of seemingly realistic conditions, surprisingly coarse granularity is called for. The paper concludes with some implications of these results concerning the viability of so called "predicate locking".Research sponsored by the Naval Electronic Systems Command Contract N00039-76-c-0022, the National Science Foundation Grant DCR75-03839 and the Army Research Office Grant DAAG29-76-6-0245.

Many database systems guarantee some form of integrity control upon multiple concurrent updates by some form of locking. Some “granule” of the database is chosen as the unit which is individually locked, and a lock management algorithm is used to ensure integrity. Using a simulation model, this paper explores the desired size of a granule. Under a wide variety of seemingly realistic conditions, surprisingly coarse granularity is called for. The paper concludes with some implications of these results concerning the viability of so-called “predicate locking”.