# Functional Collection Programming with Semi-Ring Dictionaries

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 144 references that are in the map.
- First posted on arXiv 10 Mar 2021.

## Builds on (most cited first, 22 of 22)

- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [Tensor Comprehensions: Framework-Agnostic High-Performance Machine Learning Abstractions](https://mlsanity.com/paper/1802.04730/) (2018)
- [MLlib: Machine Learning in Apache Spark](https://mlsanity.com/paper/1505.06807/) (2015)
- [Format Abstraction for Sparse Tensor Algebra Compilers](https://mlsanity.com/paper/1804.10112/) (2018)
- [Extending Relational Query Processing with ML Inference](https://mlsanity.com/paper/1911.00231/) (2019)
- [FAQ: Questions Asked Frequently](https://mlsanity.com/paper/1504.04044/) (2015)
- [On the expressive power of query languages for matrices](https://mlsanity.com/paper/1709.08359/) (2017)
- [Mathematical Foundations of the GraphBLAS](https://mlsanity.com/paper/1606.05790/) (2016)
- [Towards Linear Algebra over Normalized Data](https://mlsanity.com/paper/1612.07448/) (2016)
- [A Layered Aggregate Engine for Analytics Workloads](https://mlsanity.com/paper/1906.08687/) (2019)
- [HoTTSQL: Proving Query Rewrites with Univalent SQL Semantics](https://mlsanity.com/paper/1607.04822/) (2016)
- [Efficient Differentiable Programming in a Functional Array-Processing Language](https://mlsanity.com/paper/1806.02136/) (2018)
- [Building Efficient Query Engines in a High-Level Language](https://mlsanity.com/paper/1612.05566/) (2016)
- [AC/DC: In-Database Learning Thunderstruck](https://mlsanity.com/paper/1803.07480/) (2018)
- [LaraDB: A Minimalist Kernel for Linear and Relational Algebra Computation](https://mlsanity.com/paper/1703.07342/) (2017)
- [Multi-layer Optimizations for End-to-End Data Analytics](https://mlsanity.com/paper/2001.03541/) (2020)
- [Stream Fusion, to Completeness](https://mlsanity.com/paper/1612.06668/) (2016)
- [Push vs. Pull-Based Loop Fusion in Query Engines](https://mlsanity.com/paper/1610.09166/) (2016)
- [Query shredding: Efficient relational evaluation of queries over nested multisets (extended version)](https://mlsanity.com/paper/1404.7078/) (2014)
- [Polystore Mathematics of Relational Algebra](https://mlsanity.com/paper/1712.00802/) (2017)
- [Program Generation for Small-Scale Linear Algebra Applications](https://mlsanity.com/paper/1805.04775/) (2018)
- [Scalable Querying of Nested Data](https://mlsanity.com/paper/2011.06381/) (2020)

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

- [Fine-Tuning Data Structures for Analytical Query Processing](https://mlsanity.com/paper/2112.13099/) (2021)
- [Efficient and Sound Differentiable Programming in a Functional Array-Processing Language](https://mlsanity.com/paper/2212.10307/) (2022)
- [nablaSD: Differentiable Programming for Sparse Tensors](https://mlsanity.com/paper/2303.07030/) (2023)
- [Compressing Structured Tensor Algebra](https://mlsanity.com/paper/2407.13726/) (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)

## Abstract (arXiv)

This paper introduces semi-ring dictionaries, a powerful class of compositional and purely functional collections that subsume other collection types such as sets, multisets, arrays, vectors, and matrices. We developed SDQL, a statically typed language that can express relational algebra with aggregations, linear algebra, and functional collections over data such as relations and matrices using semi-ring dictionaries. Furthermore, thanks to the algebraic structure behind these dictionaries, SDQL unifies a wide range of optimizations commonly used in databases (DB) and linear algebra (LA). As a result, SDQL enables efficient processing of hybrid DB and LA workloads, by putting together optimizations that are otherwise confined to either DB systems or LA frameworks. We show experimentally that a handful of DB and LA workloads can take advantage of the SDQL language and optimizations. SDQL can be competitive with or outperforms a host of systems that are state of the art in their own domain: in-memory DB systems Typer and Tectorwise for (flat, not nested) relational data; SciPy for LA workloads; sparse tensor compiler taco; the Trance nested relational engine; and the in-database machine learning engines LMFAO and Morpheus for hybrid DB/LA workloads over relational data.