Journal ArticleMeaningful Data Erasure in the Presence of DependenciesChakraborty, Vishal; Kaminsky, Youri; Mehrotra, Sharad; Naumann, Felix; Nawab, Faisal; Pappachan, Primal; Sadoghi, Mohammad; Venkatasubramanian, NaliniData regulations like GDPR require systems to support data erasure but leave the definition of erasure open to interpretation. This ambiguity makes compliance challenging, especially in databases where data dependencies can lead to erased data being inferred from remaining data. We formally define a precise notion of data erasure that ensures any inference about deleted data, through dependencies, remains bounded to what could have been inferred before its insertion. We design erasure mechanisms that enforce this guarantee at minimal cost. Additionally, we explore strategies to balance cost and throughput, batch multiple erasures, and proactively compute data retention times when possible. We demonstrate the practicality and scalability of our algorithms using both real and synthetic datasets.ACM Proceedings of the VLDB Endowment, Volume 18, Issue 102025-06-0110677220Proceedings of the VLDB Endowment18103435 to 34482150-8097https://doi.org/10.14778/3748191.37482062133391; 2420846; 1952247National Science Foundation