一句话：提出半环字典这一纯函数式集合抽象与静态类型语言SDQL，统一数据库与线性代数优化，高效处理混合工作负载。
本文针对数据库（关系代数与聚合）和线性代数（数组、矩阵）工作负载使用不同集合抽象、优化难以统一的问题，提出了半环字典：一类可组合、纯函数式的集合类型，能够涵盖集合、多重集、数组、向量和矩阵。作者实现了静态类型语言 SDQL，可用半环字典表达带聚合的关系代数、线性代数和函数式集合，并借助其代数结构统一了数据库与线性代数中常见的优化，从而高效处理混合 DB/LA 工作负载。实验在若干 DB 与 LA 基准上展开，与内存数据库系统 Typer、Tectorwise，科学计算库 SciPy，稀疏张量编译器 taco，嵌套关系引擎 Trance，以及数据库内机器学习引擎 LMFAO、Morpheus 等各自领域的最先进系统相比，SDQL 取得了相当或更优的性能。
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.
@article{paperbot1532,
title = {Functional collection programming with semi-ring dictionaries},
author = {Amir Shaikhha and Mathieu Huot and Jaclyn Smith and Dan Olteanu},
journal = {Proceedings of the ACM on Programming Languages},
volume = {6},
number = {OOPSLA1},
year = {2022},
doi = {10.1145/3527333}
}