Database immutability does not mean it's impossible to delete content.

It means you separate two use cases: retracting information (I remove an item from my shopping cart because I want another item) and purging data (I delete my account and all my shopping history because I don't want the shop to store my data anymore).

You can still purge data easily in Datomic, for example.