One Runtime, Many Semantics: The Typed Carrier Algebra Behind UQA Engine

"Unified" Is a Semantic Claim

A modern application may need one question to cross several data paradigms. A relational predicate narrows the corpus, full-text search finds lexical evidence, vector search supplies semantic neighbors, a graph traversal adds structural context, and ranking chooses the final rows.

The usual architecture assigns each step to a different system. The application then becomes an accidental query engine: it maps identities between stores, moves candidate sets across process boundaries, reconciles transaction states, normalizes unrelated scores, and chooses an execution order without global statistics.

UQA Engine takes the opposite approach. It is an embeddable Rust database engine that brings PostgreSQL-oriented SQL, text retrieval, vector retrieval, graph queries, and probabilistic ranking into one planning and execution boundary. The mathematical foundation is developed in A Typed Carrier Algebra for Unified Query Execution, a manuscript that consolidates and revises the earlier UQA, graph-extension, and Bayesian hybrid-search work.

The revision matters. It replaces a tempting but overly broad idea—one universal posting-list representation—with a typed family of carriers. The new claim is both narrower and stronger:

$$\text{unification} \neq \text{one container for every intermediate value},$$ $$\text{unification} = \text{typed composition} + \text{one planning and execution calculus}.$$

Different values may travel through one runtime without pretending to obey the same laws.

Why One Universal Posting List Breaks

Let $U$ be a finite universe of document identifiers and let $\Pi$ be a payload domain. A payload-bearing posting list can be modeled as a finite partial map:

$$P:U\rightharpoonup\Pi.$$

Its support forgets everything except membership:

$$\operatorname{supp}(P) = \{d\in U\mid P(d)\text{ is defined}\}.$$

If $\operatorname{lift}(D)$ assigns a default payload to every identifier in a document set $D$, one direction round-trips exactly:

$$\operatorname{supp}(\operatorname{lift}(D))=D.$$

The reverse direction generally does not:

$$\operatorname{lift}(\operatorname{supp}(P))\neq P.$$

Projecting a posting list to support discards term positions, scores, field values, score bounds, and any other decoration. Two postings can therefore have identical support and different observable meaning.

This immediately invalidates a global Boolean simplifier. Suppose a posting merge adds scores when the same document occurs on both sides. For a document with score $0.8$,

$$P\mathbin{\widetilde\cup}P\neq P$$

because the merged score is $1.6$. If colliding fields prefer the right operand, the merge is not commutative either. Support still behaves like a set, but the complete posting value does not.

The same loss appears in other domains. A SQL bag loses duplicate multiplicity when converted to a set. A join loses tuple identity when reduced to one document ID. A graph match loses vertices, edges, paths, and graph name when reduced to support. A ranked result loses order when converted to an unordered posting list. A single physical container can hold these values, but it cannot make their distinctions disappear.

The Carrier Family

The paper assigns each observable structure its own carrier—a domain of values together with the laws valid for those values.

This is not a class hierarchy in which one carrier silently substitutes for another. Composition is legal only when an operator's output carrier matches the next operator's input carrier, or when an explicit adapter records the conversion and its information loss.

That distinction produces a useful division of labor:

• DocSet owns finite Boolean algebra: union, intersection, difference, and complement relative to an explicit universe.
• Relation<K> owns pointwise addition and multiplication supplied by semiring $K$.
• PostingList owns payload collision policies without inheriting Boolean idempotence.
• RankedView owns score order, deterministic tie-breaking, and top-$k$ selection without changing posting storage order.
• SQL execution retains bag, NULL, and ordering semantics.
• Join and graph results retain the identities and context that later operators still need.

The result is not less unified. It is a system in which every composition states what it preserves.

Laws Belong to Observations

An optimizer never preserves an abstract value in every imaginable sense. It preserves what the parent of a rewritten expression can observe.

Let $\operatorname{obs}_C$ denote the observation exposed at carrier $C$. One observation refines another when the coarser result can be recovered from the finer result. For the retrieval carriers, part of the refinement order is:

$$\operatorname{obs}_{\mathsf{support}} \sqsubseteq \operatorname{obs}_{\mathsf{payload}} \sqsubseteq \operatorname{obs}_{\mathsf{ranked}}, \qquad \operatorname{obs}_{\mathsf{support}} \sqsubseteq \operatorname{obs}_{\mathsf{graph}}.$$

The order is partial, not linear. SQL multiplicity and graph-match context are incomparable: neither can reconstruct the other.

This gives a precise rewrite rule. If expressions $e_1$ and $e_2$ are equivalent under carrier observation $C$, and their surrounding context factors only through that observation, replacing one with the other is sound:

