Convergence of Datalog over (Pre-) Semirings
Convergence of Datalog over (Pre-) Semirings
复制标题
DOI：
10.1145/3517804.3524140
复制
发表时间：
2021-05
期刊：
影响因子：
--
通讯作者：
Mahmoud Abo Khamis;H. Ngo;R. Pichler;Dan Suciu;Y. Wang
中科院分区：
文献类型：
--
作者：
Mahmoud Abo Khamis;H. Ngo;R. Pichler;Dan Suciu;Y. Wang
传统上，递归查询是在DataLog的框架中研究的，该语言将递归限制在单调查询上的语言上是集合，保证在输入大小的多项式时间内会收敛。但是现代的大数据系统需要超越布尔空间的递归计算。在本文中，我们研究了数据通过任意半导体解释时的收敛性。我们将有序的半序列考虑，将DataG程序的语义定义为本半程中的最小固定点，并研究到达该固定点所需的步骤数（如果有的话）。我们确定了半段的代数属性，这些属性与数据核心程序的某些收敛属性相对应。最后，我们描述了一类有序的半连接，可以在任何数据编号程序上使用半主体评估算法。
Recursive queries have been traditionally studied in the framework of datalog, a language that restricts recursion to monotone queries over sets, which is guaranteed to converge in polynomial time in the size of the input. But modern big data systems require recursive computations beyond the Boolean space. In this paper we study the convergence of datalog when it is interpreted over an arbitrary semiring. We consider an ordered semiring, define the semantics of a datalog program as a least fixpoint in this semiring, and study the number of steps required to reach that fixpoint, if ever. We identify algebraic properties of the semiring that correspond to certain convergence properties of datalog programs. Finally, we describe a class of ordered semirings on which one can use the semi-naive evaluation algorithm on any datalog program.