Meaningful Data Erasure in the Presence of Dependencies

Faisal Nawab; Felix Naumann; Mohammad Sadoghi; Nalini Venkatasubramanian; Primal Pappachan; Sharad Mehrotra; Vishal Chakraborty; Youri Kaminsky

REVIEW 4 major objections 5 minor 62 references

Meaningful Data Erasure in the Presence of Dependencies

T0 review · 4 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Erasing data should not reveal more than was known before insertion.

desk verdict P2E2 is a genuinely new erasure semantics, but the paper's key reduction theorem is unproved and likely false because it ignores cells in the dependency condition query. read the letter →

arxiv 2507.00343 v2 pith:R6XWHTIH submitted 2025-07-01 cs.DB

Vishal Chakraborty , Youri Kaminsky , Sharad Mehrotra , Felix Naumann , Faisal Nawab , Primal Pappachan , Mohammad Sadoghi , Nalini Venkatasubramanian This is my paper

classification cs.DB

keywords dataerasurerighttorelationaldependencyrulesP2E2inferencecontrolminimaldeletionretentiondatabasedependencies

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper sets out to give data erasure a semantics that survives the fact that cells in a database are often inferable from other cells. Its proposal, P2E2 (Pre-insertion Post-Erasure Equivalence), is that erasing a cell should not leave an observer able to infer anything about the erased value beyond what could already be inferred at the moment the value was inserted. To make this checkable, the paper expresses dependencies as relational dependency rules (RDRs), a SQL-like language for constraints and correlations, and compares the dependency sets around a cell at insertion time and after deletion. It then treats the extra cells whose erasure restores the guarantee as an optimization problem, offering exact solutions via integer linear programming and a hypergraph traversal, an approximation, and batching for pending erasure requests. If the guarantee holds, deletion compliance becomes a verifiable database operation rather than an ambiguous legal phrase.

What carries the argument

Relational dependency rules (RDRs) are the central object: each rule declares that an attribute $A(\mathbf{X})$ is not independent of other attributes $A_1(\mathbf{X}_1), \ldots, A_p(\mathbf{X}_p)$ whenever a SQL condition $Q$ holds over the records involved. Instantiating a rule on a database state produces a concrete dependency $\delta^-$ between named cells, and the set $\mathrm{dep}(A(\mathbf{x}) \mid D_t)$ collects every $\delta^-$ that can reach $A(\mathbf{x})$, directly or by chaining through shared cells. P2E2 is the subset condition comparing that set at expiration time (with the erased value restored for reasoning) against the set at insertion time; each violating instantiated dependency must be broken by deleting a cell from its head or tail, where the head is the cell being inferred and the tail cells are those it depends on. The dependence hypergraph $H(\Delta^-(\mathrm{P2E2}, A(\mathbf{x})))$ turns those choices into hyperedges, and Algorithm 2 propagates deletion costs bottom-up and extracts the cheapest deletion path top-down, an optimal strategy when the hypergraph is acyclic.

What would settle it

A concrete test: take the paper's Example 1.1 but leave the City–AreaCode constraint out of the declared RDR set. After deleting AreaCode, the remaining City value still confines AreaCode to {714, 949}, so the deleted value is inferable even though P2E2 holds for the declared rules. A system that returns compliant for this deletion would demonstrate that the guarantee's practical force depends entirely on the completeness of the dependency list.

Watch

Extended reading notes

Core claim

The paper's central discovery is Definition 3.5: for a cell $A(\mathbf{x})$ with insertion time $t_b$ and expiration time $t_e$, P2E2 holds exactly when $$dep(A(\mathbf{x}) \mid D_{t_e^+} \cup \{\mathrm{Val}(A(\mathbf{x})) \leftarrow val\}) \subseteq dep(A(\mathbf{x}) \mid D_{t_b}),$$ where $dep$ is the set of instantiated relational dependency rules through which $A(\mathbf{x})$ can be directly or indirectly inferred. The authors claim that this subset relation is the right formalization of meaningful erasure, because it permits only inferences that the database already supported before the data existed. They then show (Theorem 3.7) that finding the minimum-cost set of cells whose NULLing enforces the relation is NP-hard, and provide algorithms, including a reduction to ILP, an optimal dependence-hypergraph traversal on acyclic dependency graphs, and a greedy approximation, that compute such sets. The evaluation on five datasets reports that the number of extra deletions is usually small and that batching and retention scheduling reduce the overhead.

Load-bearing premise

The guarantee is only as strong as the supplied list of relational dependency rules: any real inference path not encoded as an RDR is invisible to P2E2, so erased data can still leak through an unlisted dependency.

