# Towards Linear Algebra over Normalized Data

arXiv: https://arxiv.org/abs/1612.07448 · HTML: https://mlsanity.com/paper/1612.07448/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Dec 2016.

## Built on by (most cited first, 12 of 12)

- [ARM-Net: Adaptive Relation Modeling Network for Structured Data](https://mlsanity.com/paper/2107.01830/) (2021)
- [Functional Collection Programming with Semi-Ring Dictionaries](https://mlsanity.com/paper/2103.06376/) (2021)
- [JoinBoost: Grow Trees Over Normalized Data Using Only SQL](https://mlsanity.com/paper/2307.00422/) (2023)
- [In-Database Data Imputation](https://mlsanity.com/paper/2401.03359/) (2024)
- [TranSQL+: Serving Large Language Models with SQL on Low-Resource Hardware](https://mlsanity.com/paper/2502.02818/) (2025)
- [Stochastic Gradient Descent without Full Data Shuffle](https://mlsanity.com/paper/2206.05830/) (2022)
- [Incorporating Deep Learning Design in Database Queries](https://mlsanity.com/paper/2605.24207/) (2026)
- [Fine-Tuning Data Structures for Analytical Query Processing](https://mlsanity.com/paper/2112.13099/) (2021)
- [TablePuppet: A Generic Framework for Relational Federated Learning](https://mlsanity.com/paper/2403.15839/) (2024)
- [InferF: Declarative Factorization of AI/ML Inferences over Joins](https://mlsanity.com/paper/2511.20489/) (2025)
- [Data Flow Control: Data Safety Policies for AI Agents](https://mlsanity.com/paper/2606.05679/) (2026)
- [InferQ: A Database-Oriented Benchmark for Quantum Circuits Simulation](https://mlsanity.com/paper/2607.29134/) (2026)

## Abstract (arXiv)

Providing machine learning (ML) over relational data is a mainstream requirement for data analytics systems. While almost all the ML tools require the input data to be presented as a single table, many datasets are multi-table, which forces data scientists to join those tables first, leading to data redundancy and runtime waste. Recent works on "factorized" ML mitigate this issue for a few specific ML algorithms by pushing ML through joins. But their approaches require a manual rewrite of ML implementations. Such piecemeal methods create a massive development overhead when extending such ideas to other ML algorithms. In this paper, we show that it is possible to mitigate this overhead by leveraging a popular formal algebra to represent the computations of many ML algorithms: linear algebra. We introduce a new logical data type to represent normalized data and devise a framework of algebraic rewrite rules to convert a large set of linear algebra operations over denormalized data into operations over normalized data. We show how this enables us to automatically "factorize" several popular ML algorithms, thus unifying and generalizing several prior works. We prototype our framework in the popular ML environment R and an industrial R-over-RDBMS tool. Experiments with both synthetic and real normalized data show that our framework also yields significant speed-ups, up to 36x on real data.