acceptodds
Under review as a conference paper at ICLR 2027

OWNERSHIP IS THE MISSING DECLARATION: DECIDING RELATIONAL TARGET LEAKAGE FROM THE SCHEMA

Abstract

Target leakage is treated as a statistical property of data: a column is leaky if a probe trained on it predicts the target too well, so no column can be judged before it is read. We ask instead which features the declared schema forces to determine the target on every database it admits, and what any schema-only method must leave undecided, where a task is a tree of many-to-one lookups over keys, foreign keys and copies. On a fragment allowing composite, cyclic and self-referencing foreign keys, a whole-key closure decides this soundly and completely, in time near-linear in the copy-closed view, and every negative verdict carries a counterexample database. One further SQL-declarable construct makes the question undecidable for feature sets, and targets aggregated over future rows, such as churn, are outside the fragment. Four such mechanisms cost models up to 22.4 accuracy points and 54.5 macro-F1, and the closure abstains on every one. Across 5,094 WikiDBs databases, 119 CTU databases and 23 benchmark tasks, keys and foreign keys alone certify no non-identifier leak at all; across 22,989 public schemas they certify 124 of 1,137,685 targets, every one a key cycle. Two open-source ERPs do declare which table owns a value, yet neither dump carries it, and one never emits a database-level foreign key at all. Blind language-model declarers recover 0 of the 90 columns designers removed by hand: the method certifies what a declaration forces, not leaks found unaided. Checking a declaration on a sample is cheap and carries a bound. On one RelBench task a name-blind generator proposes the declaration and ten sampled rows accept it; the closure certifies the removal, and re-inserting the column raises accuracy by 28.0 points. Given an ownership declaration, the rest of the fragment is decided before a row is read.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
target leakage, relational databases, database schemas, functional dependencies, data-centric machine learning, relational deep learning, benchmark curation, decidability, certificates

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_KoHrOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies which features must determine a target based on database schemas and constraints alone, without reading data. It gives a closure algorithm using complete keys (whole-key closure) for a specified class of schemas, together with finite counterexamples when a dependency does not follow from the constraints. It also examines undecidability, verification of copying rules from samples, and whether information about field sources and copying relationships is available in public databases and application code.

Critical strengths
  1. The core decision problem receives a clear answer. Under the stated schema and view conditions, Theorem 1 shows that the closure algorithm derives no invalid dependencies and misses none implied by the constraints. This separates correlations in data from determination guaranteed by database constraints and provides a precise criterion for checking dependencies without reading data.

  2. Both implication and non-implication decisions can be checked. The algorithm gives derivations for dependencies that follow from the constraints and finite counterexamples for those that do not. Appendix D also reports randomized and exhaustive checks. Users can therefore examine the reasons for a verdict rather than receiving an unexplained label.

  3. Examining application code and database exports shows where information is lost. The ERP investigation checks field relationships recorded in applications separately from exported databases. It identifies cases where field-source and copying information exists in application code but is unavailable to downstream users. This has practical implications for database publication and relational benchmark design.

  4. The experiments include controls and report unsuccessful results. The RelBench experiments that reinsert removed fields retain temporal splits and permutation controls and compare gradient-boosted trees with graph neural networks (GNNs). The automatically generated declarations did not enable the detector to recover the manually removed columns, and some controls show no expected benefit. These results distinguish proving the consequences of supplied constraints from finding useful constraints automatically.

