# Givens QR Decomposition over Relational Databases

**Authors:** Dan Olteanu, Nils Vortmeier, Đorđe Živanović  
**arXiv:** [2204.00525](https://arxiv.org/abs/2204.00525)  
**Date:** 2022-04-01  
**Summary page:** https://www.summarizepaper.com/en/paper/2204.00525v1/

## Key points

- The paper introduces Figaro, an algorithm for computing the upper-triangular matrix in the QR decomposition of a matrix defined by the natural join over a relational database.
- The QR decomposition is important for many linear algebra techniques and machine learning applications.
- Figaro extends the QR decomposition beyond the join operation, resulting in several desirable properties such as time linear to database size and independent of join size.
- Experiments showed that Figaro outperformed openblas and Intel MKL LAPACK libraries in terms of runtime performance and accuracy.
- Figaro presents a novel approach to computing QR decompositions over relational databases that offers significant advantages over existing methods.

## Summary

In their paper titled "Givens QR Decomposition over Relational Databases," Dan Olteanu, Nils Vortmeier, and Đorđe Živanović introduce Figaro, an algorithm for computing the upper-triangular matrix in the QR decomposition of a matrix defined by the natural join over a relational database. The QR decomposition is a fundamental component of many linear algebra techniques and their machine learning applications, including the matrix inverse, least squares, singular value decomposition, eigenvalue problems, and principal component analysis. Figaro's main innovation is that it extends the QR decomposition beyond the join operation. This results in several desirable properties: for acyclic joins, it takes time linear in the size of the database and independent of the join size; its execution is equivalent to applying a sequence of Givens rotations proportional to the join size; and its number of rounding errors relative to classical QR decomposition algorithms is on par with input size relative to join size. The authors conducted experiments using real-world and synthetic databases to compare Figaro's performance against openblas and Intel MKL LAPACK libraries. They found that Figaro outperformed both libraries in terms of runtime performance and accuracy by a factor proportional to the gap between output and input sizes. Overall, Figaro presents a novel approach to computing QR decompositions over relational databases that offers significant advantages over existing methods. Its ability to handle large-scale datasets efficiently while maintaining high accuracy makes it an attractive option for researchers working with machine learning applications that rely on linear algebra techniques.