$$e_1\equiv_C e_2 \;\land\; \mathcal K=\overline{\mathcal K}\circ\operatorname{obs}_C \quad\Longrightarrow\quad \mathcal K[e_1]\equiv\mathcal K[e_2].$$

In the Rust implementation, this principle is visible rather than aspirational. OperatorTree::is_membership_only exhaustively classifies operator variants. Algebraic simplification removes duplicate terms or applies absorption only when every affected subtree produces default payloads. A newly added scored or decorated operator is ineligible until its payload behavior has been reviewed.

Rejecting a safe rewrite loses an optimization. Accepting an unsafe rewrite changes the answer. The implementation deliberately prefers the former.

Ranking Cannot Be Smuggled into Set Algebra

Top-$k$ is deterministic, but it is not a Boolean homomorphism. Consider two scored postings and a merge that adds scores on collision:

$$A=\{d_1\mapsto3,\ d_2\mapsto2\}, \qquad B=\{d_2\mapsto2\}.$$

Merging first makes $d_2$ the winner with score $4$:

$$\operatorname{top}_1(A\mathbin{\widetilde\cup}B)=\{d_2\}.$$

Truncating each child first discards the contribution from $A$ that would have raised $d_2$ above $d_1$:

$$\operatorname{top}_1\!\left( \operatorname{top}_1(A) \mathbin{\widetilde\cup} \operatorname{top}_1(B) \right) =\{d_1\}.$$

This is why UQA Engine does not push a text top-$k$ through Boolean or fusion parents merely because doing so looks faster. WAND and Block-Max WAND are instead treated as physical refinements: they may skip work only when admissible upper bounds prove that the exact final ranking cannot change. A scorer or field-statistics change invalidates persisted bounds; execution falls back to an exact path rather than trusting stale metadata.

Probability Has Types Too

Search systems routinely combine numbers that share an f64 representation but not a meaning. A raw BM25 score, a likelihood-ratio contribution, a relevance prior, and a posterior probability admit different operations. UQA Engine represents them with different Rust types:

• RawBm25Score
• EvidenceLogit
• PriorLogit
• PosteriorProbability

The exact fusion rule begins with signed, prior-free evidence. Let $R\in\{0,1\}$ denote relevance, and suppose signals $x_1,\ldots,x_n$ are conditionally independent in both relevance classes. Each signal contributes a log likelihood ratio:

$$e_i = \log\frac{p(x_i\mid R=1)}{p(x_i\mid R=0)}.$$

With relevance prior $\pi$, the posterior is:

$$p(R=1\mid x_1,\ldots,x_n) = \sigma\!\left( \operatorname{logit}(\pi)+\sum_{i=1}^{n}e_i \right).$$

Three engineering rules fall straight out of the equation: zero evidence is neutral, negative evidence must remain negative, and the prior enters exactly once. Adding posterior logits that already contain the same prior would count it repeatedly.

The code keeps this exact operator separate from robust positive-evidence pooling. The latter may use non-negative gates, confidence scaling, or adaptive weights because those choices can be useful for ranking, but it is explicitly a heuristic rather than an exact posterior theorem. The SQL surface reflects the distinction: fuse_bayesian_evidence and fuse_log_odds select exact single-prior fusion, while pool_positive_evidence selects the robust heuristic.

For a supported same-relation conjunction of text and vector retrieval, the optimizer can infer the exact fusion boundary automatically. Raw text matching is calibrated there, vector evidence remains prior-free, ordinary relational conjuncts remain strict filters, and the resolved corpus prior is applied once.

Graph Results Remain Graph Results

A graph traversal does produce a set of matching identities, but that support is not the whole result. UQA Engine models a graph posting as:

$$GP=(P,\gamma), \qquad \operatorname{dom}(\gamma)\subseteq\operatorname{supp}(P),$$

where $P$ is the ordinary posting payload and $\gamma(d)$ retains graph name, matched vertices, matched edges, and an optional score override. The invariant prevents graph metadata from referring to a document absent from the posting support.

Overlapping graph results use explicit subgraph policies—union, intersection, prefer left, or prefer right—and unresolved graph-name conflicts remain errors. Generic posting-field precedence is not allowed to decide graph semantics by accident.

When graph output must cross a posting-oriented boundary, a versioned $\Phi$ codec encodes the graph side map into reserved payload fields while preserving the base payload and support. The important claim is deliberately constrained:

$$\Phi^{-1}(\Phi(g))=g$$

for valid graph-posting values under the codec contract. This is a lossless representation change for one typed carrier, not an isomorphism between arbitrary graphs and document sets.

Regular path queries remain graph-native as well. A path expression compiles to an automaton $A_R$, and traversal becomes reachability in the product graph $G\times A_R$. The result may later join relational rows, but the traversal does not have to forget its graph semantics to participate in the shared runtime.

