The invention relates to the recovery of data in a database of database records, following a failure of a media containing said database. The data recovery uses a backup of the database and a log of log records detailing any changes in the database which are not captured in the backup. The log is replayed starting with the most recent log record. It is the determined for each successive log record, that relates to an operation on a database record, whether processing the log record will result in the most recent state of the corresponding database record, and if so, the log record is processed. Subsequently additional data is restored from the backup.