It depends on how you interpret “delete”. Most people seem to want to make it synonymous with “erase”, but it should really mean something like “forget”. In that case, it’s easy to see how you would implement “undo”: just drop all (root) references to the record(s) in question and collect as garbage at a certain time (in, say, 30 days).