Critical weaknesses
  1. The proof of Theorem 2 needs correction. In Appendix A, p.17, deleting a foreign key from the new table back to the original table relies on an assumption about Fan–Libkin's reduction that is taken “on trust.” The original encoding of an ordinary functional dependency also includes that foreign key, contrary to the stated assumption. The modified construction may still support a correct reduction, so this does not refute the theorem. The authors need to explain how database instances are converted in both directions and replace the current justification.

  2. Exact implication and approximate statistical guarantees are not clearly distinguished. Definition 3 concerns exact implication in every database satisfying the constraints, whereas Table 2 labels a default copying relationship with observed violations as LEAK/C certified. Table 15 provides an upper bound on the violation rate in the sampled population. The abstract also emphasizes ten-row acceptance even though Appendix M states that this small-sample result should not be the headline. The authors need to state what each verdict guarantees and make the abstract consistent with those definitions.

  3. The guarantee for records with successful lookups does not adjust the denominator accordingly. Appendices M and N calculate the fraction of all records in the root table for which a foreign-key lookup succeeds but the copy equality fails. The subsequent 1−mε guarantee applies to records where all required lookups succeed. If these records represent a fraction q of the population, the bound needs adjustment, for example to 1−mε/q, or sampling directly from those records. Strict Φ₀ has q=1, so Theorem 1 is unaffected; the concern applies only to the extension where some records lack successful lookups.

  4. Repetition and weak transitions make the paper difficult to follow. The abstract densely lists findings, and the main text repeats several summaries. Some passages read as AI-assisted prose that needs more careful editing. Transitions between parts are unclear, making the main argument harder to follow. I recommend reducing repetition and explaining how the theoretical analysis, sampled verification, and experimental results relate to one another.

Questions for authors
  1. Does a LEAK based on sampled verification mean exact implication assuming the copying constraints, an approximate relation in the sampled population, or a dependency that holds after deleting a bounded fraction of records? How does the output distinguish these guarantees?

  2. Is ε measured over all records in the root table or only those with successful lookups? What is the correct conditional guarantee when records for which all required lookups succeed represent a fraction q?

  3. Can you give a complete reduction without the stated back-FK assumption? Please explain whether the constructed schemas meet the required conditions and how finite and unrestricted database instances are converted in both directions.

  4. For the 53 candidate constraints proposed without using field names, does Table 15's confidence bound concern a constraint selected before sampling or one selected after verification? Was a multiple-testing correction applied?

1 comment
AuthorsOpenReview ↗

Response to Reviewer KoHr

We are grateful for the technical depth of this review. Your two proof-level points were correct and have made the paper stronger.

W1 / Q3 (Theorem 2 proof; back-FK "taken on trust"; give a complete reduction). You are right; we replaced the justification entirely. The proof no longer leans on Fan–Libkin's encoding — we reduce directly from implication of an FD by FDs and inclusion dependencies, "so correctness rests on the two translations below rather than on any cited construction" (Appendix A). Forward: from finite I ⊨ Σ with I ⊭ θ, set R_new := π_XY(I(R)); since I ⊨ R:X→Y, X keys that projection, so the PK, UNIQUE(XY) and FK all hold. Backward: from admissible I′, two R-rows agreeing on X reference the same R_new-row (via the FK into pk(R_new)=X) and so agree on Y. On your exact point about the dropped back-FK: the FD gadgets carry none — "an R_new-row with no R-witness is inert precisely because R_new is referenced by nothing else, which is what the dropped back-FK formerly enforced" — while the goal gadget deliberately retains its back-FK so "determination can flow out." Both maps preserve finiteness, and the construction uses exactly one construct outside Φ₀ (Corollary 2).

W2 / Q1 (exact vs. sampled guarantee not distinguished). Agreed; we now state what each verdict guarantees and keep the tiers separate. A declared-key/FK LEAK is exact on every admissible database (Definition 3); a sample-certified LEAK is not: on rel-salt item-incoterms, "an overridable default whose certificate is a sampled defect bound rather than an exact equality… under Theorem 3's Clopper–Pearson variant, it is certified up to a sampled defect, not on every admissible database as a declared-key/FK LEAK is" (§5.1).

W3 / Q2 (1−mε uses the wrong denominator; condition on covered rows, fraction q). You are correct. The guarantee is now conditional on covered rows: "violation rate among covered rows… the covered-row guarantee would read ≥ 1 − mε/c. Strict Φ₀ has c=1" (Appendix B) — our c is your q. For c < 1 the bound degrades to 1 − mε/c; in strict Φ₀ every root row is covered, so Theorem 1 is unaffected, exactly as you note.

