{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,2]],"date-time":"2026-10-02T07:52:23Z","timestamp":1790927543128,"version":"4.1.0"},"reference-count":75,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T00:00:00Z","timestamp":1710201600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100006374","name":"NSF","doi-asserted-by":"publisher","award":["2314527,2312195,2109922"],"award-info":[{"award-number":["2314527,2312195,2109922"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,3,12]]},"abstract":"<jats:p>Datalog is a declarative programming language that has gained popularity in various domains due to its simplicity, expressiveness, and efficiency. But \"pure\" Datalog is limited to monotone queries, and cannot be used in most practical applications. For that reason, newer systems are relaxing the language by allowing non-monotone queries to be freely combined with recursion. But by departing from the elegant fixpoint semantics of pure datalog, these systems often result in inefficient query execution, for example they perform redundant computations, or use redundant storage. In this paper, we propose Temporel, a system that allows recursion to be freely combined with non-monotone operators. Temporel optimizes the program by compiling it into a novel intermediate representation that we call TempoDL. Our experimental results show that our system outperforms a state-of-the-art Datalog engine as well as a vectorized and a compiled in-memory database system for a wide range of applications from machine learning to graph processing.<\/jats:p>","DOI":"10.1145\/3639271","type":"journal-article","created":{"date-parts":[[2024,3,26]],"date-time":"2024-03-26T18:51:32Z","timestamp":1711479092000},"page":"1-27","source":"Crossref","is-referenced-by-count":5,"title":["Optimizing Nested Recursive Queries"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9062-759X","authenticated-orcid":false,"given":"Amir","family":"Shaikhha","sequence":"first","affiliation":[{"name":"University of Edinburgh, Edinburgh, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4144-0868","authenticated-orcid":false,"given":"Dan","family":"Suciu","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, WA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-5502-869X","authenticated-orcid":false,"given":"Maximilian","family":"Schleich","sequence":"additional","affiliation":[{"name":"RelationalAI, Berkeley, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3498-4744","authenticated-orcid":false,"given":"Hung","family":"Ngo","sequence":"additional","affiliation":[{"name":"RelationalAI, Berkeley, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,3,26]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"[n.d.]. Recursion - RAI Documentation. https:\/\/docs.relational.ai\/rel\/concepts\/recursion. Accessed: 2023-03--30."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 1987 Symposium on Logic Programming","author":"Abadi Mart\u00edn","year":"1987","unstructured":"Mart\u00edn Abadi and Zohar Manna. 1987. Temporal Logic Programming. In Proceedings of the 1987 Symposium on Logic Programming, San Francisco, California, USA, August 31 - September 4, 1987. IEEE-CS, 4--16."},{"key":"e_1_2_1_3_1","volume-title":"Foundations of Databases","author":"Abiteboul Serge","unstructured":"Serge Abiteboul, Richard Hull, and Victor Vianu. 1995. Foundations of Databases. Addison-Wesley. http:\/\/webdam.inria.fr\/Alice\/"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2742796"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ECOOP.2016.2"},{"key":"e_1_2_1_6_1","volume-title":"Gtgraph: A synthetic graph generator suite.","author":"Bader David A","year":"2006","unstructured":"David A Bader and Kamesh Madduri. 2006. Gtgraph: A synthetic graph generator suite. (2006)."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0743--1066(87)90004--5"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/6012.15399"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/PACT.2004.10018"},{"key":"e_1_2_1_10_1","unstructured":"Luigi Bellomarini Markus Nissl and Emanuel Sallinger. 2021. Monotonic Aggregation for Temporal Datalog. In Proceedings of the 15th International Rule Challenge 7th Industry Track and 5th Doctoral Consortium @ RuleMLRR 2021 co-located with 17th Reasoning Web Summer School (RW 2021) and 13th DecisionCAMP 2021 as part of Declarative AI 2021 Leuven Belgium (virtual due to Covid-19 pandemic) 8 - 15 September 2021 (CEUR Workshop Proceedings) Ahmet Soylu Alireza Tamaddoni-Nezhad Nikolay Nikolov Ioan Toma Anna Fensel and Joost Vennekens (Eds.) Vol. 2956. CEUR-WS.org. http:\/\/ceur-ws.org\/Vol-2956\/paper30.pdf"},{"key":"e_1_2_1_11_1","volume-title":"12th Conference on Innovative Data Systems Research, CIDR 2022","author":"Blacher Mark","year":"2022","unstructured":"Mark Blacher, Joachim Giesen, S\u00f6ren Laue, Julien Klaus, and Viktor Leis. 2022. Machine Learning, Linear Algebra, and More: Is SQL All You Need?. In 12th Conference on Innovative Data Systems Research, CIDR 2022, Chaminade, CA, USA, January 9--12, 2022. www.cidrdb.org. https:\/\/www.cidrdb.org\/cidr2022\/papers\/p17-blacher.pdf"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/3298239.3298397"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1640089.1640108"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.3233\/FI-1994--2144"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/298514.298589"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2391229.2391230"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/231379.231399"},{"key":"e_1_2_1_18_1","unstructured":"MLIR Developers. 2023. MLIR affine dialect. https:\/\/mlir.llvm.org\/docs\/Dialects\/Affine\/. Accessed: 2023--10-03."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389707"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--642--24206--9_11"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/3311880.3311886"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01407931"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/113413.113427"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3542700.3542715"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3477602"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/504077.504079"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3324959"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/11785477_2"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1860702.1860704"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3384678"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457272"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 13th Conference on Innovative Data Systems Research.","author":"Hirn Denis","year":"2023","unstructured":"Denis Hirn and Torsten Grust. 2023. A Fix for the Fixation on Fixpoints. In Proceedings of the 13th Conference on Innovative Data Systems Research."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989456"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--319--41540--6_23"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 1991 International Symposium","author":"David","year":"1991","unstructured":"David B. Kemp and Peter J. Stuckey. 1991. Semantics of Logic Programs with Aggregates. In Logic Programming, Proceedings of the 1991 International Symposium, San Diego, California, USA, Oct. 28 - Nov 1, 1991, Vijay A. Saraswat and Kazunori Ueda (Eds.). MIT Press, 387--401."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3517804.3524140"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3552490.3552492"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00961871"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO51591.2021.9370308"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exac072"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1592761.1592785"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3213846.3213847"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/93597.98734"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/191839.191860"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.5555\/645916.671834"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522738"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.14778\/2002938.2002940"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.05.014"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304--3975(92)90013--6"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.5441\/002\/edbt.2017.09"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3150211"},{"key":"e_1_2_1_52_1","volume-title":"Demand Interprocedural Program Analysis Using Logic Databases","author":"Reps Thomas W.","unstructured":"Thomas W. Reps. 1993. Demand Interprocedural Program Analysis Using Logic Databases. In Applications of Logic Databases (The Kluwer International Series in Engineering and Computer Science 296), Raghu Ramakrishnan (Ed.). Kluwer, 163--196."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v32i1.11537"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.5555\/200616.200631"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/137097.137852"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588717"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3538712.3538746"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2015.2405562"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/3578360.3580264"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796818000102"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/3527333"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183653"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915244"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915229"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113340"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2018.2857721"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2019\/261"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824052"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-021-00665--6"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389712"},{"key":"e_1_2_1_71_1","volume-title":"Hung Q. Ngo, Reinhard Pichler, and Dan Suciu.","author":"Wang Yisu Remy","year":"2022","unstructured":"Yisu Remy Wang, Mahmoud Abo Khamis, Hung Q. Ngo, Reinhard Pichler, and Dan Suciu. 2022. Optimizing Recursive Queries with Program Synthesis. CoRR abs\/2202.10390 (2022). arXiv:2202.10390 https:\/\/arxiv.org\/abs\/2202.10390"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167--8191(95)00069-0"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--642--32925--8_18"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1007\/3--540--57530--8_13"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068417000436"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639271","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3639271","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T15:13:53Z","timestamp":1755789233000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639271"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,12]]},"references-count":75,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3,12]]}},"alternative-id":["10.1145\/3639271"],"URL":"https:\/\/doi.org\/10.1145\/3639271","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,12]]}}}