Incremental Processing of Structured Data in Datalog
summary
Proposes a relational encoding that makes small edits to trees and lists produce small changes to Datalog inputs, claims up to 10,000x incremental speedups on workloads already using the encoding, and integrates the encoding into the Inca incremental Datalog framework. Encoding follows three practical rules: context-insensitive unique identifiers, unary and binary relations, and relative positioning for lists. Describes using tree-diff patches to translate edits into insertions/deletions and index structures that enable constant-time containment and efficient forward/backward queries.
AI-written summary · about
chapters (9)
- 0:00Incremental computing
- 2:11Datalog as incremental model
- 3:34Structured data challenges
- 6:07Efficient encoding design
- 6:28Tree-shaped data encoding
- 8:58List data with positioning
- 10:48Efficient relational queries
- 13:14Results in Inca framework
- 14:41Conclusion and future
related talks
36mOptimizing Relational Programs II
13mAccelerating Program Analyses in Datalog by Merging Library Facts
14mDeductive Optimization of Relational Data Storage
36mData Driven UIs, Incrementally
17mBring Your Own Data Structures to Datalog
17mA Systematic Approach to Deriving Incremental Type Checkers
01h 13mCRDTs: The hard parts
26mStateful Differential Operators for Incremental Computing