Editorial extensions

If this is right

If P2E2 is adopted, deletion becomes a verifiable operation: an auditor can check the subset relation between dependency sets instead of trusting that the word delete removed the right data.
The minimal-deletion machinery gives a cost model for erasure: the integer-linear-programming and hypergraph algorithms identify the cheapest set of extra cells, so a system can report and justify the true cost of forgetting.
Batching requests within a grace period directly reduces overhead, because multiple cells share the same dependency neighborhood and can be NULLed with fewer instantiated rules.
Advance knowledge of retention times lets the system schedule derived-data reconstruction so that fewer reconstructions are wasted, which the experiments show cuts deletions and reconstructions on the evaluated workloads.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

An implicit consequence is that P2E2 makes the completeness of the dependency inventory the real compliance question: two deployments with identical database contents but different RDR lists can make opposite erasure decisions, and the paper gives no way to certify completeness.
The same subset-equivalence reasoning transfers to other settings where a deleted record could be reconstructed, such as machine-learning models and analytics pipelines; the paper mentions this direction but does not develop it.
A practical test suggested by the paper's design is to mine RDRs automatically from query logs, triggers, and application logic, so the dependency set tracks what the system actually does rather than what was declared; the evaluation already uses discovered constraints in some datasets, so this extension is within reach.
P2E2 could be composed with query-auditing or leakage-monitoring tools to catch inference paths that cross external knowledge bases, but that synthesis is not part of the paper.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Here's my take. The genuinely new thing in this paper is P2E2: erasure is defined relative to the dependency set at insertion time, so a deleted cell can only leave the system no more inferable than it was before it arrived. That is a clean and defensible baseline, and I don't know of a prior deletion semantics that states it this way. The RDR language is expressive enough to cover FDs, INDs, denial constraints, and even aggregate dependencies, and the evaluation on five datasets gives a useful first estimate of the cost—usually only a handful of extra deletions. Those pieces earn real credit.

The soft spot is load-bearing. Theorem 3.8 says a P2E2 violation can only come from an instantiated RDR containing a cell inserted after the target cell. It is stated without proof, and as written it is not true. The instantiated RDR keeps only the cells in the dependence statement; the condition query can mention other cells—timestamps, join tables, aggregates—that change after t_b. A dependency can become active at t_e while all of Cells(delta) are old. Example: R2's condition uses pTm > dTm; updating dTm after t_b can make a pre-existing pLoc/lstLoc pair satisfy the rule. Theorem 3.8's reduction would miss that violation. Algorithm 1, the ILP, and the hypergraph methods all rely on that reduction, so the correctness and minimality claims are unsupported until the theorem is repaired or the definition is changed to include condition cells in the instantiated rule.

Smaller issues: Theorem 3.7's NP-hardness is asserted with no reduction; Theorem 4.4's optimality depends on acyclicity plus an ad hoc tail-overlap pruning rule; Algorithm 3 line 8 uses Sch[0] where it should use Sch[i]; and the experimental plots lack variance. These are addressable. Section 8's caveat that P2E2 protects only against specified dependencies is honestly stated and is a scope limit, not a flaw.

Who is this for? Researchers in regulatory-compliant storage and deletion semantics. The P2E2 idea is worth discussing and refining, and I would send it to referees. But the revision needs to either prove a corrected version of Theorem 3.8 under a precisely restricted condition language, or bite the bullet and track condition-referenced cells in the dependency set. I would not accept the current version as is.

Referee Report

4 major / 5 minor

Summary. The paper proposes a formal semantics for data erasure in the presence of dependencies, called Pre-insertion Post-Erasure Equivalence (P2E2). P2E2 requires that, after a cell is erased, the set of dependencies on that cell—evaluated in the post-erasure state with the erased value restored for reasoning—is a subset of the dependencies that existed at the time the cell was inserted. The authors introduce Relational Dependency Rules (RDRs) to capture dependencies, characterize the violating dependencies as those containing at least one cell inserted after the target cell (Theorem 3.8), and develop exact and approximate algorithms (ILP, hypergraph-based, and greedy) to compute a minimal-cost set of additional cells to erase. They also propose batching and retention-driven scheduling strategies and report an experimental study over five datasets with an available artifact.

Significance. If the stated theorems are rigorously established, P2E2 provides a concrete, checkable formal semantics for erasure that addresses the inference problem highlighted in regulations such as GDPR's prohibition on reconstructing deleted data. The paper's strengths include explicit cell-level semantics, a pragmatic rule language (RDRs) capable of expressing diverse dependencies, a simplification of the compliance condition via post-insertion dependencies, released code and data, and a broad comparison of algorithmic strategies on real and synthetic workloads. The authors are also honest about the central limitation: the guarantee is relative to the supplied list of RDRs, and protection against inferences not encoded as RDRs is explicitly deferred to future work (Section 8).

