Introduction to Relational Algorithms
summary
Defines relational linear regression that computes the covariance matrix Σ, vector c and scalar s directly from input tables S, P, C without materializing the join Q, by expressing each block of Σ as sum-product queries and solving them with variable elimination plus worst-case-optimal joins so many blocks run in linear time in input sizes and share intermediate factors. Introduces a data-complexity measure (the SPQ width) — runtime ≈ n^{width} — and relates it to fractional hypertree width and existing join bounds.
AI-written summary · about
chapters (13)
- 0:00Introduction
- 1:55What are Relational Algorithms
- 8:15Product Queries
- 11:20Product Queries Example
- 19:15Join Queries
- 26:18Elimination
- 31:13Elimination Cost
- 33:41Query Width
- 38:02Sparse Matrix Multiplication
- 42:33Feature Extraction
- 49:27Approach Outline
- 51:01Covariance Matrix
- 52:46Sigma Matrix
