A (Semi)Ring-Based Query Algebra for Incremental View Maintenance and Query Compilation

on YouTube ↗33m

" summary

Argues that queries form a polynomial algebra over avalanche (semi)rings so deltas become algebraic derivatives and the k-th deltas depend only on the update, not the database. Shows a compilation that materializes multi-layer auxiliary views to eliminate joins and maintain each aggregate with constant work for non-nested queries, proves update-time complexity in NC0 versus AC0 for non-incremental evaluation, and ships a prototype called DBToaster that implements these ideas (GitHub available).

AI-written summary · about

" chapters (11)

1. 0:00Rings in databases motivation
2. 1:24Relational algebra numerical limits
3. 4:12Monoid semirings for query algebra
4. 8:51Monoid rings and generalized multisets
5. 14:37Ring properties for bag/set semantics
6. 16:47Rings for sideways information passing
7. 18:57Query language with aggregation
8. 21:29Recursive view maintenance deltas
9. 23:56SQL compilation to incremental updates
10. 26:30Complexity and dbtoaster system
11. 28:17Future work in IVM

" related talks

• 01h 05mIncremental View Maintenance 2Dan Olteanu · Logic and Algorithms in Database Theory and AI Boot Camp
• 01h 08mIncremental View Maintenance 1Dan Olteanu · Logic and Algorithms in Database Theory and AI Boot Camp
• 21mRecent Advances in Incremental View MaintenanceHaozhe Zhang · Sparse 2024
• 38mIncremental View Maintenance: Beyond Worst-Case Analysis IXiao Hu · Fine-Grained Complexity, Logic, and Query Evaluation 2023
• 49mIncremental ComputationMihai Budiu · Rootconf Topical Edition on Databases 2026
• 26mIncremental View Maintenance: Beyond Worst-Case Analysis IIXiao Hu · Fine-Grained Complexity, Logic, and Query Evaluation 2023
• 06h 54mTopical Edition on Databases - Track 1Sandeep Joshi, Ranganadh Thata · Rootconf Topical Edition on Databases 2026
• 36mOptimizing Relational Programs IIRemy Wang · Fine-Grained Complexity, Logic, and Query Evaluation 2023