Correctness proof for database reconstruction algorithm

The increasing usage of databases in storing critical and sensitive information in various organizations has led to an increase in the rate at which databases are exploited in computer crimes. Unfortunately, despite that various digital forensics investigations involving databases have been explored in theory and in practice, database forensics has received little or research attention and there is still no defined underlying model for any aspect of database forensics. This paper describes our earlier algorithm for reconstructing the information in a database for forensics purposes and presents the proof of correctness of the algorithm. The database reconstruction algorithm determines the data in a relation on the database at some earlier time of interest using the current instance of the database and the log of modifying queries that have been performed on it from the time of interest to the present time. The paper describes inverse functions for the operators of the relational algebra and discusses the notion of relational algebra log and value blocks of a relation which are used in the algorithm. A major part of the paper presents the proof of correctness of the database reconstruction algorithm described.