lin-0210

17.1 A database is a diagram

Let \(\mathcal S\) be a category presenting a database schema. A database instance is a functor

\[ I:\mathcal S\longrightarrow \mathbf{Set} \]

that assigns rows to entity types and functions to declared foreign keys [ Spivak , 2012 ] . In the controlled construction,

\[ R\subseteq A\times B,\qquad S\subseteq B\times C,\qquad Q\subseteq A\times C. \]

The higher-order evidence is the set of join witnesses

\[ J = \{ (a,b,c):(a,b)\in R,\ (b,c)\in S,\ (a,c)\in Q\} . \]

A witness records which three typed facts cohere. It is not simply another pairwise similarity.

Diagram illustrating 17.1 A database is a diagram.

Proposition 17.1 Projection non-identifiability

Let \(P\) map database instances to weighted graphs on \(A\). If \(P(I_0)=P(I_1)\) while \(I_0\) and \(I_1\) have different join-witness structure, every deterministic embedding that factors through \(P\) returns the same output on both. Under equal priors, no evaluator of that output can identify the generating join structure with accuracy above \(1/2\).

Proof ▼

For an embedding \(E\), equality of \(P(I_0)\) and \(P(I_1)\) implies equality of \(E\circ P\). Conditioning a randomized method on its seed gives the same argument.

This is not a criticism of Uniform Manifold Approximation and Projection (UMAP) [ McInnes et al. , 2018 ] ; it applies to every method given the same lossy projection. A triangle-feature UMAP baseline is therefore necessary: it separates access to higher-order information from the value of relational descent.