Intermediate Relational Algorithm Design

on YouTube ↗44m

" summary

Relational-algorithms assume inputs stay in relational form and claim most useful operations reduce to sum-product queries; the talk shows concrete reductions: uniform sampling reduces to counting via variable elimination on path joins, 1-means++ and 2-means++ become implementable by designing a semi-ring pair (count,sumSquares) and running variable-elimination, while 3-means++ is NP-hard on compact tables so the practical fix is rejection sampling with axis-aligned boxes; counting in a hypersphere is approximable to 1+ε when operations preserve approximation; an ID3-as-homework implementation is proposed.

AI-written summary · about

" chapters (8)

1. 0:00Introduction
2. 0:48Compressed Text
3. 2:14Restricted Models
4. 3:04Joints
5. 5:29Product Queries
6. 33:16Conclusion
7. 34:04Example
8. 40:49Questions

" related talks

• 05mRelational ProgrammingRemy Wang · 9th Annual Simons Institute Industry Day
• 15mSpeeding up Symbolic Reasoning for Relational QueriesChenglong Wang · OOPSLA 2018
• 38mAdd ALL the things: abstract algebra meets analyticsAvi Bryant · Strange Loop 2013
• 29mDirect Access for Conjunctive Queries with AggregationNofar Carmeli · Logic and Algebra for Query Evaluation 2023
• 04mLogic and Algorithms In Database Theory and AIHung Ngo · 9th Annual Simons Institute Industry Day
• 01h 03mQuery Optimization and Evaluation 3: Variable Elimination and Tensor DecompositionHung Ngo · Logic and Algorithms in Database Theory and AI Boot Camp
• 26mRelational E-matchingZachary Tatlock, Max Willsey, Yihong Zhang, Yisu Remy Wang · POPL 2022
• 01h 06mSampling in Query Evaluation 1Marcelo Arenas · Logic and Algorithms in Database Theory and AI Boot Camp