Начало истории - как у всех, надо хранить историю изменений записи. Физическое удаление запрещаем. Далее варианты:

0. (Отступление) В каждой таблице имеем два поля CreatorID и CreationDT, с ИД пользователя ввёвшего (сорри, забыл как это по русски называется :)) данные и когда собс-но он их ввёл.

1 Вариант: В каждой таблице создаём аналогично два поля, с ИД пользователя, "удалившего" данные и датой/временем удаления. Очевидный минус - записи удаляются редко, а в некоторых таблицах - ОЧЕНЬ редко,так что таскать поля везде за собой - места жалко. Отсев удалённых записей в этом случае идёт по DeleterID <> NULL. Для хронологического восстановления добавляем третье поле - ссылка на ИД новой записи.

2 Вариант: Создаем отдельную таблицу удалённых элементов, в которую пишем имя таблицы, ид удаленной записи, пользователя, дату и ид новой записи. Минусы - жойниться будет медленно.

Это всё понятно. Вопрос - какой бы вариант вы препочли и почему.

Да, забыл добавить, удаления без ввода нового документа быть не может никогда.