W2 abstract (ten-row acceptance over-emphasized). Removed. The abstract no longer mentions ten-row acceptance; it states the guarantee at the level the definitions support: "proposing candidates from a bare schema and certifying each on a sample to a stated defect bound recovers 6 of 7 determining removals… the method certifies what a declaration forces, not leaks found unaided." It is now consistent with Definition 3 and Appendix M.

Q4 (53 candidates: bound selected before or after sampling; multiple-testing correction?). Before sampling, Bonferroni over the family: "All K=53 are fixed from the schema before any row is sampled… the zero-violation rule's n ≥ ⌈ln(K/δ)/ε⌉ and the Clopper–Pearson variant's α = δ/K (Bonferroni over the 53)… so item-incoterms's bound is valid as a member of the proposed-before-sampling set, not a hindsight pick" (Appendix B).

W4 (repetition, transitions). We trimmed repeated summaries and added connective transitions (the §5 opener now partitions the experiments explicitly). If specific paragraphs still read as over-compressed, we would gladly tighten the ones you point to.

We thank you again for the corrections that sharpened the proofs.

Reviewer_vBL3OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper tackles the problem of target leakage in data. In relational ML benchmarks, the training table is built by joining tables along foreign keys. However, a joined-in column can secretly contain the target. Currently, such a leakage is detected by running a probe model on each column and checking if a column predicts the target perfectly. The authors investigate if such a leakage could be detected from the schema alone. They find that if the schema includes ownership declarations, such leakages could be detected from the schema alone, but without such declarations, not. A method is proposed that detects leaks given a schema and ownership declarations. However, real-world database schemas don't contain such declarations, where the proposed method fails.

Critical strengths

The finding that ownership declarations can enable detection of leakage from schema is interesting. The diagnosis is backed by evidence.

The proposed method is proven sound and complete. The authors further show where the problem becomes undecidable and which cases become out of scope.

The leaks that the paper studies are real and costly.

Critical weaknesses

It is a bit unclear what the main goal of the paper is. Is it just a theoretical characterization and not detection? As pointed out in the paper, for the detector to work, the schemas need to include ownership declarations, which are usually absent in real-world databases. As a detector, the proposed method (Algorithm 1) finds none of the seven hand-removed RelBench columns that actually determine the target.

I would imagine that for most of the cases, if the declarations are available, detecting a feature is trivial. Things might become complicated when there are chains and combinations. However, the authors observe that such complicated cases are rare in reality. It also makes me think if ICLR is an appropriate venue for this work. While the topic does relate to relational deep learning, the technical core is database theory and does not involve any learning. The detection part, which would be useful to the community seems weak.

The paper in general is difficult to read, which limits my ability to assess its contributions. For example, the Introduction section mentions notations ϕ(0)\phi(0), (S1)-(S3) before they have been defined. The main text relies quite a bit on appendices spanning 26 sections and 48 pages. It includes a large number of copy-source variants: C0, C1, C2, C3d, C1f ... making it very difficult to read. I would suggest the authors clearly state the problem, the main goal, and the main result plainly in the introduction.

Questions for authors

Please elaborate on what is the paper's primary goal.

Could you state precisely what Theorem 1 establishes that does not follow from the previous results?

What do you mean by "taken on trust and not reproved here" in the proof for theorem 2?

1 comment
AuthorsOpenReview ↗

Response to Reviewer vBL3

Thank you for stating the central tension so crisply and for confirming the leaks we study are real and costly.

W1 (main goal; "Algorithm 1 finds none of the seven hand-removed columns"). The primary goal is the characterization: "This paper is that characterization, not a leak finder" (§1). Your observation is exactly right as RelBench ships — and it is the finding, not a failure: the released schema carries no ownership declaration, so a sound method must abstain. The revision completes the arc: "with proposed-and-certified declarations it recovers 6 of 7 on five seeds" (§5.3). So: 0 from the bare public schema (correct abstention), 6 of 7 once the missing declaration is recovered and certified.

