{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,31]],"date-time":"2026-01-31T14:22:04Z","timestamp":1769869324270,"version":"3.49.0"},"reference-count":31,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2023,9,21]],"date-time":"2023-09-21T00:00:00Z","timestamp":1695254400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["www.mdpi.com"],"crossmark-restriction":true},"short-container-title":["Software"],"abstract":"<jats:p>The core reasoning task for datalog engines is materialization, the evaluation of a datalog program over a database alongside its physical incorporation into the database itself. The de-facto method of computing is through the recursive application of inference rules. Due to it being a costly operation, it is a must for datalog engines to provide incremental materialization; that is, to adjust the computation to new data instead of restarting from scratch. One of the major caveats is that deleting data is notoriously more involved than adding since one has to take into account all possible data that has been entailed from what is being deleted. Differential dataflow is a computational model that provides efficient incremental maintenance, notoriously with equal performance between additions and deletions, and work distribution of iterative dataflows. In this paper, we investigate the performance of materialization with three reference datalog implementations, out of which one is built on top of a lightweight relational engine, and the two others are differential-dataflow and non-differential versions of the same rewrite algorithm with the same optimizations. Experimental results suggest that monotonic aggregation is more powerful than ascenting merely the powerset lattice.<\/jats:p>","DOI":"10.3390\/software2030020","type":"journal-article","created":{"date-parts":[[2023,9,22]],"date-time":"2023-09-22T05:32:45Z","timestamp":1695360765000},"page":"427-446","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["RETRACTED: A Differential Datalog Interpreter"],"prefix":"10.3390","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7171-9248","authenticated-orcid":false,"given":"Matthew","family":"Stephenson","sequence":"first","affiliation":[{"name":"Computer Science Department, Stanford University, Stanford, CA 94305-9045, USA"}]}],"member":"1968","published-online":{"date-parts":[[2023,9,21]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1109\/69.43410","article-title":"What you Always Wanted to Know About Datalog (And Never Dared to Ask)","volume":"1","author":"Ceri","year":"1989","journal-title":"Knowl. Data Eng. IEEE Trans."},{"key":"ref_2","unstructured":"Gupta, A.K., and Mumick, I.S. (1999). Incremental Maintenance of Recursive Views: A Survey, IEEE."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Abadi, M., McSherry, F., and Plotkin, G. (2015, January 11\u201318). Foundations of Differential Dataflow. Proceedings of the International Conference on Foundations of Software Science and Computation Structures, London, UK.","DOI":"10.1007\/978-3-662-46678-0_5"},{"key":"ref_4","unstructured":"Ryzhyk, L., and Budiu, M. (2019, January 4\u20135). Differential Datalog. Proceedings of the Datalog, 3rd International Workshop on the Resurgence of Datalog in Academia and Industry, Philadelphia, PA, USA."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Scholz, B., Jordan, H., Subotic, P., and Westmann, T. (2016, January 13\u201317). On fast large-scale program analysis in Datalog. Proceedings of the 25th International Conference on Compiler Construction, Seoul, Republic of Korea.","DOI":"10.1145\/2892208.2892226"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"1601","DOI":"10.14778\/3587136.3587137","article-title":"DBSP: Automatic Incremental View Maintenance for Rich Query Languages","volume":"16","author":"Budiu","year":"2022","journal-title":"Proc. VLDB Endow."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Jordan, H., Subotic, P., Zhao, D., and Scholz, B. (2019, January 16\u201320). A specialized B-tree for concurrent datalog evaluation. Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming, Washington, DC, USA.","DOI":"10.1145\/3293883.3295719"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Arch, S., Hu, X., Zhao, D., Subotic, P., and Scholz, B. (2022, January 21\u201323). Building a Join Optimizer for Souffl\u00e9. Proceedings of the International Workshop\/Symposium on Logic-based Program Synthesis and Transformation, Tbilisi, Georgia.","DOI":"10.1007\/978-3-031-16767-6_5"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Nenov, Y., Piro, R., Motik, B., Horrocks, I., Wu, Z., and Banerjee, J. (2015, January 11\u201315). RDFox: A Highly-Scalable RDF Store. Proceedings of the 14th International Semantic Web Conference, Bethlehem, PA, USA.","DOI":"10.1007\/978-3-319-25010-6_1"},{"key":"ref_10","unstructured":"Zhu, J., Zhang, Z., Albarghouthi, A., Koutris, P., and Patel, J. (2018). Scaling-Up In-Memory Datalog Processing: Observations and Techniques. arXiv."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Wu, J., Wang, J., and Zaniolo, C. (2022, January 12\u201317). Optimizing Parallel Recursive Datalog Evaluation on Multicore Machines. Proceedings of the 2022 International Conference on Management of Data, Philadelphia, PA, USA.","DOI":"10.1145\/3514221.3517853"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Shkapsky, A., Yang, M., and Zaniolo, C. (2015, January 13\u201317). Optimizing recursive queries with monotonic aggregates in DeALS. Proceedings of the International Conference on Data Engineering, Seoul, Republic of Korea.","DOI":"10.1109\/ICDE.2015.7113340"},{"key":"ref_13","unstructured":"Shkapsky, A., Yang, M., Interlandi, M., Chiu, H., Condie, T., and Zaniolo, C. (July, January 26). Big Data Analytics with Datalog Queries on Spark. Proceedings of the International Conference on Management of Data, San Francisco, CA, USA."},{"key":"ref_14","unstructured":"Armbrust, M., Ghodsi, A., Zaharia, M., Xin, R., Lian, C., Huai, Y., Liu, D., Bradley, J., Meng, X., and Kaftan, T. (June, January 31). Spark SQL. Proceedings of the International Conference on Management of Data, Melbourne, VIC, Australia."},{"key":"ref_15","unstructured":"Imran, M., G\u00e9vay, G., and Markl, V. (2020, January 4). Distributed Graph Analytics with Datalog Queries in Flink. Proceedings of the 4th International Workshop, SFDI 2020, and 2nd International Workshop, LSGDA 2020, Held in Conjunction with VLDB 2020, Tokyo, Japan."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Rabl, T., Traub, J., Katsifodimos, A., and Markl, V. (2016). Apache Flink in current research. Inf. Technol., 58.","DOI":"10.1515\/itit-2016-0005"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"971","DOI":"10.1007\/s11280-021-00960-w","article-title":"Fast datalog evaluation for batch and stream graph processing","volume":"25","author":"Imran","year":"2022","journal-title":"World Wide Web"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1145\/362384.362685","article-title":"A Relational Model for Large Shared Data Banks","volume":"13","author":"Codd","year":"1970","journal-title":"Commun. ACM."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Fr\u00f6hlich, L. (2022). PostgreSQL, Carl Hanser Verlag.","DOI":"10.3139\/9783446473157.fm"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Christudas, B.A. (2019). MySQL. Practical Microservices Architectural Patterns, Springer.","DOI":"10.1007\/978-1-4842-4501-9"},{"key":"ref_21","unstructured":"Abiteboul, S., Hull, R., and Vianu, V. (1994). Foundations of Databases, Addison-Wesley."},{"key":"ref_22","unstructured":"Rucy, B., and Kramer, M. (2023, May 31). Available online: https:\/\/github.com\/brurucy\/shapiro."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Motik, B., Nenov, Y., Piro, R., and Horrocks, I. (2015, January 25\u201330). Incremental Update of Datalog Materialisation: The Backward\/Forward Algorithm. Proceedings of the AAAI Conference on Artificial Intelligence, Austin, TX, USA.","DOI":"10.1609\/aaai.v29i1.9409"},{"key":"ref_24","unstructured":"Gottlob, G., Lukasiewicz, T., and Pieris, A. (2014, January 20\u201324). Datalog+\/\u2212: Questions and Answers. Proceedings of the Fourteenth International Conference on Principles of Knowledge Representation and Reasoning, Vienna, Austria."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/j.artint.2012.08.002","article-title":"Towards more expressive ontology languages: The query answering problem","volume":"193","author":"Gottlob","year":"2012","journal-title":"Artif. Intell."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Baldazzi, T., Bellomarini, L., Sallinger, E., and Atzeni, P. (2021, January 13\u201315). Eliminating Harmful Joins in Warded Datalog+\/\u2212. Proceedings of the 5th International Joint Conference, RuleML+RR 2021, Leuven, Belgium.","DOI":"10.1007\/978-3-030-91167-6_18"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1145\/962446.962450","article-title":"Monadic datalog and the expressive power of languages for Web information extraction","volume":"51","author":"Gottlob","year":"2003","journal-title":"J. ACM"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"101528","DOI":"10.1016\/j.is.2020.101528","article-title":"Vadalog: A modern architecture for automated reasoning with large knowledge graphs","volume":"105","author":"Bellomarini","year":"2020","journal-title":"Inf. Syst."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1016\/j.websem.2005.06.005","article-title":"LUBM: A benchmark for OWL knowledge base systems","volume":"3","author":"Guo","year":"2005","journal-title":"J. Web Semant."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Grosof, B.N., Horrocks, I., Volz, R., and Decker, S. (2003, January 20\u201324). Description logic programs: Combining logic programs with description logic. Proceedings of the 12th international Conference on World Wide Web, Budapest, Hungary.","DOI":"10.2139\/ssrn.460986"},{"key":"ref_31","unstructured":"Bader, D.A., and Madduri, K. (2006). GTgraph: A Synthetic Graph Generator Suite, ResearchGate."}],"updated-by":[{"DOI":"10.3390\/software5010003","type":"retraction","label":"Retraction","source":"publisher","updated":{"date-parts":[[2023,9,21]],"date-time":"2023-09-21T00:00:00Z","timestamp":1695254400000}},{"DOI":"10.3390\/software3020011","type":"expression_of_concern","label":"Expression of concern","source":"retraction-watch","updated":{"date-parts":[[2024,5,5]],"date-time":"2024-05-05T00:00:00Z","timestamp":1714867200000},"record-id":"69042"},{"DOI":"10.3390\/software5010003","type":"retraction","label":"Retraction","source":"retraction-watch","updated":{"date-parts":[[2026,1,20]],"date-time":"2026-01-20T00:00:00Z","timestamp":1768867200000},"record-id":"69043"}],"container-title":["Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2674-113X\/2\/3\/20\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,21]],"date-time":"2026-01-21T09:23:14Z","timestamp":1768987394000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2674-113X\/2\/3\/20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,21]]},"references-count":31,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2023,9]]}},"alternative-id":["software2030020"],"URL":"https:\/\/doi.org\/10.3390\/software2030020","relation":{},"ISSN":["2674-113X"],"issn-type":[{"value":"2674-113X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,9,21]]}}}