Classical data provenance tells you how a result was derived, but only after the system has already picked which result to produce. That assumption of a single deterministic outcome breaks entirely when concurrent transactions can serialize in different orders or a logic program admits multiple stable models.
A new preprint (arXiv:2606.10270) introduces determination provenance — an algebraic framework that tracks the commitments that resolve ambiguity. Instead of a single derivation tree, each tuple carries a support: the set of admissible resolutions (e.g., possible serializations or stable model assignments) under which the tuple holds. Supports form a commutative semiring, so you can compose and reason algebraically about ambiguity.
Layered Commitments and Query-Relative Depth
The key structural innovation is a filtration induced by layered commitments. Each layer represents a distinct semantic resolution (e.g., fixing a write order or choosing a negation semantics). A tuple’s query-relative depth is the number of layers it depends on — how many nested resolutions must be settled before that tuple becomes true. Positive relational algebra respects the filtration, meaning compositional reasoning stays sound as you add layers.
Two Concrete Instantiations: Isolation Levels and Datalog¬
The framework is not abstract speculation. The paper instantiates determination provenance for two real settings: transactional isolation and Datalog with negation. In both cases, classical semantic variants — isolation levels like read-committed vs. serializable, or stratified vs. well-founded negation — turn out to be different views of a single shared filtration. That collapses what used to be separate models into one algebraic structure, enabling quantitative diagnosis of resolution cost: how many layers of semantic resolution does a particular query actually need?
This is the kind of tool that lets you run robustness analysis on a database’s concurrency control or a logic program’s semantics without rebuilding the entire provenance graph. The filtration gives you a precise measure of where fragility lives.
What This Enables Next
Determination provenance turns a fuzzy “maybe” into an algebraic object you can compute with. That opens the door to automated reasoning about isolation level downgrades — for example, quantifying the cost of moving from serializable to snapshot isolation by tracking which tuples lose support — and to diagnosing hidden dependencies in non-deterministic logic programs. The algebra is the foundation; the engineering question is who ships the tooling first.
Source: Determination Provenance: From Ambiguity to Algebra
Domain: arxiv.org
Comments load interactively on the live page.