Relational Programming

on YouTube ↗05m

" summary

One-line relational joins and semiring rewrites turn into concrete systems: a datalog engine (birelational AI) automatically parallelizes and distributes joins, handles fault tolerance, and maps semiring +/× to matrix multiply over sparse tensors. Replacing semiring yields transitive closure or shortest paths and the optimizer rewrites code to recover Bellman-Ford for sparse shortest paths. Algebraic rewrite rules exploit associativity and commutativity and sparsity to produce a ten-line specification that rewrites into Brandes’s algorithm and runs thousands of times faster than naive.

AI-written summary · about

" related talks

• 36mOptimizing Relational Programs IIRemy Wang · Fine-Grained Complexity, Logic, and Query Evaluation 2023
• 41mOptimizing Relational Programs IRemy Wang · Fine-Grained Complexity, Logic, and Query Evaluation 2023
• 01h 08mAlgebraic Structures in Logic and Query Evaluation 4Dan Suciu · Logic and Algorithms in Database Theory and AI Boot Camp
• 15mSpeeding up Symbolic Reasoning for Relational QueriesChenglong Wang · OOPSLA 2018
• 01h 02mAlgebraic Structures in Logic and Query Evaluation 3Dan Suciu · Logic and Algorithms in Database Theory and AI Boot Camp
• 44mIntermediate Relational Algorithm DesignKirk Pruhs · Fine-Grained Complexity, Logic, and Query Evaluation 2023
• 01h 06mSemiring SemanticsErich Graedel · Logic and Algebra for Query Evaluation 2023
• 01h 05mIntroduction to Relational AlgorithmsMahmoud Abo Khamis · Fine-Grained Complexity, Logic, and Query Evaluation 2023