Verified erasure: lineage as an executable erasure program

Right-to-erasure inside a warehouse is a graph coverage problem. The DELETE is trivial; knowing the complete set of places to run it is not. A platform primitive would have the customer declare identity roots, propagate subject semantics through temporal lineage, compile an erasure plan, and emit evidence for both coverage and execution.

The propagation half of that is not speculative. One company already runs it in production.

Meta already ships obligation-carrying lineage

Policy Zones is Meta’s enforcement layer for purpose limitation, built on information flow control over data lineage. The governing rule: “The restrictions on downstream data must be equal to or more restrictive than those of the upstream source” (Meta Engineering, July 23 2025). Datasets carry Governable Data Annotations — “precise, governed annotations on datasets that describe the kinds of data that are subject to purpose-use limitations.” A Unified Programming Model intercepts SQL and builds semantic trees of inputs, outputs, and transformations. Derived datasets inherit upstream annotations automatically.

The numbers are not a pilot. Millions of datasets, tens of millions of data flows daily, hundreds of distinct policy requirements per flow, over an exabyte-scale warehouse.

Two mechanisms in that system matter for erasure. Reclassification lets an owner “stop propagation of sensitive data labels when the data is transformed to no longer be sensitive,” gated on privacy-preserving transformations or routine review. For opaque operators outside SQL, Meta falls back to coarse-grained separation and siloing rather than pretending the flow was analyzed. The broader program, Privacy Aware Infrastructure, splits into four layers: annotation, propagation, enforcement, verification.

So the thesis that lineage should carry obligations rather than only provenance is not a prediction. It is a shipped system with published scale numbers.

What erasure needs that purpose limitation does not

Policy Zones never has to find one person. That is the entire difference, and it splits into two requirements.

Addressability. Purpose limitation asks a dataset-level question: is this table restricted, and may it flow there. Erasure asks a row-level question: which rows here belong to subject 123, and can I select them deterministically. A lattice check over labels gives you the first and says nothing about the second.

Coverage proof. A purpose-limitation check that blocks a flow is self-evidently right at that flow — the enforcement point is the proof. An erasure claim is the opposite shape. It is a statement about everywhere the platform did not look. You cannot demonstrate it by pointing at the work you did.

Those two are what a platform would add on top of propagation. The DELETE is the least interesting part.

The DIY baseline today

Databricks documents the pattern rather than a primitive. The recommended process is to delete from the bronze layer on a scheduled job driven by a deletion-requests table, propagate to silver and gold, and maintain tables to remove historical data. Customers identify the affected tables themselves, and the guidance is explicit that “GDPR and CCPA apply to all data, including data in sources outside of Delta Lake, such as Kafka, files, and databases.” On obfuscation versus removal it is unambiguous: “Complete deletion is preferable to obfuscation” (Databricks documentation).

That is three separate customer obligations dressed as one runbook: find the tables, order the propagation correctly, and know when historical copies are actually gone.

The timing constraint is real too. GDPR Article 17(1) requires erasure “without undue delay” (Art. 17 GDPR). Snowflake Time Travel retains historical versions for 1 day by default, up to 90 days on Enterprise Edition, then hands them to a non-configurable 7-day Fail-safe window that only Snowflake can recover from (Time Travel, Fail-safe). Delta Lake’s VACUUM default retention threshold is 7 days (Delta Lake utilities). Seven days, not configurable, recoverable only by the vendor. Read that line while thinking about an erasure guarantee and the interesting question stops being DELETE and becomes what exactly you are promising the regulator.

Privacy subject: declare the roots, infer the rest

The platform cannot infer identity semantics from nothing. The customer declares the authoritative roots, and only those:

CREATE PRIVACY SUBJECT customer
IDENTIFIED BY (
    customers.customer_id
);

ALTER PRIVACY SUBJECT customer
ADD IDENTIFIER users.email
RESOLVED VIA identity_mapping;

