I'm not sure how to square the normalized schema with the immutability; normalization implies schema changes which imply data changes, no?
In particular, what do I do when there is erroneous historical data that violates the new schema (the newly discovered constraint that was there all along)?
Essentially they end up rebuilding the "transaction log" that most RDBMS's use to commit data safely.
Before any data is written to the "data" files of the database, it is written to a "log" file sequentially. Once that has succeeded, it will write to the data file, then write to the log file again to say that the write was successful.
That way if the database breaks during the write, the system knows about it. It's also useful because it allows you to restore the database to a point in time, as you have a full log of all the transactions run (and you know how to un-run them).
In this case, they just make the transaction log a little more accessible.
For your example, erroneous historical data would remain in the system but with a new record being added indicating that at a certain date and time the old record was replaced with the new one.
Basically if you think of a store processing a purchase for $100 and refund of $100 as 2 transactions (for $100 and -$100) rather than simply deleting the first transaction.
This is important because things may have happened between the deposit of money and its refunding (e.g. interest payments).
You have options. You can apply the schema restriction only to new inserts (since you have full control over where it's applied - the "all data" store is generally not an SQL DB).
You can "retcon" the old data (and knowing when to violate immutability is what separates the good from the great). You can make a new "table", and put the logic for dealing with the difference between old and new formats in the batch processor.
In particular, what do I do when there is erroneous historical data that violates the new schema (the newly discovered constraint that was there all along)?