Browser unable to execute script; please use the site map to navigate the site.

Correctness proof for database reconstruction algorithm

Fasan and Olivier


(Citation)Citation information

O. M. Fasan and M. S. Olivier. “Correctness proof for database reconstruction algorithm”. In: Digital Investigation 9.2 (2012), pp. 138–150


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.

(Authoritative version on publisher's site)Definitive version

The definitive version of the paper is available from the publisher.
DOI: 10.1016/j.diin.2012.09.002

(BibTeX record)BibTeX reference

author={Oluwasola Mary Fasan and Martin S Olivier},
title={Correctness proof for database reconstruction algorithm},
journal={Digital Investigation},
number={2}, pages={138--150})