Expressive power of linear algebra query languages.

Linear algebra is an essential tool of any data scientist today. They use it through computational tools, like Matlab and R, where linear algebra programs are optimized and evaluated. Furthermore, people have brought linear algebra to data management systems, where they store data as matrices, and the query language needs to perform numeric tasks.

I will present our recent work on linear algebra and query languages (presented in PODS21). I will first introduce for-Matlang, a query language for matrices that uses for-loops, and explain how this language can express linear algebra operations like the inverse and the determinant of a matrix. Then I will show how we can compare the expressive power of for-Matlang with arithmetic circuits, a computational formalism used to understand classical linear algebra operations. Specifically, I will show that for-Matlang and uniform arithmetic circuit families are equally expressive. Towards the end of the talk, I will present some syntactic subclasses of for-Matlang that capture, for example, the expressive power of relational algebra over K-relations.