{"ID":5937279,"CreatedAt":"2026-07-07T03:14:33.014478982Z","UpdatedAt":"2026-07-09T07:04:12.978444665Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.04735","arxiv_id":"2607.04735","title":"Identifiability of Relational Queries in Multi-View Pretraining","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.","short_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 dat...","url_abs":"https://arxiv.org/abs/2607.04735","url_pdf":"https://arxiv.org/pdf/2607.04735v1","authors":"[\"Ratan Bahadur Thapa\",\"Daniel Hernández\"]","published":"2026-07-06T07:18:00Z","proceeding":"cs.DB","tasks":"[\"cs.DB\",\"cs.LG\"]","methods":"[]","has_code":false}