Database Integrity Block Construct: Concepts and Design Issues

When a crash occurs in a transaction processing system, the database can enter an unacceptable state. To continue the processing, the recovery system has three tasks: 1) verification of the database state for acceptability, 2) restoration of an acceptable database state, and 3) restoration of an acceptable history of transaction processing. Unfortunately these tasks are not trivial and the computational complexity of the algorithms for most of them is either NP-complete or NP-hard. In this paper we discuss the concepts and design issues of a construct called database integrity block (DIB). The implementation of this construct allows for efficient verification of the database state by employing a set of integrity assertions and restoration of transaction history by utilizing any database restoration technique such as audit trail or differential file. This paper presents approximation algorithms for minimizing the costs of evaluation of integrity assertions by modeling the problem as the directed traveling salesman problem, and presents a methodology to compare the costs of audit trail and differential file techniques for database restoration. The applicability of integrity verification research to the problem of multiple-query optimization is also included.