Algorithmic Aspects of Semiring Provenance for Stratified Datalog

Explore the algorithmic challenges and solutions in semiring provenance for stratified Datalog in this 28-minute lecture by Matthias Naaf from RWTH Aachen. Delve into the complexities of evaluating queries with negations of least fixed points, focusing on stratified Datalog and fixed point logic. Learn how greatest fixed points can be efficiently computed in absorptive semirings with completeness and continuity assumptions. Discover the innovative approach of using circuit representations to address the issue of exponential-sized polynomials in query evaluation. Gain insights from related research on Newton's method for commutative semirings and its application to understanding fixed-point iterations through derivation trees. This talk, part of the Logic and Algebra for Query Evaluation series at the Simons Institute, is based on a RAMiCS'21 paper and draws connections to closely related works in program analysis and Datalog provenance.