Identifiability of Relational Queries in Multi-View Pretraining
For practitioners integrating data sources via shared interfaces, this work identifies a structural ambiguity that cannot be resolved by more data or larger models, providing both a diagnostic tool and a lower bound on achievable accuracy.
The paper formalizes query identifiability in multi-view pretraining under interface laws, showing that non-identifiable queries have an irreducible 1/2 minimax error floor. It provides a polynomial-time certificate (CheckCert) for identifiability and a minimum-augmentation algorithm (Greedy-MinAug) to certify queries, with experiments confirming the predicted error floor and millisecond runtimes.
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.