Incremental View Maintenance: Beyond Worst-Case Analysis I

on YouTube ↗38m

" summary

Focuses on achieving constant-delay enumeration for conjunctive queries by replacing join materialization with layered semi-joins and projections, storing per-value counters and small projection views so updates touch only bounded memory. Claims linear preprocessing and constant update time for q-hierarchical queries (equivalently height‑1 generalized join trees), while non-q-hierarchical cases hit a worst‑case Ω(√N) update barrier. Implements top‑down enumeration probing semi-join tables; it works for many practical update patterns but still suffers adversarial update sequences unless the update sequence structure is exploited.

AI-written summary · about

" chapters (7)

1. 0:00Introduction
2. 1:08Problem definition for IVM
3. 8:09Conjunctive and free-connex queries
4. 19:47Change propagation limits
5. 24:48Semi-join and projection views
6. 33:50Full enumeration with semi-join views
7. 37:57Summary & Q&A

" related talks

• 01h 05mIncremental View Maintenance 2Dan Olteanu · Logic and Algorithms in Database Theory and AI Boot Camp
• 21mRecent Advances in Incremental View MaintenanceHaozhe Zhang · Sparse 2024
• 01h 08mIncremental View Maintenance 1Dan Olteanu · Logic and Algorithms in Database Theory and AI Boot Camp
• 33mA (Semi)Ring-Based Query Algebra for Incremental View Maintenance and Query CompilationChristoph Koch · Logic and Algebra for Query Evaluation 2023
• 49mIncremental ComputationMihai Budiu · Rootconf Topical Edition on Databases 2026
• 01h 05mQuery Optimization and Evaluation 2: Worst-Case Optimal Join AlgorithmsHung Ngo · Logic and Algorithms in Database Theory and AI Boot Camp
• 45mpg_ivm - Extensions for Rapid Materialized View UpdateYugo Nagata · PostgreSQL Conference Europe 2024
• 06h 54mTopical Edition on Databases - Track 1Sandeep Joshi, Ranganadh Thata · Rootconf Topical Edition on Databases 2026