  This article introduces Figaro, an algorithm for computing the
upper-triangular matrix in the QR decomposition of the matrix defined by the
natural join over relational data. Figaro's main novelty is that it pushes the
QR decomposition past the join. This leads to several desirable properties. For
acyclic joins, it takes time linear in the database size and independent of the
join size. Its execution is equivalent to the application of a sequence of
Givens rotations proportional to the join size. Its number of rounding errors
relative to the classical QR decomposition algorithms is on par with the
database size relative to the join output size.
  The QR decomposition lies at the core of many linear algebra computations
including the singular value decomposition (SVD) and the principal component
analysis (PCA). We show how Figaro can be used to compute the orthogonal matrix
in the QR decomposition, the SVD and the PCA of the join output without the
need to materialize the join output.
  A suite of experiments validate that Figaro 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.
