Incremental View Maintenance 1
summary
Presents a concrete maintenance strategy for triangle queries that splits each relation into heavy/light partitions, materializes a few pairwise joins as auxiliary views and uses delta queries with periodic rebalancing to get amortized update time O(N^{max(ε,1−ε)}) and space that trades off to O(N^{3/2}) at worst; setting ε=1/2 yields O(N^{1/2}) amortized updates, matching a conditional OuMv-based lower bound; mentions a DBToaster-style higher-order view approach and notes prototype implementations but says practical tuning is ongoing.
AI-written summary · about
chapters (12)
- 0:00Introduction
- 0:51Setting
- 2:58Incremental View Maintenance
- 5:11Agenda
- 6:25Data Model
- 20:12Literature
- 27:38Lower Bounds
- 27:49Boolean Triangle Detection
- 33:50Algorithm B
- 35:49Encoding
- 51:21Update Time
- 52:59Maintenance Complexity
related talks
38mIncremental View Maintenance: Beyond Worst-Case Analysis I
21mRecent Advances in Incremental View Maintenance
26mIncremental View Maintenance: Beyond Worst-Case Analysis II
33mA (Semi)Ring-Based Query Algebra for Incremental View Maintenance and Query Compilation
49mIncremental Computation
45mpg_ivm - Extensions for Rapid Materialized View Update
06h 54mTopical Edition on Databases - Track 1
37mContinuous Aggregates A Use Case of Materialized Views