- 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
-
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.
-
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.
-
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.
-
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
-
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.
-
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.
-
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.
-
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
-
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?
-
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?
-
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.
-
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?
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.