How to design a SQL db with undo-redo?

Question

I'm trying to figure out how to design my DB tables to allow Undo-Redo.

Pretend you have a tasks table with the following structure:

id <int>
title <varchar>
memo <string>
date_added <datetime>
date_due <datetime>

Now assume that over a few days and multiple log-ins that several edits have taken place; but a user wants to go back to one of the versions.

1. Would you have a separate table tracking the changes - or - would you try to keep the changes within the tasks table ("ghost" rows, for lack of a better term)?
2. Would you track all of the columns or just the ones that changed each time?

If it matters, I'm using MySQL. Also, if it matters, I'd like to be able to show the history (ala Photoshop) and allow a user to switch to any version.

Bonus question: Would you save the whole memo cell on a change or would you try to save the delta only? Reason I ask is because the memo cell could be large and only a single word or character might be changed each revision. Granted, saving the delta would require parsing, but if undos aren't expected very often, wouldn't it be better to save space rather than processing time?

Thank you for your help.

Answer 1

I would create a History table for your tasks table. Same structure as tasks + a new field named previousId. This would hold the previous change id, so you can go back an forth through different changes (undo/redo).

Why a new History table? For a simple reason: do not overload tasks table with things that it was not designed for.

As for space, in the History, instead of a Memo, use a binary format and zip the content of the text you want to store. Don't try to detect changes. You will run into a buggy code which will result in frustration and wasted time...

Optimization: Even better, you may keep only three columns in History table: 1. taskId (foreign key to tasks) 2. data - a binary field. Before saving in the History table, create an XML string holding only the fields that have changed. 3. previousId (will help maintain a queue of changes and allow navigation back and forth)

As for data field, create an XML string like this:

<task>
  <title>Title was changed</title>
  <date_added>2011-03-26 01:29:22<date_added>
</task>

This will basically tell you that this time you changed only the title and the date_added fields.

After the XML string is built, just zip it if you want and store it into History table's data field.

XML will also allow for flexibility. If you add / remove a field in tasks table, you don't need to update the History table, too. So this way the structure of the tasks table and History table are decoupled so you don't need to update two tables each time.

PS: don't forget to add some indexes to quickly navigate through the history table. Fields to be indexed: taskId and previousId as you will need fast queries against this table.

Hope this helps.