Recent Advances in Incremental View Maintenance
summary
Shows that a class of conjunctive queries called q-hierarchical admits constant update time and constant enumeration delay (assuming OM-style hardness otherwise), by maintaining a factorized view tree that is constructed in linear-time view-tree construction and updated with a constant number of lookups per base-tuple change. Demonstrates on triangle counting: removing two A2 B1 tuples reduces the triangle contribution from 19 to 13 without full recomputation. Describes how joins map to root-to-leaf paths and how factorization yields both provable bounds and practical speedups.
AI-written summary · about
chapters (12)
- 0:00Incremental view maintenance intro
- 1:45Triangle count maintenance example
- 5:22IVM complexity and optimality
- 6:26Key metrics in IVM
- 7:32Caal Cures constant updates
- 8:16Optimal complexities with factorization
- 9:43Variable order and factorized rep
- 12:37Update propagation in IVM
- 14:52Enumeration delay in CES
- 16:40Beyond kyal Cures constraints
- 19:11Summary of results
- 19:35Q&A
related talks
01h 05mIncremental View Maintenance 2
38mIncremental View Maintenance: Beyond Worst-Case Analysis I
01h 08mIncremental View Maintenance 1
26mIncremental View Maintenance: Beyond Worst-Case Analysis II
33mA (Semi)Ring-Based Query Algebra for Incremental View Maintenance and Query Compilation
49mIncremental Computation
01h 09mAccessing Answers to Unions of Conjunctive Queries with Ideal Time Guarantees: I
19mAccessing Answers to Unions of Conjunctive Queries with Ideal Time Guarantees: II