Relational Processing of Linear and Tensor Algebra Queries - a Formal Approach

Abstract

Efficient query processing has long been a cornerstone of database systems, with decades of research yielding rich theoretical foundations and highly optimized techniques for relational queries. Meanwhile, linear and tensor algebra operations form the computational backbone of modern machine learning and data science, yet they lack comparable theoretical frameworks for optimization and complexity analysis. This thesis bridges this gap by establishing formal correspondences between matrix query languages and relational query fragments, transferring tractability results across settings, and extending these results to general tensor computations with arbitrary pointwise operations. We begin by refining the correspondence between sum-MATLANG, a matrix query language supporting iteration and aggregation, and positive first-order logic. Through symmetric, linear-size schema encodings, we prove that conj-MATLANG (sum-MATLANG without matrix addition) corresponds exactly to the conjunctive fragment of positive-existential firstorder logic. Building on this foundation, we identify fc-MATLANG and qh-MATLANG as the matrix counterparts of free-connex and q-hierarchical conjunctive queries, respectively, establishing these correspondences via novel characterizations involving the two-variable fragment of first-order logic. We then transfer algorithmic upper and lower bounds from the Boolean semiring to arbitrary semirings satisfying natural algebraic properties. For upper bounds, we show that free-connex queries over zero-divisor free semirings admit linear-time preprocessing and constant-delay enumeration, while q-hierarchical queries over sum-maintainable semirings additionally support constant-time updates. For lower bounds, we prove that under standard complexity-theoretic conjectures, these fragments are optimal: no query outside these classes achieves the same guarantees. Finally, we address tensor queries involving arbitrary pointwise functions beyond semiring operations. We formalize a tensor query language parameterized by universal algebras and define sparse evaluation problems asking which output coordinates have annotations in a desired set. For full queries over algebras admitting finite interpretations, we prove that sparse evaluation reduces to relational algebra computation, with positive programs arising when the algebra is monotone. However, we also establish that projection fundamentally complicates this picture, revealing inherent obstacles to purely relational optimization of non-full tensor queries. Together, these results provide a unified perspective on the complexity of linear algebra and tensor queries, identifying precisely which fragments inherit the optimization techniques and complexity guarantees of relational query processing, and delineating the boundaries beyond for which new techniques are required.