التفاصيل البيبلوغرافية
| العنوان: |
Convergence of datalog over (Pre-) Semirings. |
| المؤلفون: |
Abo Khamis, Mahmoud1 mahmoudabo@gmail.com, Ngo, Hung Q.1 hung.q.ngo@gmail.com, Pichler, Reinhard2 pichler@dbai.tuwien.ac.at, Suciu, Dan3 suciu@cs.washington.edu, Wang, Yisu Remy3 remywang@cs.washington.edu |
| المصدر: |
Journal of the ACM. Apr2024, Vol. 71 Issue 2, p1-55. 55p. |
| مصطلحات موضوعية: |
*BIG data, *ALGORITHMS, POLYNOMIAL time algorithms, NUMBER theory, SEMANTICS, NAIVE Bayes classification |
| مستخلص: |
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 article, 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-naïve evaluation algorithm on any datalog program. [ABSTRACT FROM AUTHOR] |
|
Copyright of Journal of the ACM is the property of Association for Computing Machinery and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| قاعدة البيانات: |
Business Source Index |