Factorized Databases
summary
Factorized databases store join results as lossless algebraic expressions using union and product, letting joins be computed in time proportional to the input plus the factorized output and enabling constant-delay enumeration of tuples. Variable orders and caching remove redundancy (e.g., price stored once), yielding practical compression—real retailer joins report up to 160× compression versus listing—and asymptotic savings tied to the factorization width. The same factorized circuits (deterministic, decomposable, smooth, ordered) support linear-time probability for hierarchical queries and one-pass aggregate and covariance computations via semiring/ring evaluations, and enable worst-case‑optimal incremental updates.
AI-written summary · about
chapters (8)
- 0:00Factorized databases intro
- 4:15Foundations of factorization
- 16:10Compression gains
- 23:53Factorized applications
- 27:14Probabilistic databases
- 34:25Aggregates in factorized form
- 41:05Summary and future
- 41:28Q&A on aggregates
related talks
01h 03mQuery Optimization and Evaluation 3: Variable Elimination and Tensor Decomposition
21mRecent Advances in Incremental View Maintenance
16mA Compiler for Fused Relational Operations on Multisets
36mOptimizing Relational Programs II
44mIntermediate Relational Algorithm Design
14mDeductive Optimization of Relational Data Storage
17mTowards Iterative Relational Algebra on the GPU
15mSpeeding up Symbolic Reasoning for Relational Queries