How the Algebra Appears in the Rust Engine

The current UQA Engine 0.1.6 workspace contains 25 uqa-* crates, but that modularity is an ownership boundary rather than a collection of independent query engines. Every compiled statement follows one top-level route:

UnifiedPlan is an exhaustive sum of query and command plans. A query block chooses among a relational row path, a specialized OperatorTree path, and a hybrid posting-plus-residual path. Specialized execution then returns another typed sum: ordinary PostingList, GraphPostingList, or tuple-preserving GeneralizedPostingList.

The theory maps to concrete review and execution boundaries:

Around this core, dedicated crates own analysis, storage, scoring, fusion, graph processing, joins, planning, physical execution, the PostgreSQL-oriented frontend, the engine facade, CLI, HTTP client, and Rust, Python, Node.js, and browser WASM bindings. The system can start in memory, persist through SQLite or redb, or send the same SQL shapes to a local or Cloud UQA data plane.

A Query Through the Boundary

The repository's runnable unified-search example creates one paper table, a GIN text index, a vector index, a citation graph, and a user-defined function in one engine session. Its hybrid query is ordinary SQL:

SELECT id, title, _score
FROM papers
WHERE text_match(abstract, 'retrieval ranking')
  AND knn_match(embedding, ARRAY[1.0, 0.0, 0.0], 4)
ORDER BY _score DESC, id ASC
LIMIT 4;

The conjunction is not evaluated as two unrelated service calls. The planner recognizes compatible text and vector signals on the same relation, lowers them into the operator algebra, applies the exact fusion contract, and returns ranked support to the relational boundary for projection and deterministic ordering.

The same example continues from ranked rows into a citation traversal without translating identities between systems:

SELECT p.id, p.title, p.venue, p.year
FROM papers AS p
JOIN cypher('citations', $$
    MATCH (:Paper {paper_id: 3})-[:CITES]->(cited:Paper)
    RETURN cited.paper_id
$$) AS cited(id int)
  ON p.id = cited.id
ORDER BY p.year DESC, p.id ASC;

Here cypher(...) is a typed table source. Its output joins ordinary SQL rows because both sides retain real identities and schemas. No application-side candidate copying or ID reconciliation is required.

To run the complete scenario:

git clone https://github.com/cognica-io/uqa-engine.git
cd uqa-engine
cargo run -p example-unified-search --locked

The current repository requires Rust 1.90 or newer. For this article, we ran the example from the 0.1.6 checkout and exercised lexical and Bayesian scoring, KNN, automatic exact fusion, robust pooling, typed operator joins, a host function, Cypher composition, and a final cross-paradigm query in one session.

Evidence Is Typed Alongside the Data

The paper is careful not to turn algebra into performance marketing, and the project follows the same separation of claims.

This discipline prevents one successful test from being used as evidence for a different property. A calibrated score does not prove ANN recall. ANN recall does not prove transactional durability. A benchmark does not prove an algebraic rewrite. Each claim has its own oracle.

The Boundaries Are Part of the Design

UQA Engine is broad, but neither the paper nor the project claims more than the evidence supports.

• The algebra is defined over finite, pinned snapshots; distributed execution is outside the current core.
• The SQL surface is PostgreSQL-oriented, not a claim that an embedded engine is a complete PostgreSQL server clone.
• IVF and HNSW are approximate by design; their quality depends on corpus and parameters.
• A value in $[0,1]$ is not automatically calibrated. Model and candidate-pool changes require renewed evaluation.
• General graph-pattern matching and unrestricted path enumeration retain their inherent complexity.
• Version 0.1.6 is under active development, so public APIs and storage formats may evolve before a stable release.

These are not caveats attached after the architecture. They are consequences of the same principle as typed carriers: preserve distinctions instead of hiding them.

What UQA Changes About "One Database"

The most important property of UQA Engine is not that it implements a long feature list. It is that the features enter a shared optimizer without surrendering the semantics that make each one correct.

A relational row remains a row. A text match may carry positions and a raw score. A vector candidate retains index provenance. A graph match retains graph context. A join retains both identities. A posterior retains the distinction between evidence and prior. The planner can compose them because the boundaries are explicit—not because every value has been flattened into the same shape.

That is the practical meaning of a typed carrier algebra: one runtime, several honest semantics, and optimization laws that apply exactly where they have been proved.

Further Reading

• A Typed Carrier Algebra for Unified Query Execution
• UQA Engine source and manual
• A Unified Mathematical Framework for Query Algebras Across Heterogeneous Data Paradigms
• Extending the Unified Mathematical Framework to Support Graph Data Structures
• A Unified Bayesian Framework for Hybrid Search