A Never Delete Relational DB Schema Design

If your goal is auditing, I'd create a shadow table for each table you have. Add some triggers that get fired on update and delete and insert a copy of the row into the shadow table.

I think what you're looking for here is typically referred to as "knowledge dating".

In this case, your primary key would be your regular key plus the knowledge start date.

Your end date might either be null for a current record or an "end of time" sentinel.

On an update, you'd typically set the end date of the current record to "now" and insert a new record the starts at the same "now" with the new values.

On a "delete", you'd just set the end date to "now".

1. i've done that.

2.a) version number solves the unique constraint issue somewhat although that's really just relaxing the uniqueness isn't it.

2.b) you can also archive the old versions into another table.

There's a couple of ways to do this sort of thing; I've previously used an "active" flag, with a compound uniqueness constraint with the primary key and that flag on each table. This works well when you don't particularly care about deletion times, or if you already have a timestamp column for updates in your table (the flag gets updated at update time, and prevents a select on max "updated" column). I liked the solution; it's fast, and (relatively) simple.

Here are some additional questions that you'll also want to consider

1. How often do deletes occur. What's your performance budget like? This can affect your choices. The answer to your design will be different depending of if a user deleting a single row (like lets say an answer on a Q&A site vs deleting records on an hourly basis from a feed)

2. How are you going to expose the deleted records in your system. Is it only through administrative purposes or can any user see deleted records. This makes a difference because you'll probably need to come up with a filtering mechanism depending on the user.

3. How will foreign key constraints work. Can one table reference another table where there's a deleted record?

4. When you add or alter existing tables what happens to the deleted records?

Typically the systems that care a lot about audit use tables as Steve Prentice mentioned. It often has every field from the original table with all the constraints turned off. It often will have a action field to track updates vs deletes, and include a date/timestamp of the change along with the user.

For an example see the PostHistory Table at http://data.stackexchange.com/stackoverflow/query/new