Identifiability of Relational Queries in Multi-View Pretraining
2026-07-06 • Databases
DatabasesMachine Learning
AI summaryⓘ
The authors study how information combined from different sources can sometimes be ambiguous when answering questions, because the shared rules (or interface) connecting the sources don't always fully determine the answer. They define a way to check if a question's answer is uniquely identifiable under these rules and provide an efficient method to do so. They also show that if a question isn't identifiable, no method relying only on the shared rules can do better than a 50% error rate. Finally, they offer a way to minimally improve the interface to make ambiguous questions identifiable. Their experiments confirm these methods work quickly and match their theoretical predictions.
data integrationquery identifiabilityfunctional dependenciesinterface lawsattribute closureminimax errorSet Cover problempolynomial-time algorithmsmulti-view learningpretraining
Authors
Ratan Bahadur Thapa, Daniel Hernández
Abstract
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.