Algebraic Structures in Logic and Query Evaluation 2
summary
Semiring-based provenance unifies many prior notions by mapping complex annotations in a semiring of polynomials down to simpler forms via surjective homomorphisms so containment results lift between semirings, giving concrete complexity bounds: NP-complete for set CQ/UCQ, GI-complete for some bag cases, undecidable for bag containment of UCQs, and PSpace upper bounds for polynomial-style provenance. The framework adds monus for difference, uses absorptive polynomials for fixed‑point logic, and practical systems represent provenance as circuits to share subexpressions.
AI-written summary · about
chapters (6)
- 0:00Provenance semirings intro
- 17:49Query semantics with K-relations
- 27:38Containment in semirings
- 41:15Handling negation
- 53:59Open problems in provenance
- 1:01:57Q&A
related talks
28mAlgorithmic Aspects of Semiring Provenance for Stratified Datalog
38mThe Intensional-Extensional Problem in Probabilistic Databases
01h 06mSemiring Semantics
35mApproximating Certain and Possible Answers Beyond Sets
30mAchieving Understandability and Privacy With Provenance-Based Explanations
21mGenerating Collection Transformations from Proofs
52mVariety Membership Testing, Algebraic Natural Proofs, and Geometric Complexity Theory
26mDebugging Large-Scale Datalog: A Scalable Provenance Evaluation Strategy