This is 100% accurate. In some cases you can't use a unique on a column because of the "deleted" boolean or a state machine that is in a deleted state. I would venture to guess that this is where a NoSQL solution would come in handy. Just grab all the data they deleted, shove it into a nice json or xml data structure and store it in the nosql database as a document.