In this talk I will overview recent efforts to bridge between relational algebra and linear algebra, in particular how to leverage the sparsity of relational data for efficient and numerically accurate decompositions of matrices defined by natural joins over multiple relational tables. I will consider three important matrix decompositions, which form the staple for a myriad of computations in linear algebra and machine learning: QR Decomposition, SVD and PCA.

The key insight of our approach is the ability to push the decompositions past the joins and can thus avoid the materialize the join output. This leads to several desirable properties. For acyclic joins, it takes time linear in the size of the input database and independent of the size of the join output. The number of rounding errors relative to the classical decomposition algorithms is on par with the database size relative to the join output size.

A suite of experiments validate that this approach can outperform both in runtime performance and numerical accuracy the LAPACK library Intel MKL by a factor proportional to the gap between the sizes of the join output and input.