major comments (4)

[3.4, Theorem 3.8] Theorem 3.8 is stated without proof, yet it is the load-bearing simplification that allows the algorithms to compute Δ−(P2E2, A(𝒙)) without constructing full dependency sets at both time points. The claim that the only violating dependencies are those containing a post-insertion cell requires a rigorous argument that handles the transitive closure in Definition 3.4, the presence of erased cells (which set values to NULL and thus remove dependencies), and the fact that Definition 3.5 evaluates P2E2 on D_te+ with A(𝒙) restored while Theorem 3.8 speaks about D_te. Please provide a complete proof, or a counterexample-free formal derivation, clarifying exactly which state (pre- or post-erasure of A(𝒙)) is used in the characterization.
[3.3, Theorem 3.7] Theorem 3.7 states that Opt-P2E2 is NP-hard, but no proof, reduction, or citation is provided. Since the paper presents exact algorithms (ILP, and HGr under an acyclicity assumption) and a heuristic with an approximation bound, the hardness claim is not needed for the algorithmic contributions to hold, but as a formal theorem it must be supported. Please include a reduction (e.g., from set cover or vertex cover) or move the statement to a conjecture with a clear justification.
[4.3, Theorem 4.4 and footnote 5] The optimality claim for Algorithm 2 is conditioned on the dependence hypergraph being cycle-free, and the footnote then imposes a rule-discarding heuristic (if Tail(δ₁) ∩ Tail(δ₂) ≠ ∅, discard the RDR with the larger tail) to ensure acyclicity. Consequently, the optimality result is relative to a modified set of RDRs, not the original Opt-P2E2 input. It is unclear whether the solutions produced are optimal, or even correct, for the original dependency set when such discarding occurs. Please state precisely the class of instances for which Algorithm 2 is optimal for the original problem, and verify whether the experimental RDR sets guarantee no discard is needed.
[4.1, Algorithm 1] The specification of the eval() function (line 9) is vague: the text says it 'determines if the rule could have been used for inference in the state D_κ(A(𝒙))− (Thm. 3.8)', but Theorem 3.8 concerns dependencies containing cells inserted after t_b, not a per-rule test on the insertion-time state. Because Algorithm 1 is used by all subsequent algorithms and by the evaluation, the semantics of eval must be pinned down explicitly and proven to compute exactly the set Δ−(P2E2, A(𝒙)) as characterized by Theorem 3.8.

minor comments (5)

[3.4, Theorem 3.8] There are typographical errors in the theorem statement: the set notation is inconsistent (e.g., 'dep(A(𝒙|D_tb}' and 'dep(A(𝒙)|D_tb−E}') and the time subscript in 'η(κ)(𝒙)' appears garbled.
[Definition 3.5] The notation 'dep(A(𝒙)|D_te+) ∪ {Val(A(𝒙))←val})' is confusing; it should be written as dep(A(𝒙)| D_te+[A(𝒙):=val]) or explained that the value of A(𝒙) is restored for the purpose of evaluating the dependency set.
[Definition 3.4] The definition of indirect dependency is hard to parse: the condition 'A(𝒙)∈ Cells(δ₁)' in a chain should be clarified, and the direction of the chain (whether it represents inference toward or away from A(𝒙)) should be stated unambiguously.
[Algorithm 2] The cost update 'Sum(Cost(attf), min Cost(Tail(δ)))' uses the functions 'Sum' and 'min' without formal definition, and the pseudocode would benefit from a concrete specification of the cost semantics, especially why erasing a head also requires erasing a tail cell.
[6.2, Experiment 1] The sentence 'all three baseline methods delete significantly more data than our P2E2 algorithms on every dataset except Tax' is immediately qualified but the exception is not explained until later in the same paragraph; consider moving the explanation earlier to avoid confusion.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: P2E2 is defined directly from dependency sets and enforced by algorithms without fitted parameters or load-bearing self-citations.

full rationale

