UC Irvine

Databases organize, derive, summarize, and expose data through queries, views, logs, caches, and downstream applications. As a result, deleting a value from a database does not necessarily remove what the system makes knowable about that value. For example, an employee's salary may be reconstructed from title and work hours; a user's location may be recovered from posts, and derived statistics. The deleted value of a target cell may remain inferable from other dependent data after the cell has been set to null. Meaningful deletion may therefore require deleting more than just the value of the target cell. The need to define meaningful deletion is reinforced by data regulations, which grant users the right to have their data deleted but do not provide a precise system-level interpretation of deletion. This dissertation studies a strong inference-resilient interpretation of deletion: how can a system prevent re-inference of a deleted value while minimizing additional deletions?To model inference, the dissertation introduces relational dependency rules (RDRs), an SQL-grounded language for describing data dependencies. Such dependencies are frequently present in semantically rich domains such as medical, social network applications, etc. Within this framework, information regarding a deleted value can leak through two channels: the post-deletion visible state of the database and the deletion pattern itself, namely the observable set of cells deleted in addition to the target cell.The first notion of deletion developed in the dissertation, Semantic Erasure Against Leakage (Seal), is a deterministic framework for inference-resilient deletion under binary dependencies. A dependency is treated as either supporting inference of the target or not. A deletion mechanism must ensure that the retained database and deletion pattern disallow the deleted value from being re-inferred beyond the reference allowed by the deletion semantics. We formulate a variant of SEAL named Pre-insertion Post-Erasure Equivalence (P2E2). P2E2 requires that, after erasure, the dependencies available for inferring the target be no stronger than those that existed when the target value was inserted. This offers a semantic rollback guarantee while avoiding the excessive cost of cascade-style approaches that delete all dependent data regardless of when the dependency arose.Semantic dependencies are often discovered from data or learned statistically, and hold approximately. To accommodate this, the dissertation develops Differential-SEAL (DiffSEAL), a probabilistic framework for inference-resilient deletion under weighted dependencies. Diff-SEAL bounds the adversary’s ability to re-infer the deleted value by a tunable threshold. It accounts separately for leakage through the post-deletion visible state and leakage through the deletion pattern, and combines the two channels on the log-odds scale to obtain an end-to-end bound on posterior recovery.We design mechanisms for P2E2 and Diff-SEAL and evaluate them on real-world datasets. The results show that meaningful deletion need not require the removal of all dependent data. By reasoning about when dependencies arise, how strongly they support inference, and what the deletion pattern reveals, the mechanisms can enforce inference-resilient deletion with reasonable overheads. Finally, the dissertation connects these deletion guarantees to regulatory compliance through Data-CASE, a framework for grounding ambiguous regulatory concepts into precise system actions. The dissertation does not seek, nor presume, to settle the legally authoritative meaning of erasure; instead, it shows how one strong technical interpretation can be formalized, implemented, and related to regulatory requirements. Together, these contributions frame deletion in databases from an operation on stored representations into a guarantee about what can be inferred after deletion.