Optimizing Relational Programs II

on YouTube ↗36m

" summary

Proposes concrete methods to evaluate recursive Datalog by mapping relations to vectors/matrices over closed semirings and computing fixpoints with algebraic path algorithms and Newton-style acceleration: a cubic-time Floyd–Warshall-like algorithm computes closure for linear Datalog (matrix dimension n), matrix inversion reduces to the closure operator, and certain reducible graphs admit a nearly-linear (m α(m)) solution; non-linear recursion uses a semiring-safe Newton iteration (requires natural order and closure, defines a symbolic derivative and delta update), trading inner fixpoint cost for fewer outer iterations and better parallelism.

AI-written summary · about

" chapters (7)

1. 0:00Automata minimization
2. 3:35Recursive Datalog overview
3. 7:08Datalog as linear algebra
4. 11:11Closed semirings and Kleene iteration
5. 16:15Floyd-Warshall-Kleene for closure
6. 21:59Newton’s method for Datalog
7. 31:57Questions and discussion

" related talks

• 05mRelational ProgrammingRemy Wang · 9th Annual Simons Institute Industry Day
• 01h 08mAlgebraic Structures in Logic and Query Evaluation 4Dan Suciu · Logic and Algorithms in Database Theory and AI Boot Camp
• 01h 02mAlgebraic Structures in Logic and Query Evaluation 3Dan Suciu · Logic and Algorithms in Database Theory and AI Boot Camp
• 13mAccelerating Program Analyses in Datalog by Merging Library FactsXin Zhang, Lu Zhang, Yingfei Xiong, Chenyang Yang, Yifan Chen, Hao Tang, Xiaoyin Wang · SAS 2021
• 28mAlgorithmic Aspects of Semiring Provenance for Stratified DatalogMatthias Naaf · Logic and Algebra for Query Evaluation 2023
• 01h 01mDatalog and Equality SaturationMax Willsey · Logic and Algebra for Query Evaluation 2023
• 17mTowards Iterative Relational Algebra on the GPUSidharth Kumar, Kristopher Micinski, Thomas Gilray, Ahmedur Rahman Shovon · USENIX ATC '23
• 14mDeductive Optimization of Relational Data StorageArmando Solar-Lezama, Sam Madden, Jack Feser, John Feser, Nan Tang · OOPSLA 2020