W2 (venue fit; "does not involve learning; detection weak"). We foregrounded the learning stakes: "What is at stake is a learning problem, not just data hygiene: across the 135 in-domain targets of the relational foundation models ranked on these corpora, the closure certifies none, because the released schemas cannot express ownership" (§1), and "where the leak does travel through an aggregate a heterogeneous GNN computes, its message passing inflates accuracy by +32.1 points, more than a gradient-boosted tree's" (§1). RDL and relational foundation models consume exactly the FK-reachable columns the closure screens, so a schema-only gate is the one vet that applies before any row is read. On "detection weak": the detector is intentionally the minimal object computing the theorem's relation; its strength is the certificate, and once declarations are recovered, detection reaches 6 of 7 (RelBench) and 705/10,612 (THE JOIN).

W3 (readability). Addressed (general response §2): notation glossed at first use, C-variant legend consolidated, algorithm in the main text. The appendix stays large by design (ICLR permits unlimited supplement), but the main text is self-contained for the three headline results.

Q1 (primary goal). A decision procedure and its exact boundary: which features the declared schema forces to determine the target on every admissible database, and what any schema-only method must leave undecided.

Q2 (what Theorem 1 adds). The main text now says it directly (§3): prior work gives FD propagation to SPJ views and finite controllability for key/FK goals; new is that copies and (cyclic/self-referencing) FKs do not interact with keys under (S1)–(S3), and finite = unrestricted implication for view goals.

Q3 ("taken on trust" in the Theorem 2 proof). Removed; the undecidability proof is now self-contained (see our reply to KoHr W1/Q3). It no longer depends on any uncited property of a prior construction.

Reviewer_oF9eOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

The paper investigates whether relational schema constraints can be used to detect potential target leakage in machine learning without examining the underlying data. Its central argument is that, when a schema explicitly records value ownership and relationships between original and copied values, it is sometimes possible to establish that a feature functionally determines the prediction target.

The proposed approach computes a functional dependency closure over a relational feature view using keys, foreign keys, and ownership/copy declarations. It produces four possible verdicts: (1) IDENTIFIER, when a feature determines the entity's primary key; (2) LEAK, when a non-identifier feature determines the target; (3) JOINT, when a set of features collectively determines the target; and (4) ABSTAIN, when the schema does not guarantee such a determination. The paper establishes theoretical guarantees for the approach and evaluates it on several relational datasets and benchmarks.

Critical strengths
  1. Comprehensive theoretical analysis. The paper provides an extensive formal treatment of the problem, including soundness, completeness, and decidability results under specified schema constraints. It also characterizes the limits of what can be inferred from schema declarations alone.

  2. Potentially novel connection. The characterization of how ownership/copy declarations interact with keys and foreign keys, and its application to detecting target leakage, appears to be a novel contribution.

  3. Schema-based guarantees. Unlike data-driven approaches, the proposed method can certify functional determination without accessing database records. This is an attractive property when data access is costly, restricted, or unavailable.

