This algorithm only reads the immutable fields of the record and compares them to the corresponding fields of the incoming record. If they match in a manner that you consider to be equivalent, then and only then is it appropriate to continue, otherwise, 1. If the database is designed so that in place recreation of records is allowed, throw a RecordNotFoundException (since the record you were looking for, characterized by its immutable fields, no longer exists).
Finally, concerning the creation of new records. If the policy that allows a new record to over-write a previously deleted record is active, then the database does not care at all about the contents of a deleted record; if the record is deleted, then it is locked, and then it is written over (and its contents are not important). If no re-usable records can be found (that is, the database contains no deleted records), then the new record is created at the end of the file.
So, here is what I will probably do. I will state that allowing new records
to over-write previously existing records may not be logically sound, and
that I don't know the philosophical or logical answer to this question. It is the customer's responsibility to configure the database in a safe
manner, and the customer does this by setting up the server and stating
what the policy will be by chosing one of the following choices from the
1. The database will allow the creation of new records to over-write
previously deleted records.
2. The database will only write new records at the end of the file.