The paper's central contribution, P2E2 (Definition 3.5), is a formal definition stated directly in terms of dependency sets relative to a supplied set of relational dependency rules. It is not derived from a fitted quantity, and no parameter is tuned to make the guarantee hold. The enforcement algorithms (ILP, dependence hypergraph, approximate, and batching) target the formally defined Opt-P2E2 problem, so their outputs are checked against the definition rather than being constructed to match it. The paper explicitly acknowledges that P2E2 is relative to the specified RDRs and defers protection against unspecified inferences to future work; this is a stated limitation of scope, not a circular step. The authors do cite their own prior work, notably in the discovery of dependency rules and in related-work discussion, but none of these citations carries the load of the formal derivation. The unproven Theorem 3.8, which the algorithms rely on for efficient instantiation, is a correctness risk and an omitted proof, but it is not circular: it is a claimed mathematical reduction, not an input that is renamed as an output. For these reasons, the circularity burden is negligible, and the correct score is 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central claim uses only operator-supplied inputs: deletion costs, retention times, grace periods, and RDRs. No free parameter is fitted to make P2E2 work. The principal axioms are non-adversarial ownership, completeness of the RDR set, the update-as-delete-plus-insert model, and acyclicity for the hypergraph optimality proof. No new physical entities are introduced.

assumptions (5)

domain assumption The database owner is non-adversarial and has no hidden copies of erased data; the database state and all dependencies are visible at erasure time.
Section 3.3 explicitly assumes no malicious database owner maintains a secret copy, which is load-bearing for the P2E2 guarantee.
domain assumption All inference channels relevant to erasure are captured by the supplied RDR set; RDRs are complete enough for the guarantee.
Section 3.1 takes a list of RDRs as input, and Section 8 concedes that protecting against any potential inference is future work.
domain assumption Updating a cell is modeled as erasure followed by insertion, resetting the creation timestamp while retaining the expiration timestamp.
Section 2's Base Relations paragraph defines update semantics this way, and P2E2's dependency comparison depends on that reset.
domain assumption The instantiated dependence hypergraph is acyclic for Algorithm 2 to be optimal.
Section 4.3 states the cycle-free assumption is needed for optimality, and the paper discards RDRs with overlapping tails to enforce it.
domain assumption Instantiated RDRs are only considered when all cells in the rule are non-NULL.
Definition 3.4 restricts dependency sets to rules whose cells are non-NULL; this is why P2E2 compares with the erased cell's value temporarily restored.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Meaningful Data Erasure in the Presence of Dependencies." pith.science (2026). https://pith.science/paper/R6XWHTIH

@misc{pith2026250700343,
  author       = {Pith},
  title        = {Pith review of: Meaningful Data Erasure in the Presence of Dependencies},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/R6XWHTIH}},
  note         = {Machine review of arXiv:2507.00343}
}

read the original abstract

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.

Figures

Figures reproduced from arXiv: 2507.00343 by the authors.

