Incremental View Maintenance 2
summary
Shows which conjunctive queries admit true constant-time single-tuple updates and constant enumeration delay: q-hierarchical queries do, and queries that become q-hierarchical after chasing given functional dependencies also do (example: path with x→y→z rewritten so z dominates). Practical implementation uses variable orders, factorized view trees and materialized indexed views to get O(1) lookups per delta. For non-q-hierarchical cases there is a spectrum (delta1 class) with a heavy/light partition yielding sqrt(N) update and delay trade-offs. Also demonstrates a covariance ring to maintain ML aggregates over joins.
AI-written summary · about
chapters (7)
- 0:00Hierarchical queries
- 21:22Maintenance and updates
- 24:16Open research questions
- 25:30Complexity and trade-offs
- 37:32Optimality classes
- 46:46Practical applications
- 51:15Maintaining machine learning
related talks
21mRecent Advances in Incremental View Maintenance
38mIncremental View Maintenance: Beyond Worst-Case Analysis I
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
37mContinuous Aggregates A Use Case of Materialized Views
19mAccessing Answers to Unions of Conjunctive Queries with Ideal Time Guarantees: II