Everything downstream is derived. The customer should never tag every table by hand — that is the failure mode of every classification-driven governance program, and it is the reason Meta built propagation instead of an annotation campaign.

A PII tag and a subject key are different assertions. PII=true says this field is sensitive. A subject key says this field lets me address the data belonging to subject X. Classification output is a discovery hint. It is not correctness evidence, and a coverage number computed from tags alone is a guess with a percent sign on it.

Pseudonymisation does not end the obligation. GDPR Article 4(5) defines it as processing “in such a manner that the personal data can no longer be attributed to a specific data subject without the use of additional information,” and Recital 26 is direct about the consequence: pseudonymised data “which could be attributed to a natural person by the use of additional information should be considered to be information on an identifiable natural person” (Art. 4, Recital 26). A reproducible SHA256(customer_id) therefore stays in scope — and conveniently stays addressable, because the platform can recompute the hash and match on it. Recital 26 also draws the other boundary: data protection principles “should therefore not apply to anonymous information.” That sentence is what makes a NO_ACTION verdict legitimate, and it is the exact claim a reclassification approval has to assert.

Addressability and influence are different properties

For each transformation the graph should carry four properties.

Three worked cases separate them. SHA256(customer_id) stays fully addressable, because the function is deterministic and reproducible. SUBSTR(customer_id, 1, 2) becomes only set-addressable: many subjects collide in the same prefix, so a delete predicate over it removes other people’s rows. AVG(spend) GROUP BY state loses addressability entirely and retains influence — X is gone from the output, and X still moved the number.

Influence is not a theoretical category. The FTC’s January 2021 settlement with Everalbum required the company to “delete any facial recognition models or algorithms developed with Ever users’ photos or videos” (FTC). Not the photos. The models trained on them. Any design that treats a model or an aggregate as out of scope because the rows are no longer selectable is asserting something a regulator has already rejected once.

The mechanism for the influence case is a different discipline. SISA training shards the training set, trains per shard, and aggregates, so removing a point retrains one shard instead of the whole model — 4.63x speedup on Purchase, 2.45x on SVHN, 1.36x on ImageNet-scale classification (Bourtoule et al., Machine Unlearning, IEEE S&P 2021). Those speedups are the honest framing: unlearning is cheaper retraining, not deletion. A warehouse primitive should record the obligation and hand it off, not claim to satisfy it.

The erasure plan

The request compiles rather than executes:

EXPLAIN ERASURE PRIVACY SUBJECT customer WHERE customer_id = '123';
ERASE   PRIVACY SUBJECT customer WHERE customer_id = '123';

Traversal resolves every reachable node to exactly one action:

DELETE
REWRITE
RECOMPUTE
REKEY
EXPIRE
NO_ACTION_WITH_JUSTIFICATION
UNRESOLVED

UNRESOLVED carries the design. A transformation whose erasure semantics cannot be proven — an arbitrary UDF, an external pipeline, a path-referenced sink — must surface as unresolved and must block a completeness claim. Meta’s fallback to siloing for opaque operators is the same instinct: when the analysis does not apply, say so and contain the blast radius rather than assume the flow was clean.

The REKEY action is worth calling out separately, because it is the one path that does not need graph traversal to be complete. Encrypt each subject’s data under a per-subject key and destroy the key, and every downstream copy becomes unreadable at once, including copies in snapshots you cannot address. It buys completeness and gives up queryability and the ability to prove which copies existed. That trade is a real design fork, not a footnote.

Coverage is bounded by the lineage graph underneath

This is the part that decides whether any of the above works, and it is measurable today from vendor documentation.

Unity Catalog captures column-level lineage automatically, including for views, ML model versions, and SQL, Python, and Scala UDFs. Its documented limits are the interesting content (Databricks):

