# IterLara: A Turing Complete Algebra for Big Data, AI, Scientific Computing, and Database

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 15 references that are in the map.
- First posted on arXiv 17 Jul 2023.

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

- [Pooling Methods in Deep Neural Networks, a Review](https://mlsanity.com/paper/2009.07485/) (2020)
- [LaraDB: A Minimalist Kernel for Linear and Relational Algebra Computation](https://mlsanity.com/paper/1703.07342/) (2017)
- [Expressive power of linear algebra query languages](https://mlsanity.com/paper/2010.13717/) (2020)
- [Lara: A Key-Value Algebra underlying Arrays and Relations](https://mlsanity.com/paper/1604.03607/) (2016)
- [Associative Array Model of SQL, NoSQL, and NewSQL Databases](https://mlsanity.com/paper/1606.05797/) (2016)
- [On the Expressiveness of LARA: A Unified Language for Linear and Relational Algebra](https://mlsanity.com/paper/1909.11693/) (2019)

## Abstract (arXiv)

textscLara is a key-value algebra that aims at unifying linear and relational algebra with three types of operation abstraction. The study of textscLara's expressive ability reports that it can represent relational algebra and most linear algebra operations. However, several essential computations, such as matrix inversion and determinant, cannot be expressed in textscLara. textscLara cannot represent global and iterative computation, either. This article proposes textscIterLara, extending textscLara with iterative operators, to provide an algebraic model that unifies operations in general-purpose computing, like big data, AI, scientific computing, and database. We study the expressive ability of textscLara and textscIterLara and prove that textscIterLara with aggregation functions can represent matrix inversion, determinant. Besides, we demonstrate that textscIterLara with no limitation of function utility is Turing complete. We also propose the Operation Count (OP) as a metric of computation amount for textscIterLara and ensure that the OP metric is in accordance with the existing computation metrics.