When I first encountered the problem my mind jumped to CVS. I'll just hack up a database-to-CVS bridge and handle it that way, thought I. But as I think about it further, I'm not sure that's a good idea. There's a large impedance mismatch between records in a database and files in CVS.
An alternative might be to have a version column in every table. The problem with this is that the primary key for each column is now (foo_id, version) rather than just (foo_id). I fear this will complicate the rest of the application enormously. Join tables in particular would become much less useful. It's so much nicer if a single integer is enough to identify a record.
Any bright ideas floating around in the monestary? Feel free to meditate on this one for a while - the application is at least a couple months away from implementation.
-sam