# Identifiability of Relational Queries in Multi-View Pretraining

arXiv: https://arxiv.org/abs/2607.04735 · HTML: https://mlsanity.com/paper/2607.04735/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 3 of its 37 references that are in the map.
- First posted on arXiv 6 Jul 2026.

## Builds on (most cited first, 3 of 3)

- [An Augmentation Overlap Theory of Contrastive Learning](https://mlsanity.com/paper/2511.03114/) (2025)
- [The Hunt for a Red Spider: Conjunctive Query Determinacy Is Undecidable](https://mlsanity.com/paper/1501.01817/) (2015)
- [Red Spider Meets a Rainworm: Conjunctive Query Finite Determinacy Is Undecidable](https://mlsanity.com/paper/1512.01681/) (2015)

## Abstract (arXiv)

When data sources are integrated through a shared interface, a downstream query may or may not be determined by what the interface exposes: two globally consistent worlds can agree on every shared attribute yet disagree on the query answer. This ambiguity is structural -- a property of the interface design, not the data volume -- and cannot be resolved by collecting more records or training a larger model. We formalize query identifiability for data integration under interface laws (functional dependencies that hold uniformly across all legal worlds rather than within a single instance) and prove three results. (i) A polynomial-time certificate (CheckCert) decides identifiability via attribute closure, and is exact on instances that expose any residual ambiguity (closure-separable). (ii) Non-identifiable queries face an irreducible 1/2 minimax error floor for any estimator using only interface evidence, bounding multi-view pretraining systems from below. (iii) A minimum-augmentation algorithm (Greedy-MinAug) finds the smallest set of interface additions to certify a query, reducing to Set Cover (logarithmic approximation). Experiments on synthetic benchmarks, real integration datasets spanning three domains (scholarly, product, restaurant), and schemas up to 10^3 attributes confirm CheckCert is exact, both algorithms run in single-digit milliseconds, and ML classifiers exhibit the predicted error floor and abrupt capability gains.