Critical weaknesses
  1. Unclear central message and contributions. The underlying idea is relatively straightforward: use schema constraints, including declared copies, to determine whether a feature functionally determines the prediction target. However, this message is obscured by the extensive formal development. It is difficult to identify the precise research gap, what is fundamentally new beyond existing dependency theory, and the practical implications of the results.

  2. Difficult presentation and organization. The abstract and introduction do not provide an accessible explanation of the problem and contributions. For example, the "Results in brief" paragraph in the introduction uses notation such as (\Phi_0) and conditions (S1)–(S3), which are only defined in Section 2. The main body contains numerous definitions, theorems, and corollaries without sufficient intuition or explanation of their significance. Meanwhile, the detection algorithm is deferred to Appendix K, although its underlying closure is described in Section 3. Presenting a clear algorithm and a complete worked example earlier would make the paper substantially easier to follow. The theoretical results could then be introduced progressively, with explanations of what each establishes and why it matters and parts interfering with the flow moved to the appendix.

  3. Unclear objectives and conclusions of the experimental evaluation. The experimental evaluation addresses several different objectives, including validating theoretical properties, examining the availability of schema metadata, comparing against dependency-based leakage detectors, and measuring the impact of leakage on downstream ML models. However, the main research questions and takeaways are not clearly articulated, making it difficult to assess how the experiments collectively support the paper's claims. For example, the proposed detector identifies almost no leakage using the metadata available in public benchmarks, while additional declarations are required to detect some known cases. Although these results highlight the importance of ownership declarations, they provide limited evidence of the detector's effectiveness under the metadata conditions commonly encountered in practice.

  4. Limited practical applicability without ownership declarations. The approach relies on ownership/copy declarations that are generally absent from existing relational schemas and benchmark datasets. The experiments confirm this limitation, and the attempts to infer such declarations automatically have limited success. Although the authors identify ERP systems where ownership information is available at the application level, it remains unclear how this information could be reliably extracted or reconstructed for arbitrary databases. The practical value of the proposed detector depends heavily on the availability and accuracy of these declarations. The paper does not sufficiently establish that this information can be acquired at scale or that the resulting detector would identify a meaningful proportion of actual leakage cases.

  5. Unclear practical advantages over dependency discovery methods. The proposed approach is closely related to functional dependency implication and approximate functional dependency (AFD) discovery. While schema-based reasoning offers stronger guarantees without accessing the data, existing data-driven methods can discover dependencies even when they are not explicitly declared. The paper includes comparisons with methods such as TANE and HyFD, some of which detect more leakage cases, although with different precision and computational costs. A clearer analysis of these trade-offs is needed to establish when the proposed approach is preferable to conventional dependency discovery methods. In particular, when ownership declarations are unavailable, it is unclear how much practical benefit the proposed detector offers.

Questions for authors
  1. What are the main research questions driving the experimental evaluation? Can the authors clarify which experiments validate the theoretical contributions and which demonstrate the practical effectiveness of the detector?

  2. How do the authors envision obtaining reliable ownership declarations for existing databases where this information is not explicitly recorded? Given the limited success of automatic declaration generation, how practical is the proposed approach for real-world datasets?

  3. Can the authors characterize the settings in which their approach has an advantage over approximate FD discovery methods, in particular, when ownership declarations are unavailable?

  4. The paper acknowledges that functional determination does not necessarily imply illegitimate target leakage if the feature is legitimately available at prediction time. How do the authors envision incorporating this distinction into a practical leakage detection system?

1 comment
AuthorsOpenReview ↗

Response to Reviewer oF9e

We thank you for working through the formal development in detail and for the precise presentation feedback.

W1 / Q1 (central message; theory vs. practice experiments). We have restructured around a single thesis (general response §1); §5 now opens by partitioning the experiments: "Four questions organize what follows. Three measure practice: does the missing declaration cost accuracy (§5.1), what do public exports declare (§5.2), and can ownership be acquired at scale (§5.3)? The fourth validates the theory: does the detector compute exactly the theorem's relation?" So §5.1–§5.3 measure practice; the detector-vs-theorem paragraph (13/13 declared copies at precision 1.00) validates the theory.

W2 (presentation). All addressed (general response §2): Φ₀ glossed at first use, (S1)–(S3) removed from the intro box, Algorithm 1 displayed in §4 with a Chinook worked example, each theorem/corollary carrying an "Informally, …" gloss. The detection algorithm is no longer in the appendix.

W3 / Q2 (practical applicability; declarations at scale). The heart of the revision (general response §3): we separate motivation, recovery, and composition. The recovery result is now in the paper: 0 → 6 of 7 on RelBench, 705/10,612 on THE JOIN (§5.3).

W4 / Q3 (advantage over TANE/HyFD). Warrant versus recall (general response §4). The closure certifies on every admissible database reading zero rows; discovery reports what holds in the sample it reads. The two are complementary — closure first, discovery on the remainder. Where ownership is undeclared and unrecoverable we claim only the forced-abstention certificate, and say so plainly.

Q4 (prediction-time availability). Treated as an explicit limitation: "A certified determination is a leak only if the feature is unavailable at prediction time (a deployment check we leave open)" (§7). Whether a certified feature is legitimately available needs time stamps or domain knowledge, which we place out of scope.

