arXiv CSopen access

Identifiability of Relational Queries in Multi-View Pretraining

Identifiability of Relational Queries in Multi-View Pretraining

arXiv:2607.04735v1 [cs.DB] 6 Jul 2026

RATAN BAHADUR THAPA , University of Stuttgart, Germany DANIEL HERNÁNDEZ , University of Stuttgart, Germany 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 actually expose any residual ambiguity (which we formally call 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 the problem to Set Cover (logarithmic approximation). Experiments on synthetic benchmarks, real integration datasets spanning three domains (scholarly, product, and restaurant), and schemas up to 103 attributes confirm CheckCert is exact, both algorithms run in single-digit milliseconds, and ML classifiers exhibit the predicted error floor and abrupt capability gains that augmentation produces. CCS Concepts: • Theory of computation → Database theory; • Information systems → Data integration; • Computing methodologies → Learning latent representations. Additional Key Words and Phrases: Query identifiability, Data integration, Interface laws, Conjunctive queries, Multi-view learning

1

INTRODUCTION

Enterprise analytics increasingly draws from data lakes and federated ecosystems where analysts query across hundreds to thousands of sources with incompatible schemas [29, 34]; at open-data scale, catalogues index tens of millions of datasets from independent producers [7]. In each case an integration layer specifies which attributes are shared across sources and which deterministic correspondences between them hold, but leaves the rest unconstrained. A growing class of representation-learning methods, multi-view and contrastive pretraining, learns directly from these shared attributes, aligning records across sources by the attributes they share [26, 37]. This raises a foundational question prior to any particular model or training procedure: given only what the integration interface exposes, which queries are determined—guaranteed the same answer across every dataset consistent with the interface—and which are irreducibly ambiguous, no matter how much data is gathered or how large the model? We call this property query identifiability, and it is the subject of this paper. Where does this ambiguity arise? Consider a billing system and a support system integrated through a shared interface. A data engineer needs to answer a query: does this customer have both an overdue invoice and a high-severity support ticket? The billing system identifies customers by email address (email); the support system uses an internal customer code (cid). Their shared interface aligns records on email—the one attribute they have in common—but says nothing about which cid corresponds to which email. Without that correspondence the interface offers no unique way Authors’ addresses: Ratan Bahadur Thapa , Analytic Computing, KI, University of Stuttgart, Stuttgart, Germany, ratan. [email protected]; Daniel Hernández , Analytic Computing, KI, University of Stuttgart, Stuttgart, Germany, [email protected].

2

Ratan Bahadur Thapa and Daniel Hernández

to match invoices with tickets: there are multiple ways to complete the data consistently with everything the interface exposes, and they can assign cid values differently, linking tickets to invoices differently and returning different query answers. This ambiguity is structural: it cannot be resolved by collecting more data, because the interface simply does not carry the email-to-cid mapping. Add a resolver that fixes that mapping as a deterministic law, however, and the answer changes entirely—the resolver propagates the email evidence to cid, the join key becomes available, and the query is determined by the interface alone. To reason about this systematically, we model every way of completing the observed data as a legal world—a globally consistent dataset that respects the interface’s deterministic components. A query is identifiable when all legal worlds return the same answer [2, 14]. The deterministic components— resolvers, canonicalizers, identifier crosswalks—are modeled as interface laws: constraints that fix one attribute from another uniformly across all legal worlds [4, 5]. These laws propagate overlap evidence to further attributes: in our billing example, the email → cid resolver law reaches cid from the email overlap, making the join key available and the query identifiable. This structure yields three results. First, whether the laws propagate far enough to cover all attributes a query needs is decidable in polynomial time (CheckCert, Theorem 4.5); on instances that actually expose the ambiguity, a failed check is itself a proof of non-identifiability (Corollary 4.18). Second, for every non-identifiable query there is always a concrete pair of legal worlds on which any method using only interface evidence must err with probability at least 1/2, regardless of how much data it sees (Theorem 4.7)—the information is structurally absent. Third, adding an interface component—a new resolver, a crosswalk, a shared identifier—can flip a non-identifiable query to identifiable, producing an abrupt capability gain (Theorem 4.10); Greedy-MinAug finds the smallest such addition, reducing the problem to Set Cover with a logarithmic approximation (Theorem 5.2). Because multi-view pretraining minimises a loss anchored to the shared attributes, driving that loss below a threshold forces the unique answer on certified queries—structurally determined, independently of sample size (Theorem 4.14). Contributions. We turn these results into two practical schema-design algorithms. CheckCert checks in polynomial time whether interface propagation covers all attributes a query needs— certifying identifiability on instances that expose the ambiguity (Corollary 4.18)—and pinpoints unreachable attributes when the check fails. Greedy-MinAug finds the smallest set of new interface components that certifies the query, reducing the problem to Set Cover with a logarithmic approximation (Theorem 5.2). We evaluate both algorithms on a 5-attribute synthetic benchmark with exhaustive ground truth, on real integration datasets spanning three domains (scholarly: BibInteg and CrossKG-DBLP; product: Amazon-Google; restaurant: Fodors-Zagat) with the WDC schema as a design case study, and at database scale (up to a thousand attributes and functional dependencies). The certificate is exact and both algorithms run in single-digit milliseconds. ML classifiers trained on the same schemas confirm the 1/2 error floor and the abrupt capability gains that augmentation produces. The paper is organized as follows: Section 2 discusses related work; Section 3–5 develop the theory and algorithms; Section 6 presents the evaluation. Key theoretical results are machine-verified in Lean 4: the closure certificate (Theorem 4.5), minimax lower bound (Theorem 4.7), and the reduction of identifiability to query determinacy are fully machine-checked; the capability-jump theorem and MinAug hardness remain open in the formalization. 2

RELATED WORK

Possible-worlds semantics and certain answers provide the closest semantic template [2, 14, 27]. Evidence restricts a set of admissible worlds, and a query is certain when its answer is invariant across those worlds. We adapt the idea to heterogeneous data integration by replacing a single

Identifiability of Relational Queries in Multi-View Pretraining

3

Table 1. Identifiability vs. related query-answering frameworks (Boolean CQs). † Complete on closureseparable instances (Corollary 4.18).

Framework

CQ complexity

Certificate

Query determi- Undecidable (gen- Sufficient only nacy [30] eral) Certain an- coNP-complete Complete swers [2, 27] Data ex- PTIME (chase) Sound (target-side) change [13] CheckCert (Our PTIME (closure) Complete† work)

incomplete database with observed views, designated overlaps, and deterministic interface laws that hold across all legal worlds. Data integration studies query answering over heterogeneous sources with different schemas and identifiers [11, 19, 23]. View-based query answering and query determinacy ask when views suffice to answer or rewrite a query [1, 20, 24, 30, 31]. Nash, Segoufin, and Vianu [30] give a semantic characterisation of query determinacy, prove it undecidable for first-order views, and show decidability only in restricted CQ cases (monadic/Boolean and path queries); the general CQ case was later proved undecidable over both unrestricted [17] and finite [18] instances. Our identifiability is the sub-case where observation views are closure-augmented overlap projections— projection CQs with no joins—which falls within the decidable fragment; two further restrictions yield polynomial time (Theorem 4.5): the views are FD-closures of designated overlaps, and interface laws hold across legal worlds (Definition 3.2) rather than within a single instance, reducing the containment check to standard attribute closure with no quantifier alternation. Identifiability therefore does not subsume CQ views with joins; conversely, determinacy by CQ join views is undecidable [17, 18] and admits no closure certificate. The tractability gap in Table 1 has a precise source. Query determinacy asks whether an arbitrary set of views rewrites 𝑞 under arbitrary world semantics—no constraint links views to each other, so the problem reduces to checking containment for all possible view extensions, which is undecidable in general [30] and undecidable even for CQs [17, 18]. Certain answers are complete but coNPhard because every possible open-world completion must be considered. Interface laws break both barriers: once evidence is anchored to designated overlaps and laws are restricted to FDsyntax holding across worlds, propagation reduces to standard attribute closure—a linear fixed-point computation with no quantifier alternation. Identifiability is, at its core, a closure problem; this paper recognizes that structure, formalizes it under multi-world semantics, and derives its consequences for pretraining and schema design. Data exchange studies legal target instances and certain answers under schema mappings [13]. The chase procedure produces canonical instances that satisfy a set of tgds and egds; interface laws are a restricted form of egds that hold universally. Minimum interface augmentation (Definition 5.1) is analogous to strengthening a schema mapping to eliminate ambiguity in the target: adding interface actions corresponds to adding egd constraints that make the target unique for more queries. Entity resolution and record linkage provide practical mechanisms for constructing cross-source identity evidence [9, 12]. We abstract from a particular matching algorithm and ask which queries become determined once an interface exposes particular overlaps and deterministic components.

4

Ratan Bahadur Thapa and Daniel Hernández

Table 2. Running example. Billing and Support are the integrated sources; HR is the resolver, which supplies the interface law email → cid that links them. The resolver is optional—its presence is what makes the query identifiable.

email

invoice

overdue

a@x b@x

I-1 yes I-2 no Billing

cid

ticket

C1 C2

T-1 hi T-2 lo Support

HR resolver (optional)—interface law email → cid:

severity

a@x ↦→ C1, b@x ↦→ C2

Functional dependencies and attribute closure are classical tools for reasoning about determinacy of attributes [4, 5, 16]. We use the same implication machinery, but our dependencies represent deterministic interface laws shared across legal worlds rather than only constraints internal to one relation instance. Minimum interface augmentation is closest to view-set minimization and view-selection problems [25]. Conjunctive queries are the canonical language for joins and projections in database theory [2, 8]. We use their attribute footprint to connect query evaluation to closure-augmented overlap evidence. Jensen–Shannon divergence [28], information inequalities [10], and Fano-style lower bounds [15, 21, 36] provide the tools for our robustness and capacity results. Multi-view learning uses agreement between different observations as surrogate supervision [3, 6, 26]. Representation-learning pipelines implement the same principle through contrastive or alignment losses on paired views. The key distinction from this paper is semantic vs. statistical: multiview learning bounds concern generalisation—whether a model trained on 𝑁 samples can predict well—while our identifiability is a structural question independent of sample size. A query can be statistically learnable (with enough data, a model converges to the right answer) yet not identifiable in our sense (the information is simply not present in the interface evidence). Theorem 4.7 makes this precise: for non-identifiable queries, there exists a witness pair on which any interface-evidenceonly estimator achieves error ≥ 12 regardless of 𝑁 , whereas generalisation bounds decrease with 𝑁 . Identifiability is therefore a precondition that learning bounds implicitly assume; our contribution is to make this precondition explicit and algorithmically checkable. 3

DATA INTEGRATION INTERFACE

Let us introduce a running example to help formalize three key notions: interface, worlds, and legality. Example 3.1 (Running example). A company integrates two sources (Table 2). Billing records, for each customer email, an invoice and whether it is overdue; Support records, for each internal identifier cid, a ticket and its severity. The two share no attribute directly—Billing is keyed by email, Support by cid—so the query 𝑞 (does a customer with an overdue invoice also have a highseverity ticket?) can be answered only by linking email to cid. An HR resolver supplies that link: the rule email → cid. With the resolver the link is pinned; without it the data is ambiguous—Table 3 shows two datasets 𝑤 and 𝑤 ′ that report the same Billing and Support records yet pair customers with tickets oppositely, so a@x’s overdue invoice meets a high-severity ticket in 𝑤 (𝑞 = true) but a low-severity one in 𝑤 ′ (𝑞 = false). Same observations, two answers. The running example defines multiple attributes (e.g., email and severity). The attribute universe V is the finite set of all the attributes. A world 𝑤 is a finite relation over V, and a view

Identifiability of Relational Queries in Multi-View Pretraining

5

Table 3. Two worlds that agree on the observed Billing and Support views of Table 2 but link email to cid oppositely. Under the resolver law email → cid, world 𝑤 is legal and 𝑤 ′ is not; without the law both are legal.

email

invoice

overdue

cid

ticket

severity

a@x b@x

I-1 I-2

yes no

C1 C2

T-1 T-2

hi lo

world 𝑤—legal under email → cid email

invoice

overdue

cid

ticket

severity

a@x b@x

I-1 I-2

yes no

C2 C1

T-2 T-1

lo hi

world 𝑤 ′ —illegal: a@x linked to cid=C2 𝑤 |𝑂 is its projection to a subset 𝑂 ⊆ V. If 𝑅 denotes the view 𝑤 |𝑂 then we write att(𝑅) for the set 𝑂. Table 3 shows two such worlds, 𝑤 and 𝑤 ′ : they agree on the views Billing and Support yet describe different underlying data. So, views alone do not single out one world. Interface laws are the interface’s mechanism for eliminating this ambiguity. Given two sets of attributes 𝑋, 𝑌 ⊆ V, an interface law is an expression of the form 𝑋 → 𝑌 . The running example has a single interface law, the resolver law HR = {email} → {cid}. An interface is a pair (Σ, Ω) where Σ is a finite set of interface laws, and Ω is a finite set of subsets of V, called designated overlaps. In the example, Σ = {HR} and Ω = {att(Billing), att(Support)}. So far, we have described the syntax of interfaces and worlds. Definition 3.2 defines its semantics. That is, which worlds are legal. The resolver law is what separates 𝑤 from 𝑤 ′ . Definition 3.2. A legality structure (W, Σ) consists of a nonempty set of worlds W and a set of functional dependencies Σ such that, for every 𝑋 → 𝑌 ∈ Σ and all 𝑤, 𝑤 ′ ∈ W, 𝑠 ∈ 𝑤, 𝑡 ∈ 𝑤 ′ , 𝑠 |𝑋 = 𝑡 |𝑋 =⇒ 𝑠 |𝑌 = 𝑡 |𝑌 . The worlds in W are legal. Remark 3.3. An interface law is stronger than a single-instance FD: it constrains tuples drawn from different worlds, modeling a shared, fixed component—e.g., a resolver mapping one identifier to another—whose behaviour is identical in every legal world. Example 3.4. Take Σ = {email → cid}, with the resolver of Table 2 fixing a@x ↦→ C1, b@x ↦→ C2. Of the two worlds in Table 3, 𝑤 is legal but 𝑤 ′ is not: pairing 𝑤 ′ ’s a@x tuple (cid = C2) with 𝑤’s (cid = C1) gives equal email but different cid, violating email → cid across worlds. Both agree on the observed views; only 𝑤 also respects the resolver. Drop the resolver (Σ = ∅) and both become legal—the ambiguity behind non-identifiability. The overlap evidence is what the designated overlaps expose directly; together with everything the interface laws derive from it, this forms the interface evidence. How far does an interface law carry overlap evidence? In the running example, from email to cid; in general, the reach is captured by a single standard notion, attribute closure, applied to the designated overlaps. Given Σ, the attribute closure 𝑋 Σ+ of a set 𝑋 ⊆ V is the standard Armstrong closure: the least superset of 𝑋 closed under all rules in Σ. It is computed in polynomial time via forward chaining.

6

Ratan Bahadur Thapa and Daniel Hernández

Overlap augmentation applies this closure to the overlaps: a designated overlap 𝑂 ⊆ V (one e = 𝑂 + , the attributes the interface laws make 𝑂 ∈ Ω) is extended to its closure-augmented schema 𝑂 Σ determinable from 𝑂-evidence. A single overlap closure captures what one overlap determines on its own; but a query may need attributes spread across several overlaps, linked only by chaining through the attributes those overlaps share. To track this combined reach—which attributes the interface ties together—we collect the per-overlap closures into one graph. Definition 3.5. The constraint-closed overlap graph GΣ,Ω has vertex set V; for each designated e = 𝑂 + . Its connected components are constraint-closed components; overlap 𝑂, it adds a clique on 𝑂 Σ CC(𝑎) denotes the component of 𝑎 ∈ V. Example 3.6. The two designated overlaps are the view schemas: 𝑂 𝐵 = {email, invoice, overdue} f𝐵 = (Billing) and 𝑂 𝑆 = {cid, ticket, severity} (Support). With Σ = {email → cid}: 𝑂 f {email, invoice, overdue, cid} (the law extends the Billing closure to include cid); 𝑂 𝑆 = {cid, ticket, severity}. Both augmented overlaps contain cid, so GΣ,Ω has a single connected f𝐵 = {email, invoice, overdue} and component spanning all six attributes. Without the law, 𝑂 f𝑆 = {cid, ticket, severity} share no attribute—two disjoint components, one per view. 𝑂 Given an interface (Σ, Ω), the graph is computed in polynomial time in |V | + |Σ| + |overlaps| by e and then taking connected components. computing each 𝑂 4

IDENTIFIABILITY

Section 3 fixed what an interface exposes—its legal worlds and, through closure, the attributes each overlap determines. Whether this is enough to answer a query is a separate question: the interface evidence may pin down 𝑞’s answer across all legal worlds, or leave it ambiguous. A query of the first kind is identifiable; this section makes the notion precise, characterizes when it holds, and quantifies what is lost when it does not. 4.1

Observational equivalence and identifiability

The interface reveals a world only through its closure-augmented overlap projections. Two different worlds can project identically onto every overlap, leaving them indistinguishable from the interface evidence alone. We capture this as observational equivalence, and call a query identifiable when its answer never differs between two such worlds. Definition 4.1. We call 𝑤 and 𝑤 ′ obs-equivalent, written 𝑤 ∼ 𝑤 ′ , if 𝑤 |𝑂e = 𝑤 ′ |𝑂e for every designated e = 𝑂 + ). Equivalently, writing Obs(𝑤) = (𝑤 | e)𝑂 ∈Ω for the observation of 𝑤, we overlap 𝑂 (where 𝑂 𝑂 Σ ′ have 𝑤 ∼ 𝑤 iff Obs(𝑤) = Obs(𝑤 ′ ). Example 4.2. Continue the running example of Table 2: its two designated overlaps are the Billing and Support view schemas, 𝑂 𝐵 and 𝑂 𝑆 . Obs-equivalence requires agreement on their f𝐵 = {email, invoice, overdue, cid} (the resolver law email → cid closure-augmented schemas, 𝑂 f𝑆 = {cid, ticket, severity}. The worlds 𝑤 and 𝑤 ′ of Table 3 make this concrete: adds cid) and 𝑂 they agree on the Billing and Support instances but assign a@x different cid values, so they f𝐵 (which contains cid) and are not obs-equivalent. Without the resolver law, cid disagree on 𝑂 f leaves 𝑂 𝐵 and the two become obs-equivalent, differing only in a linkage the interface no longer determines. Identifiability asks whether obs-equivalence forces a query’s answer to agree. Ó We take queries to be conjunctive, the standard language of joins and projections: a CQ 𝑞 = ∃¯ 𝑧 𝑗 𝑅𝑈 𝑗 (𝑣¯𝑗 ) references Ð the attributes att(𝑞) = 𝑗 𝑈 𝑗 , its footprint, and a Boolean CQ returns true or false on each world.

Identifiability of Relational Queries in Multi-View Pretraining

7

Definition 4.3. A CQ 𝑞 is identifiable from the interface evidence if 𝑞(𝑤) = 𝑞(𝑤 ′ ) for all legal worlds 𝑤, 𝑤 ′ ∈ W with 𝑤 ∼ 𝑤 ′ . Example 4.4. With Σ = {email → cid}, the query 𝑞 reads overdue from 𝑅𝑂g𝐵 and severity f𝐵 : every atom uses a symbol from Liv , so Theorem 4.6 certifies 𝑞 as from 𝑅𝑂f𝑆 , joined on cid ∈ 𝑂 f𝐵 = {email, invoice, overdue} loses cid, leaving Billing identifiable. Without the law (Σ = ∅): 𝑂 and Support unlinked. The two worlds 𝑤 and 𝑤 ′ of Table 3 then agree on both view projections yet answer 𝑞 differently: in 𝑤, overdue a@x is paired with high-severity cid=C1 (𝑞 = true); in 𝑤 ′ , with low-severity C2 (𝑞 = false). Same evidence, different answers—𝑞 is not identifiable without the resolver law. 4.2

Certifying identifiability

Identifiability quantifies over all obs-equivalent pairs of legal worlds—far too many to test directly. But two structural conditions, each decidable from the schema alone, are sufficient. The first asks that the query’s footprint be covered by a single overlap closure: Theorem 4.5 (Closure certificate). Let 𝑞 be a CQ. If there exists a designated overlap 𝑂 such that att(𝑞) ⊆ 𝑂 Σ+, then 𝑞 is identifiable. Proof. By Definition 4.1, 𝑤 ∼ 𝑤 ′ implies 𝑤 |𝑂e = 𝑤 ′ |𝑂e for every designated overlap 𝑂. If e both worlds agree on every attribute in att(𝑞). Equal footprint projections mean att(𝑞) ⊆ 𝑂 Σ+ = 𝑂, each atom 𝑅𝑈 𝑗 of 𝑞 has identical extension in 𝑤 and 𝑤 ′ ; therefore 𝑞(𝑤) = 𝑞(𝑤 ′ ). □ Interface-visible queries. Theorem 4.5 certifies a CQ by inspecting its footprint att(𝑞) and checking that it falls within a single overlap closure—a test repeated for each query. For a broad class of queries this per-query check is unnecessary: those written over the augmented overlap layer are identifiable by their vocabulary alone. e|, interpreted on world 𝑤 as For each designated overlap 𝑂, let 𝑅𝑂e be a relation symbol of arity |𝑂 𝑤 |𝑂e, the projection of 𝑤 to the closure-augmented overlap schema. The interface-visible vocabulary is Liv = {𝑅𝑂e | 𝑂 ∈ Ω}, and a CQ is interface-visible when every one of its atoms uses a symbol from Liv . Multi-view pretraining objectives are a canonical instance: contrastive loss and co-occurrence prediction compute functions of the form ℓ (𝑤 |𝑂e, 𝑤 ′ |𝑂e), which are CQs over Liv . The next result shows every such query is identifiable, with no footprint inspection at all. Theorem 4.6 (Interface-visible identifiability). Every interface-visible CQ is identifiable. Proof. Let 𝑤 ∼ 𝑤 ′ . By Definition 4.1, 𝑤 |𝑂e = 𝑤 ′ |𝑂e for every 𝑂 ∈ Ω, so every symbol in Liv has identical extension (as a set of tuples) in both worlds. Since 𝑞 uses only symbols from Liv , its evaluation depends entirely on these extensions, and therefore 𝑞(𝑤) = 𝑞(𝑤 ′ ). □ Theorems 4.5 and 4.6 are complementary. Theorem 4.5 certifies any CQ whose footprint happens to fall in a single closure, regardless of how the query is written; Theorem 4.6 certifies CQs written over Liv , including joins across different overlaps, with no closure condition. Multi-view pretraining objectives therefore sit inside the identifiable layer by their vocabulary alone; the contribution of this paper is to characterise which downstream queries fall outside it.

8

Ratan Bahadur Thapa and Daniel Hernández

4.3

The cost of non-identifiability

The certificates above say when a query is identifiable. But when a query fails them, does that cost anything—could more data or a larger model still recover the answer? It cannot: the obstruction is structural, not statistical, and the only remedy is to change the interface. We begin with the error floor: Theorem 4.7 (Minimax lower bound). If 𝑞 is not identifiable, there exist 𝑤 ∼ 𝑤 ′ with 𝑞(𝑤) ≠ 𝑞(𝑤 ′ ). For any estimator 𝑞b whose output depends only on interface evidence, sup

𝑢 ∈ {𝑤,𝑤 ′ }

Pr[b 𝑞 (𝑢) ≠ 𝑞(𝑢)] ≥ 12

under 0–1 loss. The 21 error floor is irreducible. Proof. Since 𝑞 is not identifiable, by Definition 4.3 there exist 𝑤 ∼ 𝑤 ′ with 𝑤, 𝑤 ′ ∈ W and 𝑞(𝑤) ≠ 𝑞(𝑤 ′ ). Since 𝑤 ∼ 𝑤 ′ , both worlds produce identical interface evidence; any estimator 𝑞b depending only on interface evidence satisfies 𝑞b(𝑤) = 𝑞b(𝑤 ′ ). Without loss of generality, 𝑞(𝑤) = true and 𝑞(𝑤 ′ ) = false. If 𝑞b(𝑤) = 𝑞b(𝑤 ′ ) = true, then 𝑞b errs on 𝑤 ′ ; if 𝑞b(𝑤) = 𝑞b(𝑤 ′ ) = false, it errs on 𝑤. In both cases the estimator misclassifies at least one element of {𝑤, 𝑤 ′ }, so sup Pr[b 𝑞 (𝑢) ≠ 𝑞(𝑢)] ≥ 21 . 𝑢 ∈ {𝑤,𝑤 ′ }

No estimator depending only on interface evidence can do better, since it cannot distinguish 𝑤 from 𝑤 ′ . □ Outcome lower bounds. Theorem 4.7 establishes that no predictor can beat the 1/2 error floor on non-identifiable queries. But that bound is uniform—it says nothing about the cost of correctly answering queries that are identifiable. For those, the interface imposes a dual constraint that Theorem 4.8 makes precise: a minimum number of bits any correct predictor must encode. Write 𝑚𝑞 = |{𝑞(𝑤) | 𝑤 ∈ W}| for the outcome multiplicity of an identifiable CQ 𝑞—the number of distinct answer values it realises over all legal worlds. Theorem 4.8 (Outcome lower bound). Let 𝑞 be an identifiable CQ with multiplicity 𝑚𝑞 . Any predictor that reads interface evidence, stores it in a representation of size at most 2𝑘 , and answers 𝑞 correctly on every 𝑤 ∈ W must satisfy 𝑘 ≥ log2 𝑚𝑞 . Proof. Since 𝑞 is identifiable it induces a well-defined map on W/∼. Distinct elements of 𝑌𝑞 = {𝑞(𝑤) | 𝑤 ∈ W} correspond to distinct equivalence classes, so the representation must have at least 𝑚𝑞 states: 2𝑘 ≥ 𝑚𝑞 . □ The distributional version follows from Fano’s inequality [15]: Corollary 4.9 (Fano lower bound). Let 𝑞 be an identifiable CQ with 𝑚𝑞 ≥ 2. Under a uniform prior over obs-equivalence classes, any predictor whose internal representation 𝑅 has at most 2𝑘 states satisfies 𝐼 (𝑞; 𝑅) + 1 𝑘 +1 Pr[b 𝑞 ≠ 𝑞] ≥ 1 − ≥ 1− . log2 𝑚𝑞 log2 𝑚𝑞 Achieving error at most 𝛿 requires 𝑘 ≥ (1 − 𝛿) log2 𝑚𝑞 − 1. For Boolean queries (𝑚𝑞 ≤ 2) a single bit suffices; the bound becomes strictly informative for 𝑚𝑞 > 2, where the required capacity grows as log2 𝑚𝑞 —quantifying the minimum interface complexity of answering 𝑞.

Identifiability of Relational Queries in Multi-View Pretraining

9

The results so far treat the interface as fixed, characterising which queries are identifiable under a given (Σ, Ω). But the interface is itself a design target—adding overlaps or laws changes it. Even a single such addition can flip a query’s status discontinuously, a capability jump: Theorem 4.10 (Capability jumps). Let 𝑞 have atoms 𝑅𝑈1 , . . . , 𝑅𝑈𝑚 . Under an augmented interface with law set Σ′ and overlaps Ω ′ : if for every atom 𝑗 there exists a designated overlap 𝑂 𝑗 (under Ω ′ ) with att(𝑈 𝑗 ) ⊆ 𝑂 𝑗 +Σ′ , then 𝑞 is identifiable under the augmented interface. If 𝑞 was not identifiable before augmentation, this constitutes a structural capability jump. Proof. By Definition 4.1, 𝑤 ∼′ 𝑤 ′ under (Σ′, Ω ′ ) requires 𝑤 |𝑂 𝑗 +Σ′ = 𝑤 ′ |𝑂 𝑗 +Σ′ for every designated overlap 𝑂 𝑗 ∈ Ω ′ . Since att(𝑈 𝑗 ) ⊆ 𝑂 𝑗 +Σ′ for each atom 𝑗, both worlds agree on att(𝑈 𝑗 ), and therefore 𝑞(𝑤) = 𝑞(𝑤 ′ ). □ 4.4

Identifiability and multi-view pretraining

Identifiability is a structural property of the interface. But a multi-view pretraining system never computes a closure—it only drives down an overlap-anchored loss. Does the structural notion constrain what such a system can deliver? It does: once the loss falls below a fixed threshold, the predictor must return the unique answer on every certified query, regardless of capacity or sample size. We measure prediction quality by Jensen–Shannon divergence [28], under which the identifiability dichotomy induces a sharp quantitative boundary. Definition 4.11. The pair discrepancy of 𝑞 under interface 𝐼 is  ΔJS (𝑞, 𝐼 ) = sup JS(𝛿𝑞 (𝑤 ) ∥𝛿𝑞 (𝑤 ′ ) ) : 𝑤, 𝑤 ′ ∈ W, 𝑤 ∼ 𝑤 ′ . Since 𝑞 takes values in a finite set, JS(𝛿𝑞 (𝑤 ) ∥𝛿𝑞 (𝑤 ′ ) ) equals 1 bit when 𝑞(𝑤) ≠ 𝑞(𝑤 ′ ) and 0 otherwise (using log2 ; this holds for all CQs: any two distinct answer values, whether Boolean or tuple-sets, yield JS = 1 bit between the corresponding Dirac masses); hence ΔJS (𝑞, 𝐼 ) ∈ {0, 1}. Theorem 4.12 (Zero-discrepancy threshold). ΔJS (𝑞, 𝐼 ) = 0 if and only if 𝑞 is identifiable under 𝐼 . Consequently, if att(𝑞) ⊆ 𝑂 Σ+ for some 𝑂 ∈ Ω, the interface achieves ΔJS = 0; augmenting the interface to satisfy this condition reduces pair discrepancy discontinuously from 1 to 0. Proof. (⇒) If 𝑞 is identifiable then 𝑞(𝑤) = 𝑞(𝑤 ′ ) for every 𝑤 ∼ 𝑤 ′ , so every term in the sup is 0. (⇐) Contrapositive: if 𝑞 is not identifiable there exist 𝑤 ∼ 𝑤 ′ with 𝑞(𝑤) ≠ 𝑞(𝑤 ′ ), giving ΔJS = 1 > 0. The closure certificate (Theorem 4.5) provides a checkable sufficient condition for ΔJS = 0. □ The threshold is sharp: no augmentation can achieve 0 < ΔJS < 1. A quantitative, noise-tolerant refinement—a small overlap loss, not only an exactly zero one, already forces exact agreement on certified queries—is given below (Theorem 4.14). Sections 6.2–6.5 validate Theorems 4.5–4.10 directly. Implication for pretraining practice. Theorem 4.12 separates two distinct quantities. The pair discrepancy ΔJS (𝑞, 𝐼 ) ∈ {0, 1} is structural: determined by the interface alone, ΔJS = 0 iff 𝑞 is identifiable. The training loss is a model quantity: a pretraining pipeline drives its overlap loss toward zero, and a predictor that lands in the low-loss slice is constrained by Theorem 4.14 to return the unique answer on every certified query, independently of sample size. For non-certified queries, ΔJS = 1 is irreducible regardless of training, and the 1/2 floor of Theorem 4.7 applies. Certifiability is therefore the checkable structural condition separating what pretraining can deliver from what it fundamentally cannot; the MinAug prescriptions in §5 identify the minimal interface changes that move a non-certifiable query across that boundary.

10

Ratan Bahadur Thapa and Daniel Hernández

Pretraining objective and noise tolerance. We make the pretraining connection precise. A multiview model is an amortised inference map 𝑞𝜃 (· | 𝐸) ∈ Δ(W) from interface evidence 𝐸 to a posterior over legal worlds, evaluated through the induced query estimator 𝑞b(𝐸). Pretraining minimises an overlap-anchored loss whose term for a designated overlap 𝑂 compares each world’s closure-augmented projection to an anchor 𝑝𝑂 fixed across worlds (e.g., the observed evidence on e 𝑂):
ℓov (𝑤) ≥ 𝜂𝑂 JS 𝛿 𝑤 |𝑂e 𝑝𝑂 , 𝜂𝑂 > 0, with JS in nats (𝜅=1). The zero-discrepancy threshold then admits a quantitative form: a small loss already forces exact agreement. Lemma 4.13. Let 𝑝 ∈ Δ(X) on a finite set and 𝑥, 𝑥 ′ ∈ X. If JS(𝛿𝑥 ∥𝑝) ≤ 𝛾 and JS(𝛿𝑥 ′ ∥𝑝) ≤ 𝛾 with 𝛾 < 8𝜅1 , then 𝑥 = 𝑥 ′ . Proof. For a point mass, a Pinsker-type bound for Jensen–Shannon divergence [28] gives √ 𝑝 (𝑥) ≥ 1 − 2𝜅𝛾 whenever JS(𝛿𝑥 ∥𝑝) ≤ 𝛾; for 𝛾 < 8𝜅1 this exceeds 12 , and likewise 𝑝 (𝑥 ′ ) > 12 . A □ finite distribution has at most one value of mass exceeding 12 , so 𝑥 = 𝑥 ′ . Call 𝑞 (𝜀, 0)-identifiable when 𝑞(𝑤) = 𝑞(𝑤 ′ ) for all 𝑤, 𝑤 ′ ∈ W with ℓov (𝑤), ℓov (𝑤 ′ ) ≤ 𝜀. A small enough loss guarantees it: Theorem 4.14 (Robust threshold). Suppose att(𝑞) ⊆ 𝑂 Σ+ for a designated overlap 𝑂 whose loss term is anchored as above, and let 𝜀 0 = 𝜂𝑂 /(8𝜅). Then for every 𝜀 < 𝜀 0 , 𝑞 is (𝜀, 0)-identifiable. Proof. If ℓov (𝑤), ℓov (𝑤 ′ ) ≤ 𝜀 < 𝜀 0 , both anchored terms are at most 𝜀/𝜂𝑂 < 8𝜅1 , so Lemma 4.13 e the two worlds agree on the whole footprint; each atom gives 𝑤 |𝑂e = 𝑤 ′ |𝑂e. Since att(𝑞) ⊆ 𝑂 Σ+ = 𝑂, 𝑅𝑈 𝑗 has identical extension in both worlds, so 𝑞(𝑤) = 𝑞(𝑤 ′ ). □ A pretraining run that drives the overlap loss below 𝜀 0 is therefore forced to the unique answer on every certified query—certified queries are structurally determined, so this is independent of sample size; whether a given architecture can drive loss below 𝜀 0 is a separate architectural question—while leaving the 1/2 floor of Theorem 4.7 untouched for non-certified queries. Certifiability, not data volume, governs what pretraining can deliver. 4.5

Witnesses and completeness

The closure certificate (Theorem 4.5) is sufficient, but its failure is not a proof of non-identifiability: a query whose footprint escapes every overlap closure can still be identifiable if the legal class simply lacks the world pairs that would realise the gap the missing closure permits. The constructive dual settles it—a non-identifiability witness for 𝑞 under 𝐼 is a pair (𝑤, 𝑤 ′ ) ∈ W 2 with 𝑤 ∼ 𝑤 ′ and 𝑞(𝑤) ≠ 𝑞(𝑤 ′ ), and its existence proves non-identifiability directly (Proposition 4.15). On closure-separable instances every failed certificate yields such a witness, so the test is complete. Proposition 4.15 (Dual certificates). (i) 𝑞 is identifiable iff no witness exists. (ii) If 𝑞 satisfies the closure certificate of Theorem 4.5—every atom footprint lies within some overlap closure—then no witness exists. (iii) If a witness exists, the closure certificate fails. Proof. (i) is Definition 4.3. (ii): the closure certificate gives 𝑈 𝑗 ⊆ 𝑂 𝑗 +Σ for each atom 𝑅𝑈 𝑗 and some overlap 𝑂 𝑗 . By Definition 4.1, 𝑤 ∼ 𝑤 ′ implies 𝑤 |𝑂 𝑗 +Σ = 𝑤 ′ |𝑂 𝑗 +Σ for each 𝑗; since 𝑈 𝑗 ⊆ 𝑂 𝑗 +Σ , both worlds agree on every attribute in 𝑈 𝑗 , hence on relation 𝑅𝑈 𝑗 . Agreement on every atom relation gives 𝑞(𝑤) = 𝑞(𝑤 ′ ) (Theorem 4.5 is the special case where one overlap covers all atoms). (iii) is the contrapositive of (ii). □

Identifiability of Relational Queries in Multi-View Pretraining

11

Proposition 4.16 (Monotone witness shrinkage). Let 𝐼 ′ extend 𝐼 with additional overlaps or FDs. The obs-equivalence ∼′ under 𝐼 ′ is finer than ∼: if 𝑤 ≁′ 𝑤 ′ then (𝑤, 𝑤 ′ ) is no longer a witness under 𝐼 ′ . Augmentation can only eliminate witnesses, never create them. Proof. Each new overlap or FD adds constraints to obs-equivalence, separating additional world pairs. A pair that was indistinguishable under 𝐼 may be distinguishable under 𝐼 ′ , removing it from the witness set. No pair becomes indistinguishable by adding evidence, so {(𝑤, 𝑤 ′ ) : 𝑤 ∼′ 𝑤 ′ } ⊆ {(𝑤, 𝑤 ′ ) : 𝑤 ∼ 𝑤 ′ }. □ When is the certificate complete? Proposition 4.15 shows certification is sound. It is not complete in general: a query can fail the closure test yet still be identifiable if no two legal worlds happen to realise the ambiguity the missing closure permits. Completeness requires the legal class to be closure-separable, made precise below. Say the interface has 𝑆-ambiguity, for 𝑆 ⊆ V, if some 𝑤 ∼ 𝑤 ′ in W disagree on the projection, 𝑤 |𝑆 ≠ 𝑤 ′ |𝑆 . This is exactly what makes a projection query fail: Theorem 4.17 (Projection witness). Let 𝑆 ⊆ att(𝑈 ) for a view 𝑈 , and suppose the interface has 𝑆-ambiguity witnessed by 𝑤 ∼ 𝑤 ′ . Then the projection CQ 𝑞𝑆 (𝑥¯𝑆 ) = ∃¯ 𝑧 𝑅𝑈 (𝑣¯𝑈 )—with the positions in 𝑆 free and the rest existentially quantified—is not identifiable. Proof. As 𝑤 |𝑆 ≠ 𝑤 ′ |𝑆 , some 𝑆-tuple lies in exactly one of 𝑤 |𝑆 , 𝑤 ′ |𝑆 , hence in the answer set of 𝑞𝑆 for exactly one of the two worlds; since 𝑤 ∼ 𝑤 ′ , Definition 4.3 fails for 𝑞𝑆 . □ Call the legality structure closure-separable for 𝑆 ⊆ V when failure of closure coverage—𝑆 ⊈ 𝑂 Σ+ for every 𝑂 ∈ Ω—forces 𝑆-ambiguity. On such instances the certificate is complete: Corollary 4.18 (Completeness on separable instances). Under closure-separability for 𝑆, the closure certificate is complete for the projection CQ 𝑞𝑆 : 𝑞𝑆 is identifiable if and only if 𝑆 ⊆ 𝑂 Σ+ for some 𝑂 ∈ Ω. Hence on closure-separable instances the closure certificate fails only for genuinely non-identifiable queries, and the minimum augmentation is then tight: no smaller set of interface actions can make 𝑞𝑆 identifiable. Proof. If such 𝑂 exists, Theorem 4.5 gives identifiability. Otherwise closure-separability yields 𝑤 ∼ 𝑤 ′ with 𝑤 |𝑆 ≠ 𝑤 ′ |𝑆 , and Theorem 4.17 produces a witness, so 𝑞𝑆 is not identifiable. □ Remark 4.19. Closure-separability is a genuine richness condition: without it, failure of closure coverage means uncertified, not necessarily non-identifiable. The exhaustive benchmark of §6.2— where every non-certified single-atom query admits an explicit witness—is its empirical counterpart: those instances are closure-separable by construction. A feasible MinAug solution therefore eliminates every remaining witness (Proposition 4.15): the augmented interface certifies 𝑞, so no witness pair can exist under it. Finding the minimum such solution is the MinAug problem (§5). 5

ALGORITHMS

CheckCert. CheckCert decides whether a given query 𝑞 is certified by the interface (Σ, Ω). It e = 𝑂 + for each designated overlap 𝑂 via forward chaining, then checks each atom computes 𝑂 Σ e for some designated overlap 𝑂, with a possibly of 𝑞 separately: atom 𝑅𝑈 𝑗 is covered if 𝑈 𝑗 ⊆ 𝑂 different overlap per atom. If every atom is covered it returns Certified, otherwise Uncertified together with the uncovered atoms. Each covered atom is interface-visible, so certification implies identifiability by Theorem 4.6 (the special case in which one overlap covers the entire footprint is Theorem 4.5); the test mirrors the atom obligations Greedy-MinAug discharges, so it certifies

12

Ratan Bahadur Thapa and Daniel Hernández

Algorithm 1 Greedy-MinAug (Unweighted & Weighted) Require: Σ, atom obligations B𝑄 , atom schemas {att(𝑈 𝑗 )} 𝑗 ∈ B𝑄 , candidates A, (optional) costs 𝑐 : A → R>0 (default 𝑐 ≡ 1). Ensure: Selected actions Agreedy ⊆ A. 1: Precompute Cover(𝐴) ← { 𝑗 ∈ B𝑄 | att(𝑈 𝑗 ) ⊆ 𝐴+ Σ } for all 𝐴 ∈ A. 2: 𝐶 ← ∅; A greedy ← ∅. 3: while 𝐶 ≠ B𝑄 do 4: 𝐴∗ ← arg max𝐴∈ A\Agreedy | Cover(𝐴) \ 𝐶 |/𝑐 (𝐴) 5: if | Cover(𝐴∗ ) \ 𝐶 | = 0 then 6: return Infeasible 7: end if 8: Agreedy ← Agreedy ∪ {𝐴∗ }; 𝐶 ← 𝐶 ∪ Cover(𝐴∗ ) 9: end while 10: 11: return A greedy

multi-atom queries that join across different overlaps rather than requiring a single closure to cover the whole footprint. The computation is polynomial in |V | + |Σ| + |overlaps|. For workloads, the overlap closures are precomputed once and shared across all queries. Minimum interface augmentation. When 𝑞 is not certified, the designer asks: what is the smallest set of new interface actions (e.g., adding a resolver, identifier, or crosswalk) that would make 𝑞 identifiable? An action 𝐴 ⊆ V creates a new designated overlap whose closure-augmented schema is 𝐴+Σ ; its atom coverage is the set of atoms of 𝑞 it resolves: Cover(𝐴) = { 𝑗 | att(𝑈 𝑗 ) ⊆ 𝐴+Σ }. Definition 5.1. Given query 𝑞 with atom obligations B𝑄 = {1, . . . , 𝑚} and candidate actions A, Ð MinAug asks for a minimum-cardinality A ′ ⊆ A with B𝑄 ⊆ 𝐴∈ A ′ Cover(𝐴). For a workload, B𝑄 is the disjoint union of obligations over all queries. Any feasible MinAug solution makes 𝑞 identifiable: each chosen action becomes a designated overlap whose closure certifies the corresponding atom obligation, so Theorem 4.10 applies (each atom is covered by its own overlap under the augmented interface). MinAug reduces exactly to Set Cover. We use the standard greedy algorithm: Theorem 5.2. The decision version of MinAug is NP-complete even when Σ = ∅. For Algorithm 1 with 𝑐 ≡ 1: |Agreedy | ≤ 𝐻 | B𝑄 | · |Aopt | ≤ (1 + ln |B𝑄 |) · |Aopt |, Í where Aopt is an optimal solution and 𝐻𝑘 = 𝑘𝑖=1 1/𝑖. The same logarithmic bound holds for the weighted variant (replacing cardinality with total cost). Proof. NP-hardness. Reduce from Set Cover: given universe {1, . . . , 𝑚} and sets 𝑇1, . . . ,𝑇𝑝 , introduce one attribute 𝑎 𝑗 per element, one unary atom 𝑅 {𝑎 𝑗 } per element as atom obligations B𝑄 = {1, . . . , 𝑚}, and candidate action 𝐴𝑖 = {𝑎 𝑗 | 𝑗 ∈ 𝑇𝑖 } for each set 𝑇𝑖 , with Σ = ∅. Then 𝐴𝑖 +Σ = 𝐴𝑖 and Cover(𝐴𝑖 ) = 𝑇𝑖 . A size-𝑘 solution to MinAug exists iff a size-𝑘 set cover exists. Membership in NP is immediate: guess a subset of candidates and verify coverage in polynomial time. Greedy bound. With 𝑐 ≡ 1, Algorithm 1 is the standard greedy Set Cover algorithm applied to the coverage function. The 𝐻 | B𝑄 | bound is the classical greedy approximation ratio for Set Cover; the weighted variant follows from the analogous weighted analysis. □

Identifiability of Relational Queries in Multi-View Pretraining

6

13

EXPERIMENTAL EVALUATION

Schema-design walkthrough. Theorems 4.5–4.10 translate directly into a two-step schema-design workflow. Step 1 (CheckCert): given the current interface (Σ, Ω) and a target query 𝑞, run CheckCert to decide whether every atom footprint of 𝑞 lies within some overlap closure 𝑂 Σ+ (a possibly different overlap per atom). If so, 𝑞 is identifiable and no augmentation is needed. Step 2 (Greedy-MinAug): if 𝑞 is not certified, enumerate candidate interface actions (e.g., adding a resolver, crosswalk, or shared identifier), compute their atom coverages, and run Greedy-MinAug to find the smallest set of actions that covers all atom obligations. Any feasible solution makes 𝑞 identifiable by Theorem 4.10. The experiments below validate both steps at scale. We evaluate CheckCert and Greedy-MinAug as schema-design tools: given a relational schema with functional dependencies and an overlap policy, do the algorithms correctly decide identifiability, witness failures, and recommend minimal augmentations at practical cost? We address four research questions. RQ1 Is the closure certificate (Theorem 4.5) exact for single-atom Boolean CQs under single-row world semantics—confirming every certified query identifiable and finding an explicit witness for every non-certified one? RQ2 Does the certificate correctly classify real integration datasets, and can non-identifiability be witnessed in real data? RQ3 Does Greedy-MinAug (Algorithm 1) achieve practical approximation ratios on realistic schemas? RQ4 Do CheckCert and Greedy-MinAug remain practical at database-scale schemas (|Attr | and |Σ| up to 103 )? Section 6.7 presents confirmatory ML classifier experiments showing that non-identifiable queries exhibit the 1/2 error floor (Theorem 4.7) and that augmentation produces the capability jumps predicted by Theorem 4.10. All RQ1–RQ4 experiments run on CPU; the confirmatory ML experiments use a GPU node equipped with an NVIDIA A40 GPU (48 GB VRAM) and a 128-core CPU, running CUDA 12.1 and PyTorch 2.3. 6.1

Setup

Synthetic benchmark. We use a CRM-inspired schema with 𝑛=5 attributes over a binary domain (𝑑=2) and three views (customer, order, support), inducing overlaps on their pairwise intersections. A legality structure (W, Σ) is instantiated by drawing functional dependencies uniformly at random from attribute pairs, then generating worlds of 𝑚 tuples consistent with Σ via shared resolvers (lookup tables keyed on FD antecedents). For each (Σ, Ω, 𝑞), identifiability of the target CQ 𝑞 is checked using Theorem 4.5. Exactness benchmark (RQ1). We use a resolver-free exhaustive enumerator. Worlds are all 𝑑 𝑛 FD-satisfying single-row assignments (𝑚=1), giving universal identifiability semantics (not restricted to resolver-generated worlds). For each (Σ, Ω, 𝑞), the enumerator groups worlds by observation and checks whether obs-equivalent worlds agree on 𝑞. Confirmatory ML (Section 6.7). Worlds are generated by the resolver model: 𝑚 ∈ {10, 30, 50} tuples consistent with Σ via shared resolver tables (lookup tables keyed on FD antecedents); training-set sizes 𝑁 ∈ {103, 5×103, 5×104 }. Real-world datasets. BibInteg is built from the OpenAlex API [32], using 10,000 computer-science papers (2015–2024) with verified DOIs. Three views mirror the DBLP/ACM/SemanticScholar schema: DBLP exposes {title, author, year, venue}; ACM exposes {title, author, year, doi}; SemanticScholar exposes {title, author, year, n_authors}. All three views share overlap 𝑂={title, author, year}. Interface laws: 𝑂 → venue, 𝑂 → doi, 𝑂 → n_authors, {year} → decade, so the Σ-closure of 𝑂 covers all seven attributes and every single-view existential query is certified. WDC-Product [33] provides the schema for a design case study, drawing its attribute structure from the Web Data Commons product corpus spanning Amazon, Walmart, and Best Buy listings. Amazon exposes {brand, model, category, price, rating}; Walmart exposes {brand, model, category, price, in_stock}; Best Buy exposes

14

Ratan Bahadur Thapa and Daniel Hernández

e Table 4. BibInteg schema. 𝑂={0, 1, 2}; FDs: 𝑂→3, 𝑂→4, 𝑂→5, {2}→6; 𝑂={0, . . . , 6}. All queries certified (C).

Attr

Semantics

DBLP

ACM

SS

∈𝑂

e ∈𝑂

0 1 2 3 4 5 6

title author year venue doi n_authors decade

✓ ✓ ✓ ✓ – – –

✓ ✓ ✓ – ✓ – –

✓ ✓ ✓ – – ✓ –

✓ ✓ ✓ – – – –

✓ ✓ ✓ ✓ ✓ ✓ ✓

e C Q_venue: footprint {0, 1, 2, 3} ⊆ 𝑂 e Q_doi: footprint {0, 1, 2, 4} ⊆ 𝑂 C e C Q_large_team: footprint {0, 1, 2, 5} ⊆ 𝑂 {brand, model, category, n_reviews}. Shared overlap 𝑂={brand, model, category}; interface laws {brand, model} → category, {brand, model} → price, {brand, model} → in_stock e yield 𝑂={brand, model, category, price, in_stock}. Both rating and n_reviews are outside the closure, yielding three non-certified queries: Q_highly_rated (Amazon rating≥4), Q_reviewed (Best Buy n_reviews≥32), and Q_popular (Amazon rating≥4 joined with Best Buy n_reviews≥32). Two certified queries ask whether a product is available (Q_available: Walmart e or inexpensive (Q_cheap: Walmart price<𝑝 0 , footprint in_stock=1, footprint {0, 1, 2, 6} ⊆ 𝑂) e {0, 1, 2, 3} ⊆ 𝑂). BibInteg and CrossKG-DBLP form single-tuple worlds (𝑚=1); Amazon-Google and Fodors-Zagat form 2-tuple matched-pair worlds—all with far smaller world multiplicity than the confirmatory ML setup (𝑚 ∈ {10, 30, 50}). WDC data construction. Raw WDC listings lack rating, n_reviews, and in_stock; these are synthesized from brand/model keys to enforce the certified/uncertified split by construction. WDC is a schema stress test; real interface-law validation is on the four real-record datasets (§6.3). CrossKG-DBLP aligns 11,800 computer-science papers from DBLP and OpenAlex on shared overlap 𝑂={title, author, year} with interface law 𝑂 → doi. Q_publisher (publication publisher, identified by DOI prefix) is certified; Q_large_team (co-author count exceeding a threshold) is uncertified—DBLP and OpenAlex maintain independent author lists with no reconciliation law across sources. Amazon-Google [33] aligns 1,046 product pairs from Amazon and Google Shopping. Matched-pair identity forms the shared overlap 𝑂; Q_catalog (whether a product is in a given catalog segment) is certified. No interface law constrains price across sources—Amazon and Google list different prices for the same product (e.g., $395 vs. $319.95)—so Q_expensive (price≥$50) is uncertified. Fodors-Zagat [33] aligns 110 restaurant pairs from the Fodors and Zagat guides. Matched-pair identity and shared restaurant segment form 𝑂; Q_segment is certified. No interface law reconciles cuisine labels—the two guides categorize the same restaurant differently (e.g., “asian” vs. “japanese”)—so Q_cuisine is uncertified. This dataset is inherently small (∼112 gold pairs total in the Magellan benchmark); we include it for domain breadth. Tables 4 and 5 give the attribute schemas, interface laws, and query certification status for BibInteg and WDC-Product. Predictor architectures. We evaluate four architectures spanning the structure-agnostic to theoryexploiting spectrum, plus two baselines. MLP: view marginals are concatenated into a feature vector, passed through a two-layer ReLU network with hidden dimension ℎ=64. SetTransformer (ST) [22]: attribute-value tokens from each view form a set; cross-view multi-head attention precedes the

Identifiability of Relational Queries in Multi-View Pretraining

15

e Table 5. WDC-Product schema. 𝑂={0, 1, 2}; FDs: {0, 1}→2, {0, 1}→3, {0, 1}→6; 𝑂={0, 1, 2, 3, 6}. Attrs 4, 5 lie e outside 𝑂; three queries uncertified (U).

Attr

Semantics

Amazon

Walmart

BestBuy

∈𝑂

e ∈𝑂

0 1 2 3 4 5 6

brand model category price rating n_reviews in_stock

✓ ✓ ✓ ✓ ✓ – –

✓ ✓ ✓ ✓ – – ✓

✓ ✓ ✓ – – ✓ –

✓ ✓ ✓ – – – –

✓ ✓ ✓ ✓ – – ✓

e C Q_available: footprint {0, 1, 2, 6} ⊆ 𝑂 e C Q_cheap: footprint {0, 1, 2, 3} ⊆ 𝑂 e U Q_highly_rated: footprint {0, 1, 2, 4} ⊈ 𝑂 e Q_reviewed: footprint {0, 1, 2, 5} ⊈ 𝑂 U e U Q_popular: footprint {0, 1, 2, 4, 5} ⊈ 𝑂 classification head. GNN-OG: message passing over the constraint-closed overlap graph GΣ,Ω (Definition 3.5); overlap-marginal features propagate along overlap edges before pooling. ClosureAware (CA): if the closure certificate holds, the answer is read from the closure-augmented overlap projection without learned inference; otherwise falls back to GNN-OG. Baselines: VanillaOv (logistic regression over Σ-closed overlap features; no hidden layers, tests whether linear expressivity suffices) and MajVote (constant majority predictor). Metrics. Boolean CQs: balanced accuracy 12 (TPR + TNR), which equals 1/2 for any majority-class predictor regardless of class imbalance, making it the correct empirical proxy for the 1/2 error floor of Theorem 4.7. MinAug: approximation ratio |Agreedy |/|Aopt | and wall-clock runtime. All error bars are over worlds; results are averaged over three random seeds. 6.2

Certificate Exactness (RQ1)

We construct a benchmark of 841 instances by sampling 200 random schemas (𝑛 ∈ {4, 6, 8} attributes, domain size 𝑑=3, up to four FDs) and generating five single-atom Boolean CQs per schema, split evenly between certified and non-certified. For each instance we run both the closure certificate and an exhaustive identifiability verifier. The verifier enumerates all 𝑑 𝑛 single-row worlds under relational FD semantics—the semantics of the theory, not the resolver model—and groups them by observation; for certified queries it checks that no group contains conflicting answers, and for non-certified queries it returns an explicit witness pair (𝑤, 𝑤 ′ ) with Obs(𝑤)=Obs(𝑤 ′ ) and 𝑞(𝑤)≠𝑞(𝑤 ′ ). Of the 353 certified instances, all 353 pass the observation-consistency check (100%, zero violations). Of the 488 non-certified instances, all 488 have an explicit witness (100%). Within this restricted class (single-atom Boolean CQs, single-row worlds), the certificate is exact on both sides; completeness is not claimed beyond this class. 6.3

Real-World Certification and Witnesses (RQ2)

Answer to RQ2: Yes across all three domains (Table 6). On BibInteg: all three queries are certified; laws hold on ≥99.9% of records, and the few violations are genuine non-identifiability witnesses (e.g., The ARRIVE guidelines 2.0 appears under one key with three venues and three DOIs). On

16

Ratan Bahadur Thapa and Daniel Hernández

Table 6. Real-data coverage: 3 domains, 5 datasets, 14 queries. C = certified (Theorem 4.5); W = real witness found; U = uncertified, schema-only (WDC).

Dataset

Domain

C/W/U

BibInteg (9,992 papers) CrossKG-DBLP (11,800 papers) Amazon-Google (1,046 pairs) Fodors-Zagat (110 pairs) WDC-Product (schema only)

scholarly scholarly product restaurant —

3C 1C 1W 1C 1W 1C 1W 2C 3U

Total

8C 3W 3U

Table 7. Balanced accuracy on all four real-world datasets. C = certified; U = uncertified; bold entries exceed the error floor (> 0.505); 3 seeds per cell; stds = 0.00 throughout. MLP/ST/VanillaOv = 1.0 on every certified query; GNN-OG/CA/MajVote = 0.5 on every certified query (see text). 𝑁 train =5000 (BibInteg); ∼120 training pairs (Fodors-Zagat; VanillaOv = 0.69 is small-sample noise).

Dataset

Query

C/U

MLP

BibInteg

Q_venue Q_doi Q_large_team

C C C

CrossKG-DBLP

Q_publisher Q_large_team

Amazon-Google Fodors-Zagat

ST

GNN-OG

CA

VanillaOv

MajVote

1.00 1.00 1.00 1.00 1.00 1.00

0.50 0.50 0.50 0.50 0.50 0.50

1.00 1.00 1.00

0.50 0.50 0.50

C U

1.00 0.50

1.00 0.50

0.50 0.50 0.50 0.50

1.00 0.50

0.50 0.50

Q_catalog Q_expensive

C U

1.00 1.00 0.50 0.52

0.50 0.50 0.50 0.50

1.00 0.51

0.50 0.50

Q_segment Q_cuisine

C U

1.00 1.00 0.52 0.54

0.50 0.50 0.50 0.50

0.69 0.53

0.50 0.50

CrossKG-DBLP: Q_publisher is certified; Q_large_team is uncertified—the same query is certified on BibInteg, whose law 𝑂 → n_authors reaches the author count, whereas DBLP and OpenAlex share no such reconciliation law—and a real witness is found in 1000/1000 random trials (median discovery position 2,100 records, positive rate 0.42). On Amazon-Google: Q_catalog is certified; 9.4% of matched pairs straddle the price threshold (first witness at scan position 62). On FodorsZagat: Q_segment is certified; cuisine labels disagree in ∼80% of matched pairs (first witness at scan position 2); the dataset is small and its value is domain breadth. Table 7 confirms the predicted pattern across all four datasets. MLP, ST, and VanillaOv reach 1.0 on every certified query; GNN-OG and CA remain at 0.50 because the single-tuple and matched-pair world structures give their overlap-graph and closure-lookup components nothing to aggregate over (cf. Section 6.7, where both reach 1.0 at 𝑚=10). Every uncertified query is at or within noise of the 0.50 floor, confirming the minimax bound of Theorem 4.7 on real data across three independent domains. 6.4

Greedy-MinAug in Practice (RQ3)

We construct multi-atom MinAug instances with |B𝑄 | ∈ {1, 2, 3, 4} atom obligations. Each atom 𝑈𝑖 has 𝑔=5 dedicated attributes forming a chain (att(𝑈𝑖 ) = {5𝑖, 5𝑖+1, . . . , 5𝑖+4} with within-atom FDs

Identifiability of Relational Queries in Multi-View Pretraining

17

(a) Ratio CDF by |B𝑄 |

(b) Solution size vs baseline

1 3

Mean actions selected

Cumulative fraction

0.8 0.6 0.4

| B𝑄 |=1 | B𝑄 |=2 | B𝑄 |=3 | B𝑄 |=4

0.2 0

1

1.2

2

1

0

1.4

Greedy Singleton-only Optimal 1

Approx. ratio

2

3

4

|B𝑄 |

Fig. 1. Greedy-MinAug approximation ratio CDF (a) and mean solution size (b). Each curve in (a) is one |B𝑄 | value; mass at 1.0 indicates optimal. Panel (b) compares Greedy (with singleton and cross-atom pair candidates), Singleton-only (pairs excluded), and the brute-force Optimal per |B𝑄 |. Table 8. Greedy-MinAug per-|B𝑄 | statistics (500 trials each). Ratio = |Agreedy |/|Aopt |; %-opt = fraction of trials with ratio 1.0. Mean actions are greedy vs. optimal (brute-force).

|B𝑄 |

%-opt

Mean ratio

Max ratio

Greedy actions

Opt. actions

1 2 3 4

100.0 98.4 89.0 79.2

1.000 1.008 1.048 1.070

1.000 1.500 1.500 1.500

1.000 1.464 2.296 3.236

1.000 1.448 2.186 3.028

{5𝑖} → 5𝑖+1 → · · · ), so a root singleton {5𝑖} covers all of atom 𝑖 via closure. A further |B𝑄 | random cross-atom FDs allow single actions to reach multiple atoms transitively. Candidates include the |B𝑄 | root singletons plus random cross-atom pairs (total ≤ 16 for brute-force feasibility; 500 trials per |B𝑄 |; 2 000 total). The singleton-only baseline restricts Greedy-MinAug to root singletons only. Figure 1 (a) shows the approximation ratio CDF per |B𝑄 |. For |B𝑄 |=1 the ratio is 1.000 on every trial—consistent with the 𝐻 1 =1 bound of Theorem 5.2. As |B𝑄 | grows the distribution spreads: at |B𝑄 |=4, 79.2% of trials remain optimal and the mean ratio is 1.070, well below 𝐻 4 ≈ 2.08. Figure 1 (b) shows that allowing cross-atom pair candidates reduces the mean augmentation size (Greedy < Singleton-only for |B𝑄 | ≥ 2), confirming that richer candidate sets translate into smaller interface augmentations. Table 8 summarises the per-|B𝑄 | statistics. Answer to RQ3: Greedy-MinAug achieves near-optimal ratios for all |B𝑄 | ∈ {1, 2, 3, 4} (Table 8; all mean ratios well below the 𝐻 | B𝑄 | bound), and richer candidate actions (singletons + pairs) reduce augmentation cost over singleton-only proposals. On all four real integration datasets (Table 9), certified queries require zero augmentation actions and non-certified queries require exactly 1 action (< 30 𝜇s each), confirming practical applicability across schema sizes and domains.

18

Ratan Bahadur Thapa and Daniel Hernández

Table 9. Greedy-MinAug on real datasets (0 actions = certified; attr indices per schema).

Dataset

Query

BibInteg

Q_doi Q_large_team Q_venue CrossKG-DBLP Q_large_team Q_publisher Amazon–Google Q_catalog Q_expensive Fodors–Zagat Q_cuisine Q_segment

Certified?

#Actions

Added attrs

yes yes yes no yes yes no no yes

0 0 0 1 0 0 1 1 0

– – – {2} – – {2} {2} –

(a) CheckCert |Σ| = 10 |Σ| = 100 |Σ| = 1000

100

Median time (ms)

Median time (ms)

100

10−1

10−2

10−3

10

100

|Attr |

(b) Greedy-MinAug

250 500 1000

10 −1

|Σ| = 10 |Σ| = 100 |Σ| = 1000

10 −2

10 −3

10

100

250 500 1000

|Attr |

Fig. 2. CheckCert (a) and Greedy-MinAug (b) median runtime versus schema size (log–log axes). Each line corresponds to a fixed FD count |Σ| ∈ {10, 100, 1000}; 𝑥-axis is the attribute count |Attr |. Both algorithms stay well below 4 ms across all 6×6 = 36 combinations tested.

6.5

Scalability (RQ4)

We sweep |Attr | and |Σ| each over {10, 50, 100, 250, 500, 1000} (36 combinations total). Certification timing uses random FD schemas; Greedy-MinAug timing uses planted instances with chain FDs that guarantee feasibility (20 candidate actions). Figure 2 shows three representative |Σ| curves. CheckCert peaks at 0.69 ms median at (|Attr |, |Σ|)=(500, 1000), consistent with its 𝑂 (|Attr |×|Σ|) cost. Greedy-MinAug with 20 candidates peaks at 3.2 ms at the largest schema (1000×1000), reflecting 𝑂 (20×|Attr |×|Σ|) precomputation. Both algorithms are dominated by the FD-closure fixed-point; at production-scale schemas with hundreds of attributes and functional dependencies, certification and augmentation complete in single-digit milliseconds. Answer to RQ4: Yes—both CheckCert and Greedy-MinAug remain practical at database-scale schemas (|Attr |, |Σ| ≤ 103 ) with sub-millisecond and low-millisecond runtimes respectively.

Identifiability of Relational Queries in Multi-View Pretraining

Certified

19

Non-certified

Balanced accuracy

1

0.5

0

te jVo Ma

Ov

la nil Va

P ML

f. ans r T Set

OG

N-

GN

CA

Fig. 3. Balanced accuracy by query type and architecture (𝑚=10, averaged over 𝑁 ∈ {103, 5×103, 5×104 } and 3 seeds). Non-certified queries (right bars) are bounded below by 1/2 for all architectures (Theorem 4.7); certified queries (left bars) converge to high balanced accuracy for structure-aware architectures.

6.6

Ablation Study

FD completeness. We vary the fraction 𝜌 of true interface laws included in Σ, sweeping 𝜌 ∈ {0, 0.25, 0.5, 0.75, 1.0}. Certificate coverage degrades monotonically as 𝜌 decreases; at 𝜌=0.5 it retains the majority of certifiable queries on the synthetic benchmark. CA error tracks certificate coverage closely, while MLP and ST degrade more slowly because they can partially recover missing closure via statistical generalization at large 𝑚; the gap closes at small sample sizes. 6.7

Confirmatory ML Experiments

We confirm Theorems 4.7 and 4.10 empirically using the six predictor architectures from Section 6.1. Error floor (E1). For each (𝑚, 𝑁 ) pair we sample 10 certified and 10 non-certified single-atom Boolean CQs, train each architecture, and report balanced accuracy. Figure 3 shows that balanced accuracy remains within 0.03 of 1/2 for all architectures on non-certified queries at every 𝑁 , confirming the irreducible error floor of Theorem 4.7. MLP, ST, GNN-OG, and CA achieve balanced accuracy 1.0 at 𝑁 =5×104 on certified queries (𝑚=10). Capability jumps (E2). We use the 5-attribute binary schema with views 𝑉0 ={0, 1} and 𝑉1 ={0, 2, 3, 4} overlapping on {0}, and query 𝑄=∃𝑥 0 . 𝑅𝑉1 (𝑥 0, 0, 0, 0). FDs {0} →𝑘 are added one at a time for 𝑘 ∈ {1, 2, 3, 4}, producing 5 interface configurations (steps 0–4); the certificate is satisfied at step 4. Figure 4 shows that the structure-preserving architectures (MLP, ST, GNN-OG, CA) remain at ≈1/2 at steps 0–1 and jump sharply when the certificate is satisfied at step 4, confirming the structural transition of Theorem 4.10. VanillaOv differs: it rises above 1/2 at intermediate steps 2–3 by exploiting statistical correlations introduced by the partial FDs, but collapses back to 1/2 at step 4, owing to a linear-expressivity failure—𝑞 is an existential query whose answer at step 4 is encoded in tuple-level relational structure that mean-pooled linear features cannot detect. This separates structural identifiability (the closure certificate guarantees the information is present in the interface evidence) from linear detectability from feature marginals. The behaviour is query-dependent: on BibInteg (Section 6.3) the certified answers are linearly decodable from the Σ-closed overlap marginals, and VanillaOv reaches 1.0 there.

Balanced accuracy

20

Ratan Bahadur Thapa and Daniel Hernández

1

MLP GNN-OG VanillaOv

0.8 0.6

Certified

SetTransf. CA MajVote

0.5

0.4 Ds

no F

+FD

1

0→

2 0→ +FD

+FD

3

0→

+FD

4

0→

Interface augmentation step Fig. 4. Balanced accuracy vs. FD-augmentation step. Steps 0–1: certificate unsatisfied, all architectures ≈1/2. Step 4: MLP and ST jump to 1.0, GNN-OG to 0.98 (identifiability guaranteed, not perfect accuracy), CA to 0.82, confirming Theorem 4.10.

7

CONCLUSION

We formalized query identifiability for data integration under an explicit relational interface model. A query is identifiable when all legal worlds consistent with the interface evidence return the same answer; when it is not, a minimax lower bound shows that for every non-identifiable query there is a witness pair on which any interface-evidence-only estimator incurs error ≥ 12 . The closure certificate (Theorem 4.5) reduces identifiability checking to forward chaining over functional dependencies, yielding the polynomial-time CheckCert algorithm. When a query is not certified, minimum augmentation (Definition 5.1) asks for the smallest set of new interface actions that would certify it; this reduces to Set Cover, and Greedy-MinAug achieves a 𝐻 | B𝑄 | approximation guarantee (Theorem 5.2). Experiments confirm that CheckCert is exact on exhaustive benchmarks and both algorithms remain practical at schemas with 103 attributes and dependencies. Scope and limitations. The closure certificate is both sufficient and necessary on separable instances (Corollary 4.18)—instances that actually contain a witness pair if one exists; on non-separable instances a failed certificate is conservative. The CQ footprint model covers single-atom Boolean CQs natively; extending certificates to UCQs, aggregation, or recursive queries requires machinery beyond attribute closure. Interface laws are restricted to FD-syntax (Armstrong implication); denial constraints, inclusion dependencies, and richer tgds are not covered. The real-data validation uses single-tuple and matched-pair worlds (𝑚≤2), while the confirmatory ML experiments span larger synthetic worlds (𝑚 ∈ {10, 30, 50}); real integration datasets with larger world multiplicity remain to be studied. WDC-Product serves as a schema-design case study—its query-critical attributes are synthesized to enforce the certified/uncertified split by construction; BibInteg, CrossKG-DBLP, Amazon-Google, and Fodors-Zagat are the real-data validations. Several directions remain open. Richer query languages (UCQs, aggregation, recursion) need new certificates beyond footprint closure. Stronger interface augmentation strategies could exploit structured FD sets to reduce outcome multiplicity exponentially. Extending the theory to multi-tuple world grouping and richer integrity constraints remains an important open direction. Identifiability is a design constraint, not only an evaluation metric.

Identifiability of Relational Queries in Multi-View Pretraining

21

REPRODUCIBILITY Experiment code is available at https://github.com/danielhz/query-identifiability and Lean 4 proofs at https://github.com/danielhz/MultiViewIdentifiability. The formalization machine-checks Theorems 4.5, 4.7, 4.8, and 4.14, the general atom-wise closure certificate (CheckCert correctness, with Theorem 4.5 as the single-overlap special case), the semantic content of the interface-visible result (Theorem 4.6; queries are modeled by their answer-invariant rather than CQ syntax), the FD/Armstrong correspondence (both directions), the reduction of identifiability to query determinacy over overlap-projection views, and Fano’s inequality itself (the information inequality behind Corollary 4.9); three separations are additionally certified as machine-checked disproofs (certificate necessity, union-of-footprints coverage, and MinAug uniqueness). Open in the formalization are the distributional Fano corollary (Corollary 4.9; its qualitative 1/2-floor form, Theorem 4.7, is machine-checked), the capability-jump theorem (Theorem 4.10; only its augmented single-overlap case is checked), and the MinAug greedy 𝐻𝑘 bound and NP-hardness (Theorem 5.2). Supplementary material includes BibInteg statistics, extended ML results, and FD-completeness curves; all artifacts (code, Lean proofs, and data) are archived at DaRUS [35]. REFERENCES [1] Serge Abiteboul and Oliver M. Duschka. 1998. The Complexity of Answering Queries Using Materialized Views. In Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. 254–263. [2] Serge Abiteboul, Richard Hull, and Victor Vianu. 1995. Foundations of Databases. Addison-Wesley. [3] Galen Andrew, Raman Arora, Jeff Bilmes, and Karen Livescu. 2013. Deep Canonical Correlation Analysis. In Proceedings of the International Conference on Machine Learning (ICML). PMLR, 1247–1255. [4] William Ward Armstrong. 1974. Dependency Structures of Data Base Relationships. In IFIP Congress, Vol. 74. Geneva, Switzerland, 580–583. [5] Catriel Beeri, Ronald Fagin, and John H Howard. 1977. A Complete Axiomatization for Functional and Multivalued Dependencies in Database Relations. In Proceedings of the 1977 ACM SIGMOD International Conference on Management of Data. 47–61. [6] Avrim Blum and Tom Mitchell. 1998. Combining Labeled and Unlabeled Data with Co-Training. In Proceedings of the eleventh annual conference on Computational learning theory. 92–100. [7] Dan Brickley, Matthew Burgess, and Natasha F. Noy. 2019. Google Dataset Search: Building a Search Engine for Datasets in an Open Web Ecosystem. In The World Wide Web Conference (WWW). ACM, 1365–1375. https://doi.org/ 10.1145/3308558.3313685 [8] Ashok K Chandra and Philip M Merlin. 1977. Optimal implementation of conjunctive queries in relational data bases. In Proceedings of the ninth annual ACM symposium on Theory of computing. 77–90. [9] Peter Christen. 2012. The Data Matching Process. In Data matching: concepts and techniques for record linkage, entity resolution, and duplicate detection. Springer, 23–35. [10] Thomas M Cover and Joy A Thomas. 2006. Elements of Information Theory. Wiley-Interscience. [11] AnHai Doan, Alon Halevy, and Zachary Ives. 2012. Principles of Data Integration. Elsevier. [12] Xin Luna Dong and Felix Naumann. 2009. Data Fusion: Resolving Data Conflicts for Integration. Proc. VLDB Endow. 2, 2 (2009), 1654–1655. [13] Ronald Fagin, Phokion G. Kolaitis, Renée J. Miller, and Lucian Popa. 2005. Data Exchange: Semantics and Query Answering. Theoretical Computer Science 336, 1 (2005), 89–124. [14] Ronald Fagin, Jeffrey D Ullman, and Moshe Y Vardi. 1983. On the semantics of updates in databases. In Proceedings of the 2nd ACM SIGACT-SIGMOD Symposium on Principles of Database Systems. 352–365. [15] Robert M. Fano. 1961. Transmission of Information: A Statistical Theory of Communication. MIT Press, Cambridge, MA. [16] Seymour Ginsburg and Richard Hull. 1983. Characterizations for functional dependency and Boyce-Codd normal form families. Theoretical Computer Science 26, 3 (1983), 243–286. [17] Tomasz Gogacz and Jerzy Marcinkowski. 2015. The Hunt for a Red Spider: Conjunctive Query Determinacy Is Undecidable. In 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS). 281–292. https://doi.org/10. 1109/LICS.2015.35 [18] Tomasz Gogacz and Jerzy Marcinkowski. 2016. Red Spider Meets a Rainworm: Conjunctive Query Finite Determinacy Is Undecidable. In 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS). 121–134. https://doi.org/10.1145/2902251.2902288

22

Ratan Bahadur Thapa and Daniel Hernández

[19] Alon Halevy, Anand Rajaraman, and Joann Ordille. 2006. Data Integration: The Teenage Years. In Proceedings of the 32nd International Conference on Very Large Data Bases. 9–16. [20] Alon Y. Halevy. 2001. Answering Queries Using Views: A Survey. The VLDB Journal 10, 4 (2001), 270–294. [21] Lucien Le Cam. 2012. Asymptotic Methods in Statistical Decision Theory. Springer. [22] Juho Lee, Yoonho Lee, Jungtaek Kim, Adam R. Kosiorek, Seungjin Choi, and Yee Whye Teh. 2019. Set Transformer: A Framework for Attention-based Permutation-Invariant Neural Networks. In Proceedings of the 36th International Conference on Machine Learning (ICML). PMLR, 3744–3753. [23] Maurizio Lenzerini. 2002. Data Integration: A Theoretical Perspective. In Proceedings of the Twenty-First ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. 233–246. [24] Alon Y. Levy, Alberto O. Mendelzon, Yehoshua Sagiv, and Divesh Srivastava. 1995. Answering Queries Using Views. In Proceedings of the Fourteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. 95–104. [25] Chen Li, Edward Chang, Ihab F. Ilyas, and Jiannan Song. 2001. Minimizing View Sets without Losing Query-Answering Power. In Proceedings of the 8th International Conference on Database Theory. 99–113. [26] Yingming Li, Ming Yang, and Zhongfei Zhang. 2018. A Survey of Multi-View Representation Learning. IEEE Transactions on Knowledge and Data Engineering 31, 10 (2018), 1863–1883. [27] Leonid Libkin. 2011. Incomplete Information and Certain Answers in General Data Models. In Proceedings of the Thirtieth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. 59–70. [28] Jianhua Lin. 1991. Divergence Measures Based on the Shannon Entropy. IEEE Transactions on Information Theory 37, 1 (1991), 145–151. https://doi.org/10.1109/18.61115 [29] Fatemeh Nargesian, Erkang Zhu, Renée J. Miller, Ken Q. Pu, and Patricia C. Arocena. 2019. Data Lake Management: Challenges and Opportunities. Proc. VLDB Endow. 12, 12 (2019), 1986–1989. https://doi.org/10.14778/3352063.3352116 [30] Alan Nash, Luc Segoufin, and Victor Vianu. 2010. Views and Queries: Determinacy and Rewriting. ACM Transactions on Database Systems 35, 3 (2010), 1–41. [31] Daniel Pasaila. 2011. Conjunctive Queries Determinacy and Rewriting. In Proceedings of the 14th International Conference on Database Theory. 220–231. [32] Jason Priem, Heather Piwowar, and Richard Orr. 2022. OpenAlex: A fully-open index of scholarly works, authors, venues, institutions, and concepts. https://openalex.org. arXiv:2205.01833. [33] Anna Primpeli and Christian Bizer. 2019. Profiling Entity Matching Benchmark Tasks. In Proceedings of the 22nd International Conference on Extending Database Technology (EDBT). 1–12. [34] Michael Stonebraker and Ihab F. Ilyas. 2018. Data Integration: The Current Status and the Way Forward. IEEE Data Eng. Bull. 41, 2 (2018), 3–9. [35] Ratan Bahadur Thapa and Daniel Hernández. 2026. Artifacts for: Identifiability of Relational Queries in Multi-View Pretraining. DaRUS, V1. https://doi.org/10.18419/DARUS-6292 [36] A. B. Tsybakov. 2009. Introduction to Nonparametric Estimation. Springer, New York. [37] Qi Zhang, Yifei Wang, and Yisen Wang. 2025. An Augmentation Overlap Theory of Contrastive Learning. Journal of Machine Learning Research 26, 228 (2025), 1–42.

Identifiability of Relational Queries in Multi-View Pretraining

23

Table 10. Correspondence between the paper’s results, this appendix, and the Lean development.

A

Result

Main text

Appx.

Lean module

Status

FD closure / Armstrong Closure certificate Certificate not necessary Atom-wise certificate Union coverage insufficient Interface-visible fragment Determinacy characterisation Minimax error floor Outcome / rate bound Capacity error bound Fano’s inequality Distributional Fano corollary Robust threshold Capability jump (augmentation) MinAug greedy / NPhardness

§3 Thm 4.5 Cor 4.18 §5 — Thm 4.6 Thm 4.6

Thm A.2 Thm A.4 Rem A.5 Thm A.7 Thm A.8 Thm A.9 Thm A.11

FDClosure proved Certificate proved Certificate disproof AtomCertificate proved InterfaceVisible disproof Determinacy proved Determinacy proved

Thm 4.7 Thm 4.8 Cor 4.9 Cor 4.9 Cor 4.9

Thm A.12 Thm A.18 Thm A.19 Thm A.22 —

Minimax OutcomeBound OutcomeBound Entropy —

proved proved proved proved open

Thm 4.14 Thm 4.10

Thm A.17 Prop A.24

Information MinAug

proved aug. case

Thm 5.2

Rem A.26

MinAug

open

MACHINE-CHECKED FORMALIZATION

This appendix restates the paper’s theoretical results with human-readable proofs, each paired with a pointer (⊢ In Lean) to the machine-checked declaration in the MultiViewIdentifiability Lean 4 development (https://github.com/danielhz/MultiViewIdentifiability). To keep the appendix self-contained, the model of Sections 3–4 is recalled briefly before the proofs. Queries are represented semantically—by their answer map together with the invariant that the answer depends only on the relevant projections of the world (its footprint)—so “machine-checked” means the semantic content of each statement is verified, not that a query syntax is reflected into Lean. Every result below is machine-checked with no sorry except those explicitly flagged open. Numbering. Appendix results are numbered independently of the main text; Table 10 gives the correspondence and Table 11 the dependency structure. Full Lean declaration names appear at each result’s ⊢ In Lean pointer. A.1

The model

Attributes, tuples, worlds. Fix a universal schema of attributes with values in a fixed domain. A tuple is a total map from attributes to values, and a world is a set of tuples (a relation over the universal schema). For an attribute set 𝑋 and tuples 𝑠, 𝑡, write 𝑠 =𝑋 𝑡 for agreement on 𝑋 : 𝑠 (𝑎) = 𝑡 (𝑎) for every 𝑎 ∈ 𝑋 . Agreement on 𝑋 is an equivalence relation and is antitone in 𝑋 (agreement on a larger set implies agreement on a smaller one). ⊢ In Lean. Tuple, World, Tuple.AgreeOn in Basic.lean; the equivalence and antitonicity facts are AgreeOn.refl/symm/trans/mono.

24

Ratan Bahadur Thapa and Daniel Hernández

Table 11. Dependency structure of the appendix’s main results.

Result

Depends on

Closure certificate (Thm A.4)

Footprint lifting (Lem A.3) ← determinacy under closure (Lem A.1) Atom footprint (Lem A.6) Views vs. agreement (Lem A.10) Gibbs (Lem A.13), point-mass (Lem A.14), mass concentration (Lem A.15), unique mode (Lem A.16) Entropy facts (Lem A.20), superadditivity (Lem A.21) Closure certificate (Thm A.4)

Atom-wise certificate (Thm A.7) Determinacy char. (Thm A.11) Robust threshold (Thm A.17) Fano’s inequality (Thm A.22) Augmentation (Prop A.24)

Interface laws and legality. The interface imposes cross-world functional dependencies. A dependency 𝑋 → 𝑏 holds across a class of legal worlds W if, for any two legal worlds 𝑤, 𝑤 ′ and any tuples 𝑠 ∈ 𝑤, 𝑡 ∈ 𝑤 ′ , agreement on 𝑋 forces agreement on 𝑏: 𝑠 =𝑋 𝑡 =⇒ 𝑠 (𝑏) = 𝑡 (𝑏). This is strictly stronger than an instance-level dependency: it ties the value of 𝑏 to the value of 𝑋 uniformly across all legal worlds, which is what lets the interface determine attributes rather than merely constrain single instances. A legality structure is a class of legal worlds W together with a set Σ of such laws that all legal worlds satisfy. ⊢ In Lean. FD, FD.HoldsOnPair, LegalityStructure in Basic.lean.

Overlaps, the observable family, observation. The interface exposes a family of observable schemas Γ — closure-augmented designated overlaps (and, more generally, local views or resolver outputs). For e = att(𝑂) +Σ for its closure-augmented schema. Two worlds 𝑤, 𝑤 ′ agree an attribute set 𝑂 we write 𝑂 on a schema 𝑂, written 𝑤 |𝑂 = 𝑤 ′ |𝑂 , when their 𝑂-projections coincide as sets of 𝑂-restricted tuples; the observation of 𝑤 is the family Obs(𝑤) = (𝑤 |𝑂 )𝑂 ∈Γ , and 𝑤, 𝑤 ′ are observationally equivalent (𝑤 ∼ 𝑤 ′ ) when Obs(𝑤) = Obs(𝑤 ′ ), i.e. they agree on every schema in Γ. ⊢ In Lean. World.AgreeOn and ObsEquiv in Basic.lean. In the Lean development the observable family Γ is the interface’s list of designated (closure-augmented) overlaps Interface.augOverlaps; World.AgreeOn O w w’ is set equality of the 𝑂-projections (made precise in §A.6).

Conjunctive queries, footprint, identifiability. A Boolean conjunctive query 𝑄 has a footprint att(𝑄) — the attributes its answer can depend on — and its answer is invariant under agreement on the footprint: if 𝑤 | att(𝑄 ) = 𝑤 ′ | att(𝑄 ) then 𝑄 (𝑤) = 𝑄 (𝑤 ′ ). 𝑄 is identifiable under the interface when observationally equivalent legal worlds always agree on the answer: for all legal 𝑤, 𝑤 ′ :

𝑤 ∼ 𝑤 ′ =⇒ 𝑄 (𝑤) = 𝑄 (𝑤 ′ ).

⊢ In Lean. BoolCQ (with the footprint-faithfulness field) in Basic.lean; Identifiable in Identifiability.lean. As noted above, the footprint-faithfulness field is the semantic invariant of a CQ, taken as the query’s defining property.

A.2

Functional-dependency closure and Armstrong entailment

The closure operator. For an attribute set 𝑋 , its closure 𝑋 Σ+ under Σ is the least set containing 𝑋 and closed under the laws: if 𝑌 → 𝑏 ∈ Σ and 𝑌 ⊆ 𝑋 Σ+ then 𝑏 ∈ 𝑋 Σ+ . The closure is extensive (𝑋 ⊆ 𝑋 Σ+ ), monotone (𝑋 ⊆ 𝑌 ⇒ 𝑋 Σ+ ⊆ 𝑌Σ+ ), and idempotent (𝑋 Σ+ +Σ = 𝑋 Σ+ ).

Identifiability of Relational Queries in Multi-View Pretraining

25

⊢ In Lean. InClosure/fdClosure with fdClosure_extensive, fdClosure_mono, fdClosure_idem_le, fdClosure_idem_ge in FDClosure.lean.

Lemma A.1 (Determinacy under closure). For every attribute set 𝑋 , all legal worlds 𝑤, 𝑤 ′ , and all tuples 𝑠 ∈ 𝑤, 𝑡 ∈ 𝑤 ′ , 𝑠 =𝑋 𝑡 =⇒ 𝑠 =𝑋 Σ+ 𝑡 . Proof. Induct on the construction of 𝑋 Σ+ . If 𝑏 ∈ 𝑋 the conclusion is the hypothesis. If 𝑏 enters the closure through a law 𝑌 → 𝑏 with 𝑌 ⊆ 𝑋 Σ+ , then by the induction hypothesis 𝑠 =𝑌 𝑡; since the law holds across the legal worlds 𝑤, 𝑤 ′ and 𝑠 ∈ 𝑤, 𝑡 ∈ 𝑤 ′ , agreement on 𝑌 forces 𝑠 (𝑏) = 𝑡 (𝑏). Hence 𝑠 =𝑋 Σ+ 𝑡. □ ⊢ In Lean. fd_determinacy in FDClosure.lean (with corollaries fdClosure_propagates_agreement lifting it from a single attribute to the whole closure).

Theorem A.2 (Armstrong soundness and completeness). For attribute sets 𝑋 and a single attribute 𝑎, the law 𝑋 → 𝑎 is entailed by Σ (holds in every legality structure satisfying Σ) iff 𝑎 ∈ 𝑋 Σ+ . Proof. Soundness (𝑎 ∈ 𝑋 Σ+ ⇒ entailed): immediate from Lemma A.1, which already shows 𝑠 =𝑋 𝑡 ⇒ 𝑠 (𝑎) = 𝑡 (𝑎) for any legality structure satisfying Σ. Completeness (entailed ⇒ 𝑎 ∈ 𝑋 Σ+ ): contrapositive. If 𝑎 ∉ 𝑋 Σ+ , build a canonical two-tuple legality structure that satisfies Σ but violates 𝑋 → 𝑎: take two tuples that agree exactly on 𝑋 Σ+ and differ on every attribute outside it. This pair satisfies every law of Σ (a law 𝑌 → 𝑏 with the tuples agreeing on 𝑌 forces 𝑌 ⊆ 𝑋 Σ+ , hence 𝑏 ∈ 𝑋 Σ+ , hence agreement on 𝑏), yet they agree on 𝑋 and disagree on 𝑎 ∉ 𝑋 Σ+ . So 𝑋 → 𝑎 is not entailed. □ ⊢ In Lean. fdClosure_sound and fdClosure_complete in FDClosure.lean; the canonical separating structure is canonStruct.

A.3

The closure certificate

The first sufficient condition for identifiability covers a query whose entire footprint is captured by the closure of a single observable overlap. Lemma A.3 (Footprint lifting). Let 𝑂 be an attribute set and 𝑄 a query with att(𝑄) ⊆ 𝑂 Σ+ . For all legal worlds 𝑤, 𝑤 ′ and tuples 𝑠 ∈ 𝑤, 𝑡 ∈ 𝑤 ′ , if 𝑠 =𝑂 𝑡 then 𝑠 =att(𝑄 ) 𝑡. Proof. By Lemma A.1, 𝑠 =𝑂 𝑡 gives 𝑠 =𝑂 Σ+ 𝑡; antitonicity of agreement and att(𝑄) ⊆ 𝑂 Σ+ give 𝑠 =att(𝑄 ) 𝑡. □ ⊢ In Lean. footprint_lifting in Certificate.lean.

Theorem A.4 (Closure certificate). If att(𝑄) ⊆ 𝑂 Σ+ for some observable overlap 𝑂 ∈ Γ, then 𝑄 is identifiable. Proof. Let 𝑤, 𝑤 ′ be legal with 𝑤 ∼ 𝑤 ′ . Since 𝑂 ∈ Γ, observation equivalence gives 𝑤 |𝑂 = 𝑤 ′ |𝑂 : every tuple of 𝑤 has a tuple of 𝑤 ′ agreeing on 𝑂, and vice versa. Take 𝑠 ∈ 𝑤; pick the matching 𝑡 ∈ 𝑤 ′ with 𝑠 =𝑂 𝑡. By Lemma A.3, 𝑠 =att(𝑄 ) 𝑡. Symmetrically every tuple of 𝑤 ′ has a footprint-agreeing partner in 𝑤. Hence 𝑤 | att(𝑄 ) = 𝑤 ′ | att(𝑄 ) , and footprint faithfulness yields 𝑄 (𝑤) = 𝑄 (𝑤 ′ ). □ ⊢ In Lean. certificate_sufficiency in Certificate.lean. The “fully grounded” variant, where every part of the query is grounded in some overlap, is fully_grounded_identifiable/hasCertificate_identifiable.

26

Ratan Bahadur Thapa and Daniel Hernández

Remark A.5 (The certificate is sufficient, not necessary). The converse fails: an identifiable query need not have its footprint inside any single closure. The Lean development exhibits a machinechecked counterexample — a degenerate single-world interface in which every query is vacuously identifiable while the closure condition fails. Necessity holds only under an additional richness (“closure-separability”) assumption on the legal class, which is not assumed here. ⊢ In Lean. certificate_necessity_false in Certificate.lean.

A.4

The atom-wise closure certificate

The closure certificate of §A.3 asks the whole footprint to sit inside one overlap. The atom-wise certificate is sharper: it covers a query atom by atom, allowing different atoms to be grounded in different overlaps. This is the right granularity, because covering a query’s attributes separately is not enough. A conjunctive query is presented by its relation-atom schemas 𝑈 1, . . . , 𝑈𝑚 together with an answer that depends only on the per-atom projections. Lemma A.6 (Atom footprint). Let 𝑄 have atom schemas 𝑈 1, . . . , 𝑈𝑚 . If legal worlds 𝑤, 𝑤 ′ satisfy 𝑤 |𝑈 𝑗 = 𝑤 ′ |𝑈 𝑗 for every 𝑗, then 𝑄 (𝑤) = 𝑄 (𝑤 ′ ). Proof. The interpretation of every relation symbol occurring in 𝑄 is fixed by the per-atom projections; agreeing on all of them makes the two induced structures interpret 𝑄 identically, so set-semantics evaluation gives the same answer. (In the formalisation this is the query’s defining per-atom faithfulness invariant.) □ ⊢ In Lean. cq_footprint (the field AtomCQ.faithful) in AtomCertificate.lean.

Theorem A.7 (Atom-wise closure certificate). If for every atom 𝑈 𝑗 there is an observable overlap 𝑂 𝑗 ∈ Γ with att(𝑈 𝑗 ) ⊆ 𝑂 𝑗 +Σ , then 𝑄 is identifiable. Proof. Let 𝑤, 𝑤 ′ be legal with 𝑤 ∼ 𝑤 ′ . Fix an atom 𝑈 𝑗 and its overlap 𝑂 𝑗 . Observation equivalence gives 𝑤 |𝑂 𝑗 = 𝑤 ′ |𝑂 𝑗 , and the lifting argument of Lemma A.3 (now with att(𝑈 𝑗 ) ⊆ 𝑂 𝑗 +Σ ) upgrades this to 𝑤 |𝑈 𝑗 = 𝑤 ′ |𝑈 𝑗 : each tuple of 𝑤 has an 𝑂 𝑗 -agreeing partner in 𝑤 ′ , which by Lemma A.1 agrees on 𝑂 𝑗 +Σ ⊇ att(𝑈 𝑗 ), and conversely. As this holds for every atom, Lemma A.6 yields 𝑄 (𝑤) = 𝑄 (𝑤 ′ ). □ ⊢ In Lean. atomwise_certificate in AtomCertificate.lean; the per-overlap lifting step is agreeOn_lift. The single-overlap certificate (Theorem A.4) is the one-atom case. This declaration depends on no axioms.

Theorem A.8 (Union-of-footprint coverage is insufficient). It is not the case that “att(𝑄) ⊆ Ð + 𝑂 ∈Γ att(𝑂) Σ implies 𝑄 identifiable.” That is, covering the footprint by the closure of the union of the overlaps does not suffice. Proof. Counterexample. Take two overlaps {0} and {1}, no laws, and the two worlds 𝑤 𝐴 = {(0, 0), (1, 1)},

𝑤 𝐵 = {(0, 1), (1, 0)}

(pairs written as (attr0, attr1 )). Their projections onto {0} are both {0, 1}, and likewise onto {1}, so 𝑤 𝐴 ∼ 𝑤 𝐵 . The query “some tuple has attr0 = attr1 ” is true on 𝑤 𝐴 (e.g. (0, 0)) and false on 𝑤 𝐵 , although its footprint {0, 1} lies in the closure of the union {0} ∪ {1}. Hence the union condition does not imply identifiability. □ ⊢ In Lean. union_footprint_coverage_insufficient in InterfaceVisible.lean. This refutes the flat union-of-footprint heuristic only; it is consistent with both the atom-wise certificate (the offending atom {0, 1} lies in no single overlap) and the interface-visible fragment below.

Identifiability of Relational Queries in Multi-View Pretraining

A.5

27

The interface-visible fragment

A complementary, exact fragment is obtained by building queries directly from the observation. For each observable schema 𝐻 ∈ Γ introduce a predicate 𝑅𝐻 interpreted on 𝑤 as the projection 𝑤 |𝐻 ; the interface-visible vocabulary Liv consists of these base predicates together with derived predicates, each defined by a conjunctive query over the 𝑅𝐻 . A conjunctive query is interface-visible when every relation symbol it uses belongs to Liv . Theorem A.9 (Interface-visible fragment is identifiable). Every interface-visible conjunctive query is identifiable. Proof. Let 𝑤 ∼ 𝑤 ′ be legal. For each base symbol 𝑅𝐻 , observation equivalence gives 𝑤 |𝐻 = 𝑤 ′ |𝐻 , so the two structures interpret 𝑅𝐻 identically. Each derived symbol is computed by a fixed query over the base symbols, hence is also interpreted identically. Thus the two structures agree on every symbol the query mentions, and set-semantics evaluation gives 𝑄 (𝑤) = 𝑄 (𝑤 ′ ). □ ⊢ In Lean. iv_identifiable (with the query model IVQuery, whose visible field records that the answer is fixed by the observable projections) in Determinacy.lean. Unlike the closure certificate this needs no legality assumption — the symbols are fixed by the observation outright — and it permits joins across overlaps, provided they are expressed over the observable 𝑅𝐻 relations rather than over raw attributes spanning overlaps (the case Theorem A.8 rules out).

A.6

Identifiability is query determinacy

Identifiability coincides exactly with query determinacy (in the sense of Nash–Segoufin–Vianu) by the overlap-projection views. Define the 𝑂-projection view of a world by view𝑂 (𝑤) = { 𝑡 : ∃𝑠 ∈ 𝑤, 𝑠 =𝑂 𝑡 }. Lemma A.10 (Views vs. agreement). view𝑂 (𝑤) = view𝑂 (𝑤 ′ ) if and only if 𝑤 |𝑂 = 𝑤 ′ |𝑂 (the two worlds agree on 𝑂). Proof. (⇐) If the worlds agree on 𝑂 and 𝑡 ∈ view𝑂 (𝑤) via 𝑠 ∈ 𝑤 with 𝑠 =𝑂 𝑡, then 𝑠 has an 𝑂-agreeing partner 𝑢 ∈ 𝑤 ′ , and 𝑢 =𝑂 𝑡 by transitivity, so 𝑡 ∈ view𝑂 (𝑤 ′ ); symmetrically. (⇒) For 𝑠 ∈ 𝑤 we have 𝑠 ∈ view𝑂 (𝑤) (reflexivity), hence 𝑠 ∈ view𝑂 (𝑤 ′ ), giving a partner 𝑢 ∈ 𝑤 ′ with 𝑢 =𝑂 𝑠; symmetrically. Thus the worlds agree on 𝑂. □ ⊢ In Lean. projView and projView_eq_iff_agreeOn in Determinacy.lean.

Theorem A.11 (Determinacy characterisation). A query is identifiable under the interface if and only if it is determined, in the determinacy sense, by the overlap-projection views: every two legal worlds with equal views agree on the answer. Proof. By Lemma A.10, equality of all overlap-projection views is the same relation as observation equivalence. Identifiability is precisely “observationally equivalent legal worlds agree on the answer,” which is exactly determinacy by those views. □ ⊢ In Lean. DeterminedBy and identifiable_iff_determined in Determinacy.lean.

A.7

The minimax error floor

Identifiability is also exactly the line below which no observation-based predictor can do better than chance.

28

Ratan Bahadur Thapa and Daniel Hernández

Theorem A.12 (Minimax floor). Let 𝑄 be non-identifiable, witnessed by legal 𝑤 ∼ 𝑤 ′ with 𝑄 (𝑤) ≠ 𝑄 (𝑤 ′ ), and let 𝑓 be any classifier that depends only on the observation (so 𝑓 (𝑤) = 𝑓 (𝑤 ′ ) whenever 𝑤 ∼ 𝑤 ′ ). Then 𝑓 misclassifies at least one of 𝑤, 𝑤 ′ : there is a legal world on which 𝑓 ’s prediction is wrong. Proof. Because 𝑓 is observation-based and 𝑤 ∼ 𝑤 ′ , we have 𝑓 (𝑤) = 𝑓 (𝑤 ′ ). But 𝑄 (𝑤) ≠ 𝑄 (𝑤 ′ ), so 𝑓 ’s single shared prediction cannot match both answers; it is wrong on at least one of the two legal worlds. Averaged over the witness pair this is an error rate of at least 12 . □ ⊢ In Lean. minimax_error_floor in Minimax.lean (with not_perfect_balanced_accuracy); “observationbased” is ObsDetermined.

A.8

Robustness: a zero-discrepancy threshold

The certificates are exact: zero overlap loss forces exact agreement on certified queries. We show a quantitative refinement — a small loss already forces exact agreement — when prediction quality is measured by Jensen–Shannon divergence. All divergences use natural logarithms (𝜅 = 1). For finite mass functions 𝑝, 𝑞, the Kullback–Leibler and Jensen–Shannon divergences are ∑︁ 𝑝 (𝑎) 𝑝+𝑞 KL(𝑝 ∥ 𝑞) = 𝑝 (𝑎) log , JS(𝑝 ∥ 𝑞) = 12 KL(𝑝 ∥ 𝑚) + 12 KL(𝑞 ∥ 𝑚), 𝑚 = 2 . 𝑞(𝑎) 𝑎 Write 𝛿𝑥 for the point mass at 𝑥. Lemma A.13 (Gibbs’ inequality). For mass functions 𝑝, 𝑞 with 𝑞(𝑎) > 0 whenever 𝑝 (𝑎) ≠ 0, KL(𝑝 ∥ 𝑞) ≥ 0.
𝑞 (𝑎) 𝑞 (𝑎) Proof. Using log 𝑧 ≤ 𝑧 − 1 for 𝑧 > 0, for each 𝑎 with 𝑝 (𝑎) > 0, 𝑝 (𝑎) log 𝑝 (𝑎) ≤ 𝑝 (𝑎) 𝑝 (𝑎) − 1 = 𝑞(𝑎) − 𝑝 (𝑎); the inequality also holds trivially when 𝑝 (𝑎) = 0 (left side 0 ≤ 𝑞(𝑎)). Summing, Í Í 𝑞 (𝑎) 𝑎 𝑝 (𝑎) log 𝑝 (𝑎) ≤ 𝑎 (𝑞(𝑎) − 𝑝 (𝑎)) = 1 − 1 = 0, and KL(𝑝 ∥ 𝑞) is the negation of the left-hand side, hence ≥ 0. □ ⊢ In Lean. kl_nonneg in Information.lean.

Lemma A.14 (Point-mass lower bound). For a mass function 𝑝 and any 𝑥, JS(𝛿𝑥 ∥ 𝑝) ≥ 12 log 1+𝑝2(𝑥 ) . 1+𝑝 (𝑥 )

1 2 Proof. With 𝑚 = 12 (𝛿𝑥 + 𝑝) we have 𝑚(𝑥) = 2 , and KL(𝛿𝑥 ∥ 𝑚) = log 𝑚 (𝑥 ) = log 1+𝑝 (𝑥 ) . By Lemma A.13, KL(𝑝 ∥ 𝑚) ≥ 0, so JS(𝛿𝑥 ∥ 𝑝) ≥ 21 KL(𝛿𝑥 ∥ 𝑚) = 12 log 1+𝑝2(𝑥 ) . □

⊢ In Lean. kl_dirac_mix and jsdiv_dirac_lower in Information.lean.

Lemma A.15 (Mass concentration). If JS(𝛿𝑥 ∥ 𝑝) ≤ 𝛾 with 𝛾 < 81 , then 𝑝 (𝑥) > 12 . Proof. By Lemma A.14, 12 log 1+𝑝2(𝑥 ) ≤ 𝛾, so 1+𝑝2(𝑥 ) ≤ 𝑒 2𝛾 and 1 +𝑝 (𝑥) ≥ 2𝑒 −2𝛾 . Using 𝑒 −𝑡 ≥ 1 −𝑡, √ 1 + 𝑝 (𝑥) ≥ 2(1 − 2𝛾), i.e. 𝑝 (𝑥) ≥ 1 − 4𝛾. As 𝛾 < 18 , 𝑝 (𝑥) > 12 . (Avoiding the usual · Pinsker step keeps the bound elementary.) □ ⊢ In Lean. px_gt_half in Information.lean.

Lemma A.16 (Unique majority / unique mode). A finite mass function has at most one outcome of mass > 21 . Consequently, if JS(𝛿𝑥 ∥ 𝑝) ≤ 𝛾 and JS(𝛿𝑥 ′ ∥ 𝑝) ≤ 𝛾 with 𝛾 < 18 , then 𝑥 = 𝑥 ′ . Í Proof. If 𝑥 ≠ 𝑥 ′ both had mass > 12 , then 𝑝 (𝑥) + 𝑝 (𝑥 ′ ) > 1, contradicting 𝑎 𝑝 (𝑎) = 1. The second statement applies Lemma A.15 to 𝑥 and 𝑥 ′ . □

Identifiability of Relational Queries in Multi-View Pretraining

29

⊢ In Lean. unique_majority and js_mode in Information.lean.

Theorem A.17 (Robust threshold). Suppose the overlap projection proj(𝑤) of a world (its value on a e covers the query’s footprint, in the sense that proj(𝑤) = proj(𝑤 ′ ) ⇒ closure-augmented overlap 𝑂) ′ 𝑄 (𝑤) = 𝑄 (𝑤 ), and that the overlap loss is anchored to a fixed reference 𝑝𝑂 : 𝜂·JS(𝛿 proj(𝑤 ) ∥ 𝑝𝑂 ) ≤ ℓ (𝑤) with 𝜂 > 0. Let 𝜀 0 = 𝜂/8. Then for every 𝜀 < 𝜀 0 , 𝑄 is (𝜀, 0)-identifiable: any two worlds with loss ≤ 𝜀 give the same answer. Proof. If ℓ (𝑤), ℓ (𝑤 ′ ) ≤ 𝜀 < 𝜂/8, anchoring gives JS(𝛿 proj(𝑤 ) ∥ 𝑝𝑂 ) ≤ 𝜀/𝜂 < 81 and likewise for ′ 𝑤 . By Lemma A.16, proj(𝑤) = proj(𝑤 ′ ), and footprint coverage yields 𝑄 (𝑤) = 𝑄 (𝑤 ′ ). □ ⊢ In Lean. robust_threshold in Information.lean. The footprint-coverage hypothesis is the abstract e (Theorem A.4); the anchoring hypothesis models the overlap-anchored loss term. counterpart of “att(𝑄) ⊆ 𝑂”

A.9

Information-theoretic lower bounds

Capacity and outcome bounds. Let 𝑚𝑄 be the outcome multiplicity of 𝑄 — the number of distinct answers it realises over the legal worlds. Theorem A.18 (Outcome lower bound). Any predictor that reads the observation, stores it in a representation with at most 2𝑘 states, and answers 𝑄 correctly on every legal world satisfies 𝑚𝑄 ≤ 2𝑘 (equivalently 𝑘 ≥ log2 𝑚𝑄 ). Proof. Write the predictor as a representation map rep into a set 𝑅 with |𝑅| ≤ 2𝑘 , followed by a decoder ans : 𝑅 → answers, correct in the sense ans(rep(𝑤)) = 𝑄 (𝑤) for every legal 𝑤. Then the realised answers are {𝑄 (𝑤)} = {ans(rep(𝑤))} ⊆ range(ans), a set of size ≤ |𝑅| ≤ 2𝑘 . Hence 𝑚𝑄 ≤ 2𝑘 . □ ⊢ In Lean. outcome_lower_bound in OutcomeBound.lean.

Theorem A.19 (Capacity error bound). Index the 𝑚𝑄 distinct outcomes by a set on which the true answer is injective. Any ≤ 2𝑘 -state predictor errs on at least 𝑚𝑄 − 2𝑘 of them; under a uniform prior its error satisfies 𝑃𝑒 ≥ 1 − 2𝑘 /𝑚𝑄 . Proof. On the set of correctly-answered outcomes the representation map is injective (two correctly answered, distinct-outcome worlds with the same representation would force equal answers, hence equal outcomes), so at most |𝑅| ≤ 2𝑘 are correct; the remaining ≥ 𝑚𝑄 − 2𝑘 are errors. Dividing by 𝑚𝑄 gives 𝑃𝑒 ≥ 1 − 2𝑘 /𝑚𝑄 . □ ⊢ In Lean. capacity_error_bound and capacity_error_rate in OutcomeBound.lean.

Fano’s inequality. Write nml(𝑥) = −𝑥 log 𝑥 and entropy 𝐻 (𝑝) = entropy is 𝐻 b (𝑝) = nml(𝑝) + nml(1 − 𝑝).

𝑎 nml(𝑝 (𝑎)) (nats); the binary

Í

Lemma A.20 (Basic entropy facts). For a mass function on an 𝑀-element set: 𝐻 ≥ 0; 𝐻 (uniform) = log 𝑀; and 𝐻 (𝑝) ≤ log 𝑀 (maximum entropy). Proof. nml ≥ 0 on [0, 1], so 𝐻 ≥ 0. For the uniform law each term is nml(1/𝑀) =

1 𝑀 log 𝑀, summing to log 𝑀. Maximum entropy is KL(𝑝 ∥ uniform) ≥ 0 (Lemma A.13): expanding,

KL(𝑝 ∥ uniform) = log 𝑀 − 𝐻 (𝑝).

⊢ In Lean. entropy_nonneg, entropy_uniform, entropy_le_log_card in Entropy.lean.

□

30

Ratan Bahadur Thapa and Daniel Hernández

Lemma A.21 (Superadditivity and the max-entropy-with-total bound). nml is superadditive on nonnegatives: nml(𝑥 +𝑦) ≤ nml(𝑥) + nml(𝑦). Hence joint entropy dominates a marginal, 𝐻 (marginal) ≤ Í 𝐻 (joint); and for nonnegatives 𝑎 1, . . . , 𝑎 𝑁 with sum 𝑆, 𝑖 nml(𝑎𝑖 ) ≤ nml(𝑆) + 𝑆 log 𝑁 . Proof. For 𝑥, 𝑦 > 0, since 0 < 𝑥, 𝑦 ≤ 𝑥 + 𝑦 and log is increasing, 𝑥 log 𝑥 + 𝑦 log 𝑦 ≤ 𝑥 log(𝑥 + 𝑦) + 𝑦 log(𝑥 + 𝑦) = (𝑥 + 𝑦) log(𝑥 + 𝑦), which is nml(𝑥 + 𝑦) ≤ nml(𝑥) + nml(𝑦) (boundary cases 𝑥 = 0 or 𝑦 = 0 are immediate). Summing row-wise gives 𝐻 (marginal) ≤ 𝐻 (joint). The Í last bound is Jensen for the concave nml with uniform weights: 𝑁1 𝑖 nml(𝑎𝑖 ) ≤ nml( 𝑁𝑆 ), and 𝑁 nml( 𝑁𝑆 ) = nml(𝑆) + 𝑆 log 𝑁 . □ ⊢ In Lean. negMulLog_add_le, entropy_marginalX_le/condEntropy_nonneg, negMulLog_sum_le_total in Entropy.lean.

Theorem A.22 (Fano’s inequality). Let 𝑞 be a mass function on an 𝑀-element set with a distinguished outcome 𝑥 0 , and write 𝑝 = 1−𝑞(𝑥 0 ) for the residual (“error”) mass. Then 𝐻 (𝑞) ≤ 𝐻 b (𝑝) +𝑝 log(𝑀 −1). Í Í Proof. Split off 𝑥 0 : 𝐻 (𝑞) = nml(𝑞(𝑥 0 )) + 𝑎≠𝑥 0 nml(𝑞(𝑎)). The residual massÍis 𝑎≠𝑥 0 𝑞(𝑎) = 𝑝 over 𝑀 − 1 outcomes, so by the max-entropy-with-total bound (Lemma A.21), 𝑎≠𝑥 0 nml(𝑞(𝑎)) ≤ nml(𝑝) + 𝑝 log(𝑀 − 1). Therefore 𝐻 (𝑞) ≤ nml(𝑞(𝑥 0 )) + nml(𝑝) + 𝑝 log(𝑀 − 1) = nml(1 − 𝑝) + nml(𝑝) + 𝑝 log(𝑀 − 1) = 𝐻 b (𝑝) + 𝑝 log(𝑀 − 1). □ ⊢ In Lean. entropy_le_fano (with binEntropy_eq_negMulLog) in Entropy.lean.

Remark A.23 (Distributional predictor corollary — open). The verbatim entropic predictor bound 𝑃𝑒 ≥ 1 − 𝐼 (𝑄;Obs)+1 log2 𝑚𝑄 , the conditional/averaged lift of Theorem A.22 over a joint distribution, is not formalised. Its operational content (interface capacity forces an error floor) is the proved Theorem A.19. A.10

Minimum augmentation

When a query is not certified, one seeks the smallest augmentation — extra attributes added to an overlap — whose closure covers the footprint. Say aug is an augmentation certificate for 𝑄 on overlap 𝑂 when att(𝑄) ⊆ 𝑂 ∪ aug +Σ . Proposition A.24 (Structure of augmentation certificates). Augmentation certificates are monotone (if aug 1 ⊆ aug 2 certifies, so does aug 2 ); certification depends only on the closure 𝑂 ∪ aug +Σ ; and aug certifies 𝑄 iff it covers the residual {𝑎 ∈ att(𝑄) : 𝑎 ∉ 𝑂 Σ+ }. Moreover, adding aug to the interface (making 𝑂 ∪ aug an observable overlap) renders 𝑄 identifiable under the augmented interface. Proof. Monotonicity and closure-dependence are immediate from monotonicity and idempotence of ·+Σ . The residual characterisation splits att(𝑄) into the part already in 𝑂 Σ+ and the rest. Identifiability under the augmented interface is Theorem A.4 applied to the overlap 𝑂 ∪ aug in the augmented interface. □ ⊢ In Lean. augCertificate_mono, augCertificate_closure_char, augCertificate_iff_covers_residual, aug_closure_equiv, augCertificate_identifiable_augmented in MinAug.lean.

Remark A.25 (Closure-uniqueness of minimum augmentations is false). Two minimum-cardinality augmentations need not have the same closure (minimum set covers are not unique). The development records a machine-checked counterexample. ⊢ In Lean. minAug_closure_unique_false in MinAug.lean.

Identifiability of Relational Queries in Multi-View Pretraining

31

Table 12. Datasets: source, size, designated overlap 𝑂, and interface laws Σ. Attribute indices follow the per-dataset schemas of Section 6.

Dataset

Source / size

Synthetic

generated; all 𝑑 𝑛 single-

BibInteg CrossKG-DBLP Amazon-Google Fodors-Zagat WDC-Product

Overlap 𝑂

random per inrow worlds (𝑛=5) stance OpenAlex API; 9,992 pa- {title, author, year} pers DBLP × OpenAlex; {title, author, year} 11,800 papers Magellan; 1,046 pairs matched-pair identity Magellan; 110 pairs matched-pair + segment WDC corpus; schema {brand, model} only

Interface laws Σ random FDs (exact ground truth by enumeration) 𝑂 → venue, 𝑂 → doi, 𝑂 → n_authors, {year}→ decade 𝑂 → doi none across price none across cuisine {brand,model}→ sised attrs

synthe-

Remark A.26 (Greedy approximation and hardness — open). Selecting a minimum augmentation reduces to Set Cover, so the greedy algorithm enjoys the standard 𝐻𝑘 ≤ 1 + ln 𝑘 approximation guarantee and the decision problem is NP-complete. These two facts are not machine-checked: they require a formal Set Cover/greedy development and an NP-completeness framework outside the present scope. This is the single remaining sorry (greedy_approx_ratio) together with the placeholder minAug_NP_hard_from_SetCover. Reproducing the proofs The toolchain is pinned by lean-toolchain (Lean 4.30.0) and the dependencies by lake-manifest.json (Mathlib v4.30.0); from the repository root, run lake exe cache get then lake build. A successful build reports only the one documented sorry (greedy_approx_ratio) and unused-variable warnings; the declaration names cited above are checked against the sources in CI. B

EXPERIMENTAL DETAILS

This appendix expands Section 6 with dataset construction, predictor architectures and hyperparameters, the experimental protocol, and the per-architecture error-floor numbers behind the figures. Experiment code is at https://github.com/danielhz/query-identifiability. B.1

Datasets

Table 12 summarises how each dataset is built. The synthetic benchmark supports the exact certificate/oracle comparison (RQ1) by exhaustive enumeration; the four real-record datasets validate the interface-law model on genuine integration data; WDC-Product is a schema-design illustration whose query-critical attributes are synthesised to realise a prescribed certified/uncertified split. B.2

Predictor architectures and training

Six predictors span the structure-agnostic-to-structure-exploiting spectrum plus two baselines; all consume the same per-overlap feature vector (the concatenated closure-augmented overlap marginals) and are trained identically (Table 13).

32

Ratan Bahadur Thapa and Daniel Hernández

Table 13. Training configuration (shared across all learnable architectures).

Setting

Value

Loss / optimiser Epochs (max) Learning rate Batch size MLP width Hardware Software

binary cross-entropy / Adam 300, early stopping (patience 30) on val. loss 10−3 ; weight decay 10−5 256; best-val checkpoint restored 128 (swept over {64, 256, 1024}), 2 hidden layers NVIDIA A40 (48 GB), 128-core CPU PyTorch 2.3.0 / CUDA 12.1, PyG 2.5.0, Python 3.11

• MLP: two hidden layers, ReLU, dropout; a flat feed-forward network over the feature vector. • SetTransformer (ST): each overlap’s marginal is linearly projected to a shared dimension, followed by multi-head self-attention blocks and a pooled read-out (cross-overlap attention). • GNN-OG: message passing on the overlap graph; each attribute’s marginal is recovered from its overlap’s probability tensor and propagated along overlap edges before pooling. • Closure-Aware (CA): when the query is certified it reads the answer directly from the Σ-closure of the overlap projection (no learned inference); otherwise it falls back to GNN-OG. • VanillaOv: logistic regression on the raw overlap feature vector (no hidden layers), testing whether linear expressivity suffices. • MajVote: constant majority-class predictor. B.3

Protocol

Certificate exactness (RQ1). A benchmark of 841 instances (sampling 200 random 5-attribute schemas with up to four FDs and five single-atom Boolean CQs each, split evenly certified/non-certified) is checked by CheckCert against an exhaustive oracle that enumerates all 𝑑 𝑛 single-row worlds, groups them by observation, and tests answer agreement; for non-certified queries it returns an explicit witness pair. Confirmatory ML. Worlds are drawn from the resolver model with 𝑚 ∈ {10, 30, 50} tuples consistent with Σ; training sizes 𝑁 ∈ {103, 5×103, 5×104 } (validation/test scaled proportionally); 10 certified and 10 non-certified single-atom Boolean CQs per configuration; three seeds (0, 1, 2). Minimum augmentation (RQ3). 500 random trials per (𝑛, |Σ|) with 𝑛 ∈ {4, 6}, footprint ≈ 0.6𝑛, and atom-obligation counts |B𝑄 | ∈ {1, 2, 3, 4}. Scalability (RQ4). |V | and |Σ| each swept over {10, 50, 100, 250, 500, 1000}. B.4

Detailed error-floor results

Table 14 reports the per-architecture balanced accuracy underlying Figure 3 (𝑚=10, aggregated over 𝑁 and three seeds). Structure-exploiting architectures separate certified from non-certified queries; the flat and constant baselines sit at the 1/2 floor on both. On non-certified queries every architecture stays within noise of 1/2 for all 𝑚 ∈ {10, 30, 50} (maximum observed deviation 0.02), the empirical counterpart of Theorem 4.7.

Identifiability of Relational Queries in Multi-View Pretraining

33

Table 14. Balanced accuracy (mean ± std over queries, 𝑁 , and seeds) at 𝑚=10.

Architecture

Certified

Non-certified

MLP SetTransf. GNN-OG CA VanillaOv MajVote

0.97 ± 0.12 1.00 ± 0.00 0.83 ± 0.24 0.89 ± 0.21 0.50 ± 0.00 0.50 ± 0.00

0.51 ± 0.02 0.52 ± 0.03 0.52 ± 0.03 0.50 ± 0.00 0.50 ± 0.00 0.50 ± 0.00

Related documents

• TrajectoryDB: A New Database for Agent Trajectories#673620
• Preserving contextual information in cultural heritage metadata through multidimensional knowledge graphs#673621
• X-DigCheck: Co-Evolving Application Profiles and Knowledge Graphs, Demonstrated on the RTI Documentation of Rupe Magna#673622
• Open Tabular Insight Extraction: Where Do We Stand, and Where Should We Go?#673623
• Protocol effects on feature-based hardware-Trojan detection across Trust-Hub families#673624