[Paper] Determination Provenance: From Ambiguity to Algebra
Source: arXiv - 2606.10270v1
Overview
Many data systems admit multiple admissible outcomes for the same input: concurrent transactions may serialize in one of many orders; a logic program may have multiple stable models. Classical data provenance cannot even pose its question in such settings — it explains how a result was derived, but only after something has chosen which result to produce. We introduce \emph{determination provenance} to track the commitments that resolve this ambiguity. A tuple’s \emph{support} is the set of resolutions under which it holds. Supports form a commutative semiring, and layered commitments induce a \emph{filtration} measuring each tuple’s \emph{query-relative depth} — how many layers of semantic resolution it depends on. Positive relational algebra respects the filtration, enabling compositional robustness analysis and quantitative diagnosis of resolution cost. We instantiate the framework for transactional isolation and for $\mbox{Datalog}^\neg$; in both, classical semantic variants (isolation levels; negation semantics) correspond to different views of a single shared filtration.
Key Contributions
This paper presents research in the following areas:
- cs.DB
- cs.DC
- cs.LO
Methodology
Please refer to the full paper for detailed methodology.
Practical Implications
This research contributes to the advancement of cs.DB.
Authors
- Joseph M. Hellerstein
Paper Information
- arXiv ID: 2606.10270v1
- Categories: cs.DB, cs.DC, cs.LO
- Published: June 9, 2026
- PDF: Download PDF