Algebraic Structures in Logic and Query Evaluation 1
summary
Semiring-based provenance treats input tuple labels as algebraic tokens and computes provenance polynomials that record exact derivations and multiplicities, are PTIME computable, and admit a universality property so any semiring evaluation (e g confidence, access cost) extends uniquely and commutes with query execution. The framework requires a commutative semiring (covers set and bag semantics) and yields practical systems — an Orchestra implementation stores provenance with roughly 30% overhead and supports Viterbi/tropical, trust and access-control interpretations.
AI-written summary · about
chapters (16)
- 0:00Introduction
- 1:48Data Sharing
- 7:14Trust
- 10:17Access Control
- 12:13Confidence Scores
- 14:49Provenance
- 17:22Proposal
- 18:45Problem Setup
- 21:43How does this work
- 36:19Tropical Semiring
- 39:19Lukasievich Semiring
- 41:14Semiring aficionados
- 43:54Semiring properties
- 47:16Provenance polynomials
- 49:29Provenance tokens
- 55:22Boolean positive expressions
related talks
28mAlgorithmic Aspects of Semiring Provenance for Stratified Datalog
01h 06mSemiring Semantics
26mDebugging Large-Scale Datalog: A Scalable Provenance Evaluation Strategy
35mApproximating Certain and Possible Answers Beyond Sets
30mAchieving Understandability and Privacy With Provenance-Based Explanations
05mRelational Programming
15mSpeeding up Symbolic Reasoning for Relational Queries
57mAlgebraic Databases