On the Expressiveness of LARA: A Unified Language for Linear and Relational Algebra
On the Expressiveness of LARA: A Unified Language for Linear and Relational Algebra
复制标题
论 LARA 的表达能力：线性和关系代数的统一语言
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Bernardo Subercaseaux
中科院分区：
文献类型：
--
作者：
P. Barceló;N. Higuera;Jorge Pérez;Bernardo Subercaseaux
我们研究了LARA语言（最近提出的用于表达关系和线性代数运算的统一模型）在传统数据库查询语言和机器学习管道中经常执行的一些分析任务方面的表达能力。我们首先证明LARA对于一阶逻辑的集合是表达完备的。由于LARA是由一组允许转换表中的值的用户定义函数参数化的，因此该语言的确切表达能力取决于如何定义这些函数。我们根据强制查询要满足的泛型级别来区分两种主要情况。在强泛型假设下，语言不能表示矩阵卷积，这是当前机器学习操作中非常重要的操作。这种语言也是局部的，因此不能表示表现递归行为的矩阵逆等操作。对于表示卷积，可以通过在定义域上添加一个潜在的线性阶来放宽对泛型的要求。然而，这破坏了局部性，使语言的表达能力变得更加难以理解。特别是，尽管在复杂性假设下，生成的语言仍然不能表示矩阵逆，但在没有这些假设的情况下对这一事实的证明似乎很难获得。
We study the expressive power of the LARA language -- a recently proposed unified model for expressing relational and linear algebra operations -- both in terms of traditional database query languages and some analytic tasks often performed in machine learning pipelines. We start by showing LARA to be expressive complete with respect to first-order logic with aggregation. Since LARA is parameterized by a set of user-defined functions which allow to transform values in tables, the exact expressive power of the language depends on how these functions are defined. We distinguish two main cases depending on the level of genericity queries are enforced to satisfy. Under strong genericity assumptions the language cannot express matrix convolution, a very important operation in current machine learning operations. This language is also local, and thus cannot express operations such as matrix inverse that exhibit a recursive behavior. For expressing convolution, one can relax the genericity requirement by adding an underlying linear order on the domain. This, however, destroys locality and turns the expressive power of the language much more difficult to understand. In particular, although under complexity assumptions the resulting language can still not express matrix inverse, a proof of this fact without such assumptions seems challenging to obtain.
DOI：
10.1145/2926534.2926540
发表时间：
2016-06
期刊：
Proceedings of the 3rd ACM SIGMOD Workshop on Algorithms and Systems for MapReduce and Beyond
影响因子：
--
作者：
Andreas Kunft;Alexander B. Alexandrov;Asterios Katsifodimos;V. Markl
通讯作者：
Andreas Kunft;Alexander B. Alexandrov;Asterios Katsifodimos;V. Markl