> The idea of a relational schema having some kind of temporal dimension letting you get at changes is something that's been on my mind a lot lately.

You may want to check out Datomic. It uses an immutable, time-based model that covers deleted_at and many more scenarios (e.g., it's effortless to ask, "what was the state of this object last month?" without the need for looking at old backups.)