• Lineage system tables retain a rolling one-year window.
• No lineage data captured before September 1 2024 is available.
• Column lineage cannot be captured when the source or target is referenced as a path — an s3:// sink drops to table level.
• UDF usage obscures column-to-column mapping, leaving table-level lineage only.
• Renaming a catalog, schema, or table loses lineage history.
• Jobs submitted via runs submit or the spark submit task type, RDDs, and global temp views are not covered.

Snowflake’s ACCESS_HISTORY gives column lineage through objects_modified, with directSources and baseSources mapping source columns to target columns — “provided that objects in the lineage chain are not dropped,” and with externally managed Apache Iceberg tables supporting DQL and DDL but not DML (ACCESS_HISTORY).

Now put a subject next to those limits. Someone who signed up in 2023 has a data history that predates the lineage record entirely. A pipeline that passed through a Python UDF has no column mapping to follow. A table renamed during a migration severed its own past. This is why lineage has to be temporal rather than current-state, with valid_from, valid_until, observed_at, and evidence_source on every edge: table A → table B may have been true last month and false today, and an erasure request has to reason over the versions of the graph that overlap the subject’s lifetime.

It is also why coverage must be a reported number that can be low. A platform that returns 100% because it only counted what it could see has built a compliance risk with a progress bar on it.

Two proofs, one attestation

A recall is the closer analogy than a delete. A manufacturer does not just fix the cars in the lot; it traces which VINs received the defective part through the bill of materials, and then produces evidence that the recall reached them. Erasure needs both halves, and they are independent.

Scope proof answers why you believe you found everything: declared roots, compiler-derived lineage, observed runtime lineage, identity transformations, edge validity intervals, and the enumerated gaps. Execution proof answers whether the actions happened: predicates run, rows and objects affected, table versions, rewrite jobs, retention expiry, failures and retries, timestamps.

ErasureRequest #8472
Subject: customer/123

Coverage:  47 datasets discovered
           45 resolved automatically
            2 explicitly exempt
            0 unresolved

Execution: 31 deleted
            8 recomputed
            6 expired
            2 anonymized / no action

Logical erasure: COMPLETE
Physical purge:  PENDING RETENTION (Fail-safe, 7d, vendor-controlled)

That attestation is the clean case. A single UNRESOLVED node has to change the verdict to INCOMPLETE and name the dataset, because a request that lands on a gap must not report success. The physical purge line is the other one most designs omit, and a Time Travel window plus a VACUUM default force you to write it down.

MVP, and what to leave out

Keep V1 to SQL-derived warehouse and lakehouse data: projection, rename, filter, join, union, deterministic functions, tokenization and hashing, group-by aggregation, materialized tables and views. Require explicit annotation for arbitrary UDFs and external pipelines — the same boundary Meta drew for opaque operators. Ship five commands: CREATE PRIVACY SUBJECT, SHOW PRIVACY COVERAGE, EXPLAIN ERASURE, ERASE PRIVACY SUBJECT, SHOW ERASURE ATTESTATION.

The preflight is the product:

> EXPLAIN ERASURE PRIVACY SUBJECT customer;

Coverage: 96.8%
  Automatically resolvable: 412 datasets
  Needs annotation:          11
  Unknown lineage:            3

That answers a question a company currently cannot answer before a request arrives: can we honor right-to-erasure correctly at all.

Three things belong out of scope, stated rather than quietly dropped:

1. Anything past the platform boundary. GDPR Article 17(2) obliges a controller who made data public to take “reasonable steps, including technical measures” to inform other controllers. A warehouse can produce the manifest of downstream exports; it cannot execute in someone else’s system.
2. Model unlearning. Record the influence obligation, name the affected artifacts, hand it to the ML platform. Do not claim it.
3. Streaming and unmanaged files. Databricks’ own guidance already says the obligation covers Kafka, files, and external databases. Any coverage number that silently excludes them is wrong in the direction that matters.

Provenance answers where data came from. Obligation-carrying lineage answers what followed it there, and Meta has run that in production for purpose limitation since at least 2024. Erasure is the same graph with a harder question attached, and a number at the end that a company has to be willing to see.