Patterns for undo in multi-user applications on relational data

Question

I want to build a web application that will allow multiple users to collaboratively populate the contents of a fairly conventional relational database. (The database will have a fixed schema, which is known in advance).

I can see how to define the schema for the necessary object types, relations, and foreign key constraints (items, items as members of categories, links between items, and so on). Basic CRUD operations to instantiate and modify objects are no problem.

But for resilience against vandalism and mistakes, I can foresee that it will be necessary to have undo/rollback functionality, so that moderator-level users can undo changes made by other users. I'm having trouble figuring out a suitable approach to take for two key functional pre-requisites:

1. Capturing all the database changes that result from an initial user request. For example, there's a many-to-many relationship between items and categories. Therefore, if a category is deleted (triggered by a user submitting an HTML form), all the category-item relation records corresponding to that category will get deleted due to referential integrity constraints on the many-to-many relation. How can I record all the cascading consequences of an initial operation, so that's it's possible to completely undo it later?
2. How can I isolate undo operations so that a bad action by one user can be undone without also needing to roll back all the beneficial changes which have been made by other users, in between the bad action and the moderator's review?

The Undo patterns I've seen described (e.g. "Command" pattern) all assume that there is a stack of commands and undo operations are always applied in strict reverse order of initial application (no support for out-of-order undos).

Are there any standard patterns for handling undo capability in relational databases which would help meet these two goals? At the moment, I'm looking for generic algorithms and patterns which help solve the problems listed above, rather than platform-specific details.

Answer 1

What you're probably looking for is a schema like this:

    DOCUMENT
       |
DOCUMENT_VERSION
       |
DOCUMENT_CATEGORY

That is, each entity has a VERSION collection associated to it. When you do an edit, you store the entire new version under a new version record leaving the original untouched. Then you can implement a diff function to show the user the differences between two versions, and a rollback function to make a previous version the new active version.

These are basic functions in a lot of web applications, particularly Wikis. If you're using ASP.NET, you could consider downloading and installing ScrewTurn Wiki and look at how it handles versioning. It's open source.

Answer 2

The approach I have used is an audit table which records the before image and change time before each update or deletion. Each table would have its own audit table, populated by a trigger. This is usually combined with audit fields listing the change time and user making the change. The audit fields should populated by triggers to prevent spoofing.

Assuming a single userid was used for vandalism, this system should enable you to quickly identify potentially vandalized records.

To be able to back out changes, you would use a history browser, that allows a record to be replaced by a previous version.

Depending on your requirements, you may also want a database backup that allows you to perform point in time recovery. This would allow you to quickly restore to the point before vandalism started.