2023/07/17 by Hongxiao Li, Li, Hongxiao, Wanling Gao +5
Computer Science · #Advanced Algebra and Logic #Advanced Database Systems and Queries #Computation and Language (cs.CL) #Data Structures and Algorithms (cs.DS) #Databases (cs.DB) #FOS: Computer and information sciences #Logic, Reasoning, and Knowledge
paper · pdf · doi:10.48550/arxiv.2307.08315
openalex publication_date 2023/07/17 · openalex created_date 2023/07/19 · openalex updated_date 2026/07/28
Lara is a key-value algebra that aims at unifying linear and relational algebra with three types of operation abstraction. The study of Lara'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 Lara. Lara cannot represent global and iterative computation, either. This article proposes IterLara, extending Lara 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 Lara and IterLara and prove that IterLara with aggregation functions can represent matrix inversion, determinant. Besides, we demonstrate that IterLara with no limitation of function utility is Turing complete. We also propose the Operation Count (OP) as a metric of computation amount for IterLara and ensure that the OP metric is in accordance with the existing computation metrics.