The novel core is the ownership/copy declaration as a schema primitive and the decidability boundary it opens (Theorem 1 decidable for view goals, Theorem 2 undecidable without it) — a boundary existing dependency theory does not draw. We hope the restructured presentation makes that contribution legible.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response to All Reviewers

General Response to All Reviewers

We thank all three reviewers for their careful and constructive reading. We are especially grateful for the depth of engagement: oF9e and KoHr each worked through the formal development in detail, KoHr identified two genuine technical points in the proofs that have made the paper stronger, and vBL3 crisply articulated the central tension our work addresses. The reviews converge on a small number of themes, which we address here once and reference from our individual replies.

We read the reviews as agreeing on a clear diagnosis: the contribution is sound and the problem is real and costly, but the central message is obscured by the formal development, and the practical pathway to acquiring ownership declarations was not established convincingly enough. We have reworked the paper accordingly.

  1. The central message and contribution. oF9e (W1), vBL3 (W1) and KoHr (W4) all note the main contribution is hard to extract. The main text is now built around a single thesis, stated in §1: "On multi-table data, we show, one schema-level declaration settles the question before a row is read," framed explicitly as "This paper is that characterization, not a leak finder: §5 tests it with one detector whose only job is to compute the theorem's relation and certify it, never to find leaks unaided." The §1 "Results in brief" box now carries three results: (i) Decide — on Φ₀ a whole-key closure decides declared determination soundly and completely, with finite and unrestricted implication coinciding (Theorem 1); (ii) a sharp boundary — one construct more makes it undecidable (Theorem 2), a secondary key restores decidability (Theorem 5), the copy declaration being a new ownership primitive opening a decidable island; (iii) forced abstention — every negative verdict carries a machine-verifiable counterexample, so abstention is forced for every sound schema-only method (Corollary 1). A consequence worth stating directly: the low detection numbers on public benchmarks are the finding, not a failure — public schemas carry no ownership declaration, so a sound method must abstain.

  2. Presentation. Φ₀ is now glossed inline at first use and (S1)–(S3) removed from the intro box; the detector is a displayed algorithm (Algorithm 1) in §4 with a complete Chinook worked example immediately after it; the copy-source variants (C0–C2, C1f, C1n, C3/C3d) are introduced once as a legend before any table uses them; each theorem/corollary opens with a one-line "Informally, …" gloss and repeated summaries have been trimmed.

  3. Acquiring ownership declarations at scale. We separate three things we had conflated. Motivation: two audited ERPs ship machine-readable ownership (ERPNext's fetch_from, 555 copies over 838 tables; Odoo's stored related, 169 over 655), yet the bare exports certify nothing. Recovery: we add an automated step that proposes declarations from a bare export and certifies each on a sample to a defect bound (Theorem 3, ε=0.01, δ=0.05), target-blind (the joins that seed the proposals are the foreign keys the released manifests declare; where an export lacks them we examined a schema-recovery tool, NVIDIA Auto Ontology, without running it against a model, and three no-model checks show the joins are replaceable scaffolding). As RelBench ships, the detector certifies none of its 7 determining removals; with proposed-and-certified declarations it recovers 6 of 7 on five seeds. On THE JOIN it returns LEAK on 705 of 10,612 official tasks in 169 of 639 databases; a held-out census marks 692 determined, 639 (92%) with a leak. Composition: recovered declarations feed the unchanged zero-row detector, certified up to a defect bound at stated confidence, never as exact implication; re-tested out of sample, 0 of 1,106 value maps exceed their 1% bound.

  4. Warrant, not recall. The value of a schema-only method is warrant: "it reads 0 rows and returns a certificate, where the baselines read 93.2M rows and return none, and 15,891 of 22,989 schemas ship no rows for them to read at all." The method is additive — closure first to exclude what the schema forces, discovery on the remainder.

We are grateful to the reviewers; the revision is materially clearer and more honestly scoped as a direct result of their comments. Per-reviewer responses follow.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.