Algebraic Structures in Logic and Query Evaluation 4

on YouTube ↗01h 08m

" summary

Explains that datalog evaluation over semirings reduces to grounded systems of polynomial equations whose solutions are provenance power series, shows simple examples (Fibonacci, Catalan) and proves termination depends on algebraic properties: dioids can still diverge, absorptive semirings always converge in ≤N iterations, p-stable semirings give a rather large bound, and non-uniform stability is necessary and sufficient. Covers Lehmann’s matrix closure for linear systems and Kozen/Parikh results for commutative Kleene algebras, then asks whether these closures can speed real datalog evaluation.

AI-written summary · about

" chapters (12)

1. 0:00Intro
2. 5:10Termination of the naive algorithm
3. 6:19Polynomial equations
4. 13:44Omega continuous semiring
5. 17:13Grounding
6. 28:11Algebraic Properties
7. 29:09Diodes
8. 32:58Absorptive Semi Rings
9. 37:31Stable Semi Rings
10. 44:45Closure Operator
11. 48:49Closed Same Ring
12. 52:10Closing a Matrix

" related talks

• 36mOptimizing Relational Programs IIRemy Wang · Fine-Grained Complexity, Logic, and Query Evaluation 2023
• 28mAlgorithmic Aspects of Semiring Provenance for Stratified DatalogMatthias Naaf · Logic and Algebra for Query Evaluation 2023
• 01h 06mSemiring SemanticsErich Graedel · Logic and Algebra for Query Evaluation 2023
• 05mRelational ProgrammingRemy Wang · 9th Annual Simons Institute Industry Day
• 01h 01mDatalog and Equality SaturationMax Willsey · Logic and Algebra for Query Evaluation 2023
• 35mApproximating Certain and Possible Answers Beyond SetsBoris Glavic · Logic and Algebra for Query Evaluation 2023
• 24mWhen Less Is More: Consequence-Finding in a Weak Theory of ArithmeticZachary Kincaid, Shaowei Zhu, Nicolas Koh · POPL 2023
• 32mCircuits for Querying Trees: A Little SurveyPierre Bourhis · Logic and Algebra for Query Evaluation 2023