Khamis, M. A., Ngo, H. Q., Pichler, R., Suciu, D., & Wang, Y. R. (2023). Convergence of datalog over (pre-)semirings. SIGMOD RECORD, 52(1), 75–82. https://doi.org/10.1145/3604437.3604454
E192-02 - Forschungsbereich Databases and Artificial Intelligence
-
Journal:
SIGMOD RECORD
-
ISSN:
0163-5808
-
Date (published):
Mar-2023
-
Number of Pages:
8
-
Publisher:
ASSOC COMPUTING MACHINERY
-
Peer reviewed:
Yes
-
Keywords:
Datalog; Semantics; Optimization; Semirings; Algorithm; Boolean world; graph algorithms; Formal Language Theory; Machine Learning; Linear Algebra; Modern Deep Learning; semi-na¨ıve evaluation
en
Abstract:
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 generalize the semi-naïve evaluation algorithm to compute their minimal fixpoints.
en
Project title:
Decompose and Conquer: Fast Query Processing via Decomposition: ICT22-011 (WWTF Wiener Wissenschafts-, Forschu und Technologiefonds)
