Search papers, labs, and topics across Lattice.
This paper introduces the concept of determination provenance to address the ambiguity in data systems where multiple admissible outcomes can arise from the same input. By defining a tuple's support as the set of resolutions under which it holds, the authors establish a commutative semiring structure that allows for the measurement of a tuple's query-relative depth through layered commitments. The framework is instantiated for transactional isolation and Datalog with negation, revealing that classical semantic variants correspond to different perspectives of a unified filtration, thus enhancing compositional robustness analysis and resolution cost diagnosis.
Determination provenance reveals how to quantify and analyze the ambiguity in data systems, transforming our understanding of data resolution costs.
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.
BAIR