Meaningful Data Erasure in the Presence of Dependencies
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915420962816000 |
|---|---|
| author | Chakraborty, Vishal Kaminsky, Youri Mehrotra, Sharad Naumann, Felix Nawab, Faisal Pappachan, Primal Sadoghi, Mohammad Venkatasubramanian, Nalini |
| author_facet | Chakraborty, Vishal Kaminsky, Youri Mehrotra, Sharad Naumann, Felix Nawab, Faisal Pappachan, Primal Sadoghi, Mohammad Venkatasubramanian, Nalini |
| contents | Data 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_00343 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Meaningful Data Erasure in the Presence of Dependencies Chakraborty, Vishal Kaminsky, Youri Mehrotra, Sharad Naumann, Felix Nawab, Faisal Pappachan, Primal Sadoghi, Mohammad Venkatasubramanian, Nalini Databases Data 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. |
| title | Meaningful Data Erasure in the Presence of Dependencies |
| topic | Databases |
| url | https://arxiv.org/abs/2507.00343 |