1. I would expect a data base table column flag for the deleted record, set this bit type e.g. deleted record value for this field = 1.
2. Your database query should exclude where deleted = 1 and thus only return "visible" non-deleted data.
e.g. MS SQL:
select * from table1 where not (deleted = 1)
3. On insert, first do query to check if the record exists using record parameters including deleted = 1
e.g. in MS SQL:
if not exists (select * from table1 where col1 = @col1 and col2 = @col2 etc...)
begin
insert into table 1 @col1, @col2 etc...
end
else
begin
update table1 set deleted = 0 where col1 = @col1 and col2 = @col2 etc...
end