**Figure 2.** Example of a dependence hypergraph. For a dependence hypergraph H (Δ − (P2E2, A(𝒙))) = (𝑉 , 𝐸), a vertex 𝑣 ∈ 𝑉 is called a root if 𝑣 is not in the tail of any instantiated RDR, i.e., for all 𝛿𝑖 ∈ Δ − (D𝑡) we have 𝑣 ∉ Tail(𝛿𝑖). Similarly, a vertex 𝑣 ∈ 𝑉 is called a leaf if 𝑣 is not the head of any instantiated RDR, i.e., for all 𝛿𝑖 ∈ Δ − (D𝑡) we have 𝑣 ∉ Head(𝛿𝑖) [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗

**Figure 3.** Evaluation of demand-driven erasures highlight the similarity within these groups by using the same axis scaling. RDRs for the HotCRP and TPC-H datasets were created using data dependencies from schema constraints (or IND discovery). DBMSs already include a mechanism to delete data linked by foreign keys. Thus, there is no overhead to guarantee P2E2. Interestingly, neither the number of rules, nor the dataset size … view at source ↗

Figures from the paper (2 more)

**Figure 4.** Figure 4: Impact of dependencies (log-axis) on P2E2 overhead; [PITH_FULL_IMAGE:figures/full_fig_p010_4.png]

**Figure 6.** Figure 6: Number of saved reconstructions vs. grace period [PITH_FULL_IMAGE:figures/full_fig_p011_6.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

62 extracted references · 57 canonical work pages

[1]

Archita Agarwal, Marilyn George, Aaron Jeyaraj, and Malte Schwarzkopf. 2022. Retrofitting GDPR Compliance onto Legacy Databases. PVLDB 15, 4 (2022), 958–970

work page 2022
[2]

Kinan Dak Albab, Ishan Sharma, Justus Adam, Benjamin Kilimnik, Aaron Jeyaraj, Raj Paul, Artem Agvanian, Leonhard Spiegelberg, and Malte Schwarzkopf. 2023. K9db: Privacy-Compliant Storage for Web Applications by Construction. In Proceedings of the 17th USENIX Symposium on Operating Systems Design and Implementation (OSDI 23). USENIX Association, Boston, MA...

work page 2023
[3]

Marcelo Arenas, Leopoldo Bertossi, and Jan Chomicki. 1999. Consistent Query Answers in Inconsistent Databases. In Proceedings of the Symposium on Principles of Database Systems (PODS) . ACM, New York, NY, 68–79. https://doi.org/10. 1145/303976.303983

work page arXiv 1999
[4]

Manos Athanassoulis, Subhadeep Sarkar, Zichen Zhu, and Dimitris Staratzis

work page
[5]

Leopoldo Bertossi. 2006. Consistent Query Answering in Databases. ACM SIGMOD Record 35, 2 (2006), 68–76

work page 2006
[6]

Leopoldo Bertossi. 2011. Database Repairing and Consistent Query Answering . Morgan & Claypool Publishers

work page 2011
[7]

Tobias Bleifuß, Sebastian Kruse, and Felix Naumann. 2017. Efficient denial constraint discovery with Hydra. PVLDB 11, 3 (2017), 311–323

work page 2017
[8]

Tobias Bleifuß, Thorsten Papenbrock, Thomas Bläsius, Martin Schirneck, and Felix Naumann. 2024. Discovering Functional Dependencies through Hitting Set Enumeration. Proceedings of the International Conference on Management of Data (SIGMOD) 2, 1 (2024), 1–24

work page 2024

Show all 62 references

[9]

Philip Bohannon, Wenfei Fan, Floris Geerts, Xibei Jia, and Anastasios Kementsi- etsidis. 2007. Conditional Functional Dependencies for Data Cleaning. In Pro- ceedings of the IEEE International Conference on Data Engineering (ICDE) . IEEE, 746–755

2007
[10]

Choquette-Choo, Hen- grui Jia, Adelin Travers, Baiwu Zhang, David Lie, and Nicolas Papernot

Lucas Bourtoule, Varun Chandrasekaran, Christopher A. Choquette-Choo, Hen- grui Jia, Adelin Travers, Baiwu Zhang, David Lie, and Nicolas Papernot. 2021. Machine Unlearning. In Proceedings of the 2021 IEEE Symposium on Security and Privacy (S&P). IEEE, 141–159

2021
[11]

Brazil. 2018. Lei Geral de Proteção de Dados (LGPD) - Article 18(IV). https: //www.gov.br/cidadania/pt-br/acesso-a-informacao/lgpd Brazilian Federal Law No. 13,709/2018. Last accessed on 2025-01-10

2018
[12]

California. 2018. Title 1.81.5. California Consumer Privacy Act of 2018 [1798.100 - 1798.199.100]. California Legislative Information. https://leginfo.legislature.ca.gov/faces/codes_displayText.xhtml?division=3. &part=4.&lawCode=CIV&title=1.81.5 California Civil Code. Last acc...

2018
[13]

Canada. 2000. Personal Information Protection and Electronic Documents Act (S.C. 2000, c. 5). https://laws-lois.justice.gc.ca/ENG/ACTS/P-8.6/index.html Justice Laws Website. Last accessed on 2025-01-10

2000
[14]

Nicholas Carlini, Steve Chien, Milad Nasr, Shuang Song, Andreas Terzis, and Florian Tramer. 2022. Membership Inference Attacks from First Principles. In Proceedings of the 2022 IEEE Symposium on Security and Privacy (S&P) . IEEE, 1897–1914

2022
[15]

Vishal Chakraborty, Stacy Ann-Elvy, Sharad Mehrotra, Faisal Nawab, Mohammad Sadoghi, Shantanu Sharma, Nalini Venkatsubhramanian, and Farhan Saeed. 2024. Data-CASE: Grounding Data Regulations for Compliant Data Processing Systems. In Proceedings of the International Conference ...

2024
[16]

James Cheney, Laura Chiticariu, and Wang-Chiew Tan. 2009. Provenance in Databases: Why, How, and Where. Foundations and Trends in Databases 1, 4 (April 2009), 379–474. https://doi.org/10.1561/1900000006

2009 doi
[17]

Jan Chomicki and Jerzy Marcinkowski. 2005. Minimal-Change Integrity Main- tenance Using Tuple Deletions. Information and Computation 197, 1-2 (2005), 90–121

2005
[18]

Katriel Cohn-Gordon, Georgios Damaskinos, Divino Neto, Joshi Cordova, Benoît Reitz, Benjamin Strahs, Daniel Obenshain, Paul Pearce, and Ioannis Papagiannis
[19]

Ilyas, Mourad Ouzzani, and Nan Tang

Michele Dallachiesa, Amr Ebaid, Ahmed Eldawy, Ahmed Elmagarmid, Ihab F. Ilyas, Mourad Ouzzani, and Nan Tang. 2013. NADEEF: A Commodity Data Cleaning System. In Proceedings of the International Conference on Management of Data (SIGMOD). ACM, New York, NY, USA, 541–552

2013
[20]

Ghana Data Protection Commission. 2012. Data Protection Act. https://nca. org.gh/wp-content/uploads/2020/09/Data-Protection-Act-2012.pdf Accessed: 2025-04-02

2012
[21]

enryu43. 2023. Twitter 100 Million Tweets Dataset. https://huggingface.co/ datasets/enryu43/twitter100m_tweets Accessed: 2025-01-25

2023
[22]

European Parliament and Council of the European Union. 2016. Regulation (EU) 2016/679 (General Data Protection Regulation). https://eur-lex.europa. eu/eli/reg/2016/679/oj Official Journal of the European Union. Last accessed on 2025-01-10

2016
[23]

European Parliament and Council of the European Union. 2024. Regulation (EU) 2024/1689: Artificial Intelligence Act. https://eur-lex.europa.eu/eli/reg/2024/ 1689/oj/eng Official Journal of the European Union. Last accessed on 2025-01-10

2024
[24]

Ronald Fagin, Benny Kimelfeld, Frederick Reiss, and Stijn Vansummeren. 2016. Declarative Cleaning of Inconsistencies in Information Extraction. ACM Trans- actions on Database Systems (TODS) 41, 1 (2016), 1–44

2016
[25]

Wenfei Fan, Floris Geerts, Xibei Jia, and Anastasios Kementsietsidis. 2008. Con- ditional functional dependencies for capturing data inconsistencies. ACM Trans- actions on Database Systems (TODS) 33, 2 (2008), 1–48

2008
[26]

Helena Galhardas, Daniela Florescu, Dennis Shasha, Eric Simon, and Cristian- Augustin Saita. 2001. Declarative Data Cleaning: Language, Model, and Algo- rithms. In Proceedings of the International Conference on Very Large Databases (VLDB) (2013) . Morgan Kaufmann Publishers In...

2013
[27]

Ullman, and Jennifer Widom

Hector Garcia-Molina, Jeffrey D. Ullman, and Jennifer Widom. 2009. Database Systems: The Complete Book (2nd ed.) . Pearson Education

2009
[28]

Dan Geiger, Azaria Paz, and Judea Pearl. 1991. Axioms and algorithms for inferences involving probabilistic independence. Information and Computation 91, 1 (1991), 128–141

1991
[29]

Amir Gilad, Daniel Deutch, and Sudeepa Roy. 2020. On Multiple Semantics for Declarative Database Repairs. In Proceedings of the International Conference on Management of Data (SIGMOD) . ACM, New York, NY, USA, 817–831

2020
[30]

Green, Grigoris Karvounarakis, Zachary G

Todd J. Green, Grigoris Karvounarakis, Zachary G. Ives, and Val Tannen. 2007. Provenance Semirings. In Proceedings of the Twenty-Sixth ACM SIGMOD-SIGACT- SIGART Symposium on Principles of Database Systems (PODS ’07) (Beijing, China). ACM, New York, NY, USA, 31–40

2007
[31]

Green, Grigoris Karvounarakis, Zachary G

Todd J. Green, Grigoris Karvounarakis, Zachary G. Ives, and Val Tannen. 2007. Update Exchange with Mappings and Provenance. In Proceedings of the Interna- tional Conference on Very Large Databases (VLDB) . ACM, New York, NY, USA, 675–686

2007
[32]

Peeyush Gupta, Michael J Carey, Sharad Mehrotra, and oberto Yus. 2020. Smart- Bench: a benchmark for data management in smart spaces. Proceedings of the VLDB Endowment 13, 12 (2020), 1807–1820

2020
[33]

Ilyas, Volker Markl, Peter Haas, Paul Brown, and Ashraf Aboulnaga

Ihab F. Ilyas, Volker Markl, Peter Haas, Paul Brown, and Ashraf Aboulnaga. 2004. CORDS: automatic discovery of correlations and soft functional dependencies. In Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD). ACM, New York, NY, USA, 647–658

2004
[34]

Youri Kaminsky, Eduardo HM Pena, and Felix Naumann. 2023. Discovering similarity inclusion dependencies. Proceedings of the International Conference on Management of Data (SIGMOD) 1, 1 (2023), 1–24

2023
[35]

Subhash Khot and Oded Regev. 2008. Vertex cover might be hard to approximate to within 2-𝜀. J. Comput. System Sci. 74, 3 (2008), 335–349

2008
[36]

Eddie Kohler. 2024. HotCRP: Conference Review System. https://github.com/ kohler/hotcrp Accessed: 2025-01-25

2024
[37]

Michael Kuperberg. 2020. Towards Enabling Deletion in Append-Only Blockchains to Support Data Growth Management and GDPR Compliance. In Proceedings of the IEEE International Conference on Blockchain (Blockchain) . IEEE, Piscataway, NJ, USA, 393–400

2020
[38]

Andrei Lopatenko and Leopoldo Bertossi. 2007. Complexity of Consistent Query Answering in Databases under Cardinality-Based and Incremental Repair Se- mantics. In Proceedings of the International Conference on Database Theory (ICDT) . Springer, Berlin, Heidelberg, 179–193

2007
[40]

Meta. 2017. Permanently Delete Your Facebook Account. https://www.facebook. com/help/224562897555674. Accessed: 2025-01-14

2017
[41]

MySQL. 2019. MySQL Triggers. https://dev.mysql.com/doc/refman/9.0/en/ trigger-syntax.html. Accessed:2025-01-10

2019
[42]

Eduardo HM Pena, Fabio Porto, and Felix Naumann. 2022. Fast Algorithms for Denial Constraint Discovery. PVLDB 16, 4 (2022), 684–696

2022
[43]

Eduardo H. M. Pena, Eduardo C. de Almeida, and Felix Naumann. 2019. Discovery of Approximate (and Exact) Denial Constraints. PVLDB 13, 3 (2019), 266–278

2019
[44]

Ilyas, and Christopher Ré

Theodoros Rekatsinas, Xu Chu, Ihab F. Ilyas, and Christopher Ré. 2017. Holo- Clean: holistic data repairs with probabilistic inference. PVLDB 10, 11 (Aug. 2017), 1190–1201. https://doi.org/10.14778/3137628.3137631

2017
[45]

Eduard Rupp, Emmanuel Syrmoudis, and Jens Grossklags. 2022. Leave no data behind–empirical insights into data erasure from online services. Proceedings on Privacy Enhancing Technologies 3 (2022), 437–455

2022
[46]

Subhadeep Sarkar and Manos Athanassoulis. 2022. Query Language Support for Timely Data Deletion. In Proceedings of the International Conference on Extending Database Technology (EDBT). OpenProceedings, Online, 418–429. https://doi. org/10.48786/edbt.2022.35

2022 doi
[47]

Subhadeep Sarkar, Jean-Pierre Banâtre, Louis Rilling, and Christine Morin. 2018. Towards Enforcement of the EU GDPR: Enabling Data Erasure. In Proceedings of the 11th IEEE International Conference on Internet of Things (iThings 2018) . IEEE, Halifax, Canada, 1–8

2018
[48]

Subhadeep Sarkar, Tarikul Islam Papon, Dimitris Staratzis, and Manos Athanas- soulis. 2020. Lethe: A Tunable Delete-Aware LSM Engine. In Proceedings of the International Conference on Management of Data (SIGMOD) . ACM, New York, NY, USA, 893–908. https://doi.org/10.1145/331846...

2020
[49]

Subhadeep Sarkar, Dimitris Staratzis, Ziehen Zhu, and Manos Athanassoulis
[50]

Supreeth Shastri, Vinay Banakar, Melissa Wasserman, Arun Kumar, and Vijay Chidambaram. 2020. Understanding and Benchmarking the Impact of GDPR on Database Systems. Proceedings of the VLDB Endowment (PVLDB) 13, 7 (mar 2020), 1064–1077

2020
[51]

David W Shipman. 1981. The functional data model and the data languages DAPLEX. ACM Transactions on Database Systems (TODS) 6, 1 (1981), 140–173

1981
[52]

Singapore. 2012. Personal Data Protection Act 2012 (PDPA) - Part IV: Retention Limitation Obligation. https://sso.agc.gov.sg/Act/PDPA2012 Singapore Statutes Online. Last accessed on 2025-01-10

2012
[53]

Slawomir Staworko. 2007. Declarative Inconsistency Handling in Relational and Semi-Structured Databases. PhD Thesis. State University of New York at Buffalo. https://cse.buffalo.edu/tech-reports/2007-11.pdf

2007
[54]

Transaction Processing Performance Council. 2021. TPC-H Benchmark Speci- fication, Version 2.17.3. Technical Report. Transaction Processing Performance Council. http://www.tpc.org/tpch/

2021
[55]

Ujcich, Adam Bates, and William H

Benjamin E. Ujcich, Adam Bates, and William H. Sanders. 2018. A Provenance Model for the European Union General Data Protection Regulation. InProceedings of the International Provenance and Annotation Workshop (IPA W). Springer, 45–57

2018
[56]

United States. 2003. HIPAA Security Rule - 45 CFR §164.310(d)(2)(i). https://www.ecfr.gov/current/title-45/subtitle-A/subchapter-C/part- 164/subpart-C/section-164.310 U.S. Code of Federal Regulations. Last accessed on 2025-01-10

2003
[57]

Virginia. 2021. SB 1392: Consumer Data Protection Act (Virginia). https://lis. virginia.gov/cgi-bin/legp604.exe?211+sum+SB1392 Virginia General Assembly. Last accessed on 2025-01-10

2021
[58]

Yang Wang, Pedro Giovanni Leon, Alessandro Acquisti, Lorrie Faith Cranor, Alain Forget, Norman Sadeh, Norman Sadeh, Lorrie Faith Cranor, Alain Forget, and Norman Sadeh. 2014. A Field Trial of Privacy Nudges for Facebook. In Proceedings of the SIGCHI Conference on Human Factors...

2014
[59]

WhatsApp. 2020. About Disappearing Messages. https://faq.whatsapp.com/ 673193694148537/?helpref=uf_share Last accessed on 2025-01-10

2020
[60]

Lefeng Zhang, Tianqing Zhu, Haibin Zhang, Ping Xiong, and Wanlei Zhou. 2023. FedRecovery: Differentially Private Machine Unlearning for Federated Learning Frameworks. IEEE Transactions on Information Forensics and Security 18 (2023), 4732–4746

2023
[2020]

In Proceedings of the 29th USENIX Conference on Security Symposium (SEC)

DELF: Safeguarding Deletion Correctness in Online Social Networks. In Proceedings of the 29th USENIX Conference on Security Symposium (SEC) . USENIX, USA, Article 60, 18 pages
[2021]

PVLDB 14, 11 (jul 2021), 2216–2229

Constructing and analyzing the LSM compaction design space. PVLDB 14, 11 (jul 2021), 2216–2229. https://doi.org/10.14778/3476249.3476274

2021
[2022]

IEEE Data Engineering Bulletin 45, 1 (2022), 21–36

Building Deletion-Compliant Data Systems. IEEE Data Engineering Bulletin 45, 1 (2022), 21–36. http://sites.computer.org/debull/A22mar/p21.pdf

2022

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.

[1] [1]

Archita Agarwal, Marilyn George, Aaron Jeyaraj, and Malte Schwarzkopf. 2022. Retrofitting GDPR Compliance onto Legacy Databases. PVLDB 15, 4 (2022), 958–970

work page 2022

[2] [2]

Kinan Dak Albab, Ishan Sharma, Justus Adam, Benjamin Kilimnik, Aaron Jeyaraj, Raj Paul, Artem Agvanian, Leonhard Spiegelberg, and Malte Schwarzkopf. 2023. K9db: Privacy-Compliant Storage for Web Applications by Construction. In Proceedings of the 17th USENIX Symposium on Operating Systems Design and Implementation (OSDI 23). USENIX Association, Boston, MA...

work page 2023

[3] [3]

Marcelo Arenas, Leopoldo Bertossi, and Jan Chomicki. 1999. Consistent Query Answers in Inconsistent Databases. In Proceedings of the Symposium on Principles of Database Systems (PODS) . ACM, New York, NY, 68–79. https://doi.org/10. 1145/303976.303983

work page arXiv 1999

[4] [4]

Manos Athanassoulis, Subhadeep Sarkar, Zichen Zhu, and Dimitris Staratzis

work page

[5] [5]

Leopoldo Bertossi. 2006. Consistent Query Answering in Databases. ACM SIGMOD Record 35, 2 (2006), 68–76

work page 2006

[6] [6]

Leopoldo Bertossi. 2011. Database Repairing and Consistent Query Answering . Morgan & Claypool Publishers

work page 2011

[7] [7]

Tobias Bleifuß, Sebastian Kruse, and Felix Naumann. 2017. Efficient denial constraint discovery with Hydra. PVLDB 11, 3 (2017), 311–323

work page 2017

[8] [8]

Tobias Bleifuß, Thorsten Papenbrock, Thomas Bläsius, Martin Schirneck, and Felix Naumann. 2024. Discovering Functional Dependencies through Hitting Set Enumeration. Proceedings of the International Conference on Management of Data (SIGMOD) 2, 1 (2024), 1–24

work page 2024