Convergence of Datalog over (Pre-) Semirings
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.
References
[1]
Abadi, M., Barham, P., Chen, J., Chen, Z., Davis, A., Dean, J., Devin, M., Ghemawat, S., Irving, G., Isard, M., Kudlur, M., Levenberg, J., Monga, R., Moore, S., Murray, D. G., Steiner, B., Tucker, P. A., Vasudevan, V., Warden, P., Wicke, M., Yu, Y., and Zheng, X. Tensorflow: A system for large-scale machine learning. In 12th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2016, Savannah, GA, USA, November 2--4, 2016 (2016), K. Keeton and T. Roscoe, Eds., USENIX Association, pp. 265--283.
[2]
Abiteboul, S., Hull, R., and Vianu, V. Foundations of Databases. Addison-Wesley, 1995.
[3]
Aji, S. M., and McEliece, R. J. The generalized distributive law. IEEE Trans. Inf. Theory 46, 2 (2000), 325--343.
[4]
Carr´e, B. Graphs and networks. The Clarendon Press, Oxford University Press, New York, 1979. Oxford Applied Mathematics and Computing Science Series.
[5]
Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. Introduction to algorithms, third ed. MIT Press, Cambridge, MA, 2009.
[6]
Cousot, P., and Cousot, R. Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints. In Conference Record of the Fourth ACM Symposium on Principles of Programming Languages, Los Angeles, California, USA, January 1977 (1977), R. M. Graham, M. A. Harrison, and R. Sethi, Eds., ACM, pp. 238--252.
[7]
Dannert, K. M., Gr¨adel, E., Naaf, M., and Tannen, V. Semiring provenance for fixed-point logic. In 29th EACSL Annual Conference on Computer Science Logic, CSL 2021, January 25--28, 2021, Ljubljana, Slovenia (Virtual Conference) (2021), C. Baier and J. Goubault-Larrecq, Eds., vol. 183 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum f¨ur Informatik, pp. 17:1--17:22.
[8]
Dechter, R. Bucket elimination: a unifying framework for processing hard and soft constraints. Constraints An Int. J. 2, 1 (1997), 51--55.
[9]
Eisner, J., and Filardo, N. W. Dyna: Extending datalog for modern AI. In Datalog Reloaded - First International Workshop, Datalog 2010, Oxford, UK, March 16--19, 2010. Revised Selected Papers (2010),
[10]
Fitting, M. A kripke-kleene semantics for logic programs. J. Log. Program. 2, 4 (1985), 295--312.
[11]
Freeman, L. C. A Set of Measures of Centrality Based on Betweenness. Sociometry 40, 1 (Mar. 1977), 35--41.
[12]
Gondran, M., and Minoux, M. Graphs, dioids and semirings, vol. 41 of Operations Research/Computer Science Interfaces Series. Springer, New York, 2008. New models and algorithms.
[13]
Green, T. J., Karvounarakis, G., and Tannen, V. Provenance semirings. In Proceedings of the Twenty-Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 11--13, 2007, Beijing, China (2007), L. Libkin, Ed., ACM, pp. 31--40.
[14]
Gunawardena, J. An introduction to idempotency. In Idempotency (Bristol, 1994), vol. 11 of Publ. Newton Inst. Cambridge Univ. Press, Cambridge, 1998, pp. 1--49.
[15]
Khamis, M. A., Ngo, H. Q., Pichler, R., Suciu, D., and Wang, Y. R. Convergence of datalog over (pre-) semirings. CoRR abs/2105.14435 (2021).
[16]
Khamis, M. A., Ngo, H. Q., Pichler, R., Suciu, D., and Wang, Y. R. Convergence of datalog over (pre-) semirings. In PODS '22: International Conference on Management of Data, Philadelphia, PA, USA, June 12 - 17, 2022 (2022), L. Libkin and P. Barcel´o, Eds., ACM, pp. 105--117.
[17]
Khamis, M. A., Ngo, H. Q., and Rudra, A. FAQ: questions asked frequently. In Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2016, San Francisco, CA, USA, June 26 - July 01, 2016 (2016), T. Milo and W. Tan, Eds., ACM, pp. 13--28.
[18]
Kohlas, J. Information algebras - generic structures for inference. Discrete mathematics and theoretical computer science. Springer, 2003.
[19]
Kohlas, J., and Wilson, N. Semiring induced valuation algebras: Exact and approximate local computation algorithms. Artif. Intell. 172, 11 (2008), 1360--1399.
[20]
Kuich, W. Semirings and formal power series: their relevance to formal languages and automata. In Handbook of formal languages, Vol. 1. Springer, Berlin, 1997, pp. 609--677.
[21]
Lehmann, D. J. Algebraic structures for transitive closure. Theor. Comput. Sci. 4, 1 (1977), 59--76.
[22]
Lipton, R. J., Rose, D. J., and Tarjan, R. E. Generalized nested dissection. SIAM J. Numer. Anal. 16, 2 (1979), 346--358.
[23]
Lipton, R. J., and Tarjan, R. E. Applications of a planar separator theorem. SIAM J. Comput. 9, 3 (1980), 615--627.
[24]
Liu, Y. A., and Stoller, S. D. Founded semantics and constraint semantics of logic rules. J. Log. Comput. 30, 8 (2020), 1609--1668.
[25]
Liu, Y. A., and Stoller, S. D. Recursive rules with aggregation: A simple unified semantics, 2020.
[26]
Nielson, F., Nielson, H. R., and Hankin, C. Principles of program analysis. Springer-Verlag, Berlin, 1999.
[27]
Rockt¨aschel, T. Einsum is all you need - Einstein summation in deep learning. https://rockt.github.io/2018/04/30/einsum.
[28]
Rote, G. Path problems in graphs. In Computational graph theory, vol. 7 of Comput. Suppl. Springer, Vienna, 1990, pp. 155--189.
[29]
Scott, D., and Strachey, C. Toward a mathematical semantics for computer languages, 1971.
[30]
Shenoy, P. P., and Shafer, G. Axioms for probability and belief-function proagation. In UAI '88: Proceedings of the Fourth Annual Conference on Uncertainty in Artificial Intelligence, Minneapolis, MN, USA, July 10--12, 1988 (1988), R. D. Shachter, T. S. Levitt, L. N. Kanal, and J. F. Lemmer, Eds., North-Holland, pp. 169--198.
[31]
Vardi, M. Y. The complexity of relational query languages (extended abstract). In Proceedings of the 14th Annual ACM Symposium on Theory of Computing, May 5--7, 1982, San Francisco, California, USA (1982), H. R. Lewis, B. B. Simons, W. A. Burkhard, and L. H. Landweber, Eds., ACM, pp. 137--146.
[32]
Wang, Y. R., Khamis, M. A., Ngo, H. Q., Pichler, R., and Suciu, D. Optimizing recursive queries with progam synthesis. In SIGMOD '22: International Conference on Management of Data, Philadelphia, PA, USA, June 12 - 17, 2022 (2022), Z. Ives, A. Bonifati, and A. E. Abbadi, Eds., ACM, pp. 79--93.
[33]
Zaharia, M., Xin, R. S., Wendell, P., Das, T., Armbrust, M., Dave, A., Meng, X., Rosen, J., Venkataraman, S., Franklin, M. J., Ghodsi, A., Gonzalez, J., Shenker, S., and Stoica, I. Apache spark: a unified engine for big data processing. Commun. ACM 59, 11 (2016), 56--65.
[34]
Zaniolo, C., Yang, M., Interlandi, M., Das, A., Shkapsky, A., and Condie, T. Declarative bigdata algorithms via aggregates and relational database dependencies. In Proceedings of the 12th Alberto Mendelzon International Workshop on Foundations of Data Management, Cali, Colombia, May 21--25, 2018 (2018), D. Olteanu and B. Poblete, Eds., vol. 2100 of CEUR Workshop Proceedings, CEUR-WS.org.
Recommendations
Convergence of datalog over (Pre-) Semirings
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 ...
Convergence of Datalog over (Pre-) Semirings
PODS '22: Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database SystemsRecursive 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 ...
Inductive *-semirings
Words, languages and combinatoricsOne of the most well-known induction principles in computer science is the fixed point induction rule, or least pre-fixed point rule. Inductive *-semirings are partially ordered semirings equipped with a star operation satisfying the fixed point ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
March 2023
118 pages
ISSN:0163-5808
DOI:10.1145/3604437
- Editors:
- Rada Chirkova,
- Vanessa Braganholo,
- Wim Martens,
- Manos Athanassoulis,
- Marcelo Arenas,
- Marianne Winslett,
- Susan B. Davidson,
- Lyublena Antova,
- Aaron J. Elmore,
- Kyriakos Mouratidis,
- Dan Olteanu,
- Immanuel Trummer,
- Yannis Velegrakis,
- Renata Borovica-Gajic,
- Tamer Özsu,
- Pınar Tözün,
- Wook-Shin Han,
- Kenneth Ross,
- Alfons Kemper,
- Samuel Madden
Copyright © 2023 Copyright is held by the owner/author(s).
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 08 June 2023
Published in SIGMOD Volume 52, Issue 1
Check for updates
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 52Total Downloads
- Downloads (Last 12 months)35
- Downloads (Last 6 weeks)3
Reflects downloads up to 20 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in