{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T00:41:41Z","timestamp":1777941701033,"version":"3.51.4"},"reference-count":47,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2024,10,28]],"date-time":"2024-10-28T00:00:00Z","timestamp":1730073600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Theory and Practice of Logic Programming"],"published-print":{"date-parts":[[2025,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>DatalogMTL is an extension of Datalog with metric temporal operators that has found an increasing number of applications in recent years. Reasoning in DatalogMTL is, however, of high computational complexity, which makes reasoning in modern data-intensive applications challenging. In this paper we present a practical reasoning algorithm for the full DatalogMTL language, which we have implemented in a system called MeTeoR. Our approach effectively combines an optimised (but generally non-terminating) materialisation (a.k.a. forward chaining) procedure, which provides scalable behaviour, with an automata-based component that guarantees termination and completeness. To ensure favourable scalability of the materialisation component, we propose a novel semina\u00efve materialisation procedure for DatalogMTL enjoying the non-repetition property, which ensures that each rule instance will be applied at most once throughout its entire execution. Moreover, our materialisation procedure is enhanced with additional optimisations which further reduce the number of redundant computations performed during materialisation by disregarding rules as soon as it is certain that they cannot derive new facts in subsequent materialisation steps. Our extensive evaluation supports the practicality of our approach.<\/jats:p>","DOI":"10.1017\/s1471068424000164","type":"journal-article","created":{"date-parts":[[2024,10,28]],"date-time":"2024-10-28T08:36:37Z","timestamp":1730104597000},"page":"225-255","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":2,"title":["Practical Reasoning in DatalogMTL"],"prefix":"10.1017","volume":"25","author":[{"given":"DINGMIN","family":"WANG","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2909-5923","authenticated-orcid":false,"given":"BERNARDO","family":"CUENCA GRAU","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"PRZEMYS\u0141AW A.","family":"WA\u0141\u0228GA","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1701-9640","authenticated-orcid":false,"given":"PAN","family":"HU","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2024,10,28]]},"reference":[{"key":"S1471068424000164_ref18","doi-asserted-by":"publisher","DOI":"10.1109\/69.43410"},{"key":"S1471068424000164_ref13","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1.11229"},{"key":"S1471068424000164_ref8","doi-asserted-by":"crossref","unstructured":"Bellomarini, L. , Blasi, L. , Nissl, M. and Sallinger, E. 2022, The temporal Vadalog system. In International Joint Conference on Rules and Reasoning, 130\u2013145.","DOI":"10.1007\/978-3-031-21541-4_9"},{"key":"S1471068424000164_ref12","doi-asserted-by":"crossref","unstructured":"Brandt, S. , Kalayc\u0131, E. G. , Kontchakov, R. , Ryzhikov, V. , Xiao, G. and Zakharyaschev, M. 2017. Ontology-based data access with a horn fragment of metric temporal logic. In Proc. of the AAAI Conference on Artificial Intelligence, 1070\u20131076.","DOI":"10.1609\/aaai.v31i1.10696"},{"key":"S1471068424000164_ref31","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2018.12.004"},{"key":"S1471068424000164_ref25","volume-title":"Description Logics","author":"Kikot","year":"2018"},{"key":"S1471068424000164_ref2","first-page":"1","volume-title":"Theory and Practice of Logic Programming","author":"Aguado","year":"2021"},{"key":"S1471068424000164_ref19","doi-asserted-by":"crossref","unstructured":"Chomicki, J. and Imielinski, T. 1988. Temporal deductive databases and infinite objects. In Proc. of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 61\u201373.","DOI":"10.1145\/308386.308416"},{"key":"S1471068424000164_ref16","doi-asserted-by":"crossref","unstructured":"Carral, D. , Dragoste, I. , Gonz\u00e1lez, L. , Jacobs, C. J. H. , Kr\u00f6tzsch, M. and Urbani, J. 2019. Vlog: A rule engine for knowledge graphs. In International Semantic Web Conference, 19\u201335.","DOI":"10.1007\/978-3-030-30796-7_2"},{"key":"S1471068424000164_ref1","volume-title":"Foundations of Databases","author":"Abiteboul","year":"1995"},{"key":"S1471068424000164_ref24","doi-asserted-by":"crossref","unstructured":"Kalayc\u0131, E. G. , Xiao, G. , Ryzhikov, V. , Kalayci, T. E. and Calvanese, D. 2018. Ontop-temporal: a tool for ontology-based query answering over temporal data. In Proc. of the 27th ACM International Conference on Information and Knowledge Management, 1927\u20131930.","DOI":"10.1145\/3269206.3269230"},{"key":"S1471068424000164_ref29","doi-asserted-by":"publisher","DOI":"10.1175\/1520-0442(2002)015<3237:ALTHBD>2.0.CO;2"},{"key":"S1471068424000164_ref37","doi-asserted-by":"crossref","unstructured":"Wa\u0142\u0229ga, P. A. , Cuenca Grau, B. , Kaminski, M. and Kostylev, E. V. 2019a. DatalogMTL: computational complexity and expressive power. In International Joint Conferences on Artificial Intelligence, 1886\u20131892.","DOI":"10.24963\/ijcai.2019\/261"},{"key":"S1471068424000164_ref4","unstructured":"Artale, A. , Kontchakov, R. , Kovtunova, A. , Ryzhikov, V. , Wolter, F. and Zakharyaschev, M. 2015. First-order rewritability of temporal ontology-mediated queries. In Proc. of the International Joint Conference on Artificial Intelligence, 25 July 2015, 2706\u20132712."},{"key":"S1471068424000164_ref36","unstructured":"Thost, V. 2018. Metric temporal extensions of DL-Lite and interval-rigid names. In Proc. of the International Conference on Principles of Knowledge Representation and Reasoning, 665\u2013666."},{"key":"S1471068424000164_ref38","doi-asserted-by":"crossref","unstructured":"Wa\u0142\u0229ga, P. A. , Cuenca Grau, B. , Kaminski, M. and Kostylev, E. V. 2020. DatalogMTL over the integer timeline. In Proc. of the International Conference on Principles of Knowledge Representation and Reasoning, 768\u2013777.","DOI":"10.24963\/kr.2020\/79"},{"key":"S1471068424000164_ref39","doi-asserted-by":"crossref","unstructured":"Wa\u0142\u0229ga, P. A. , Cuenca Grau, B. , Kaminski, M. and Kostylev, E. V. 2021. Tractable fragments of Datalog with metric temporal operators. In Proc. of the AAAI Conference on Artificial Intelligence, 1919\u20131925.","DOI":"10.24963\/ijcai.2020\/266"},{"key":"S1471068424000164_ref14","first-page":"1","volume-title":"Reasoning Web","author":"Bry","year":"2007"},{"key":"S1471068424000164_ref35","doi-asserted-by":"crossref","unstructured":"Ryzhikov, V. , Wa\u0142\u0229ga, P. A. and Zakharyaschev, M. 2019a. Data complexity and rewritability of ontology-mediated queries in metric temporal logic under the event-based semantics. In International Joint Conferences on Artificial Intelligence, 1851\u20131857.","DOI":"10.24963\/ijcai.2019\/256"},{"key":"S1471068424000164_ref45","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-21541-4_12"},{"key":"S1471068424000164_ref27","doi-asserted-by":"crossref","unstructured":"Koopmann, P. 2019. Ontology-based query answering for probabilistic temporal data. In Proc. of the AAAI Conference on Artificial Intelligence, 2903\u20132910.","DOI":"10.1609\/aaai.v33i01.33012903"},{"key":"S1471068424000164_ref9","article-title":"Query evaluation in DatalogMTL \u2013 taming infinite query results","author":"Bellomarini","year":"2021","journal-title":"CoRR abs\/2109.10691"},{"key":"S1471068424000164_ref15","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068420000307"},{"key":"S1471068424000164_ref21","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-29026-9_1"},{"key":"S1471068424000164_ref32","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v28i1.8730"},{"key":"S1471068424000164_ref33","unstructured":"Nissl, M. and Sallinger, E. 2022. Modelling smart contracts with datalogmtl. In Proc. of the Workshops of the EDBT\/ICDT."},{"key":"S1471068424000164_ref6","volume-title":"Principles of Model Checking","author":"Baier","year":"2008"},{"key":"S1471068424000164_ref7","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2018.04.003"},{"key":"S1471068424000164_ref40","doi-asserted-by":"crossref","unstructured":"Wa\u0142\u0229ga, P. A. , Kaminski, M. and Cuenca Grau, B. 2019b. Reasoning over streaming data in metric temporal Datalog. In Proc. of the AAAI Conference on Artificial Intelligence, 3092\u20133099.","DOI":"10.1609\/aaai.v33i01.33013092"},{"key":"S1471068424000164_ref34","doi-asserted-by":"crossref","unstructured":"Raheb, K. E. , Mailis, T. , Ryzhikov, V. , Papapetrou, N. and Ioannidis, Y. E. 2017. Balonse: Temporal aspects of dance movement and its ontological representation. In European Semantic Web Conference, 49\u201364.","DOI":"10.1007\/978-3-319-58451-5_4"},{"key":"S1471068424000164_ref41","doi-asserted-by":"crossref","unstructured":"Wa\u0142\u0229ga, P. A. , Tena Cucala, D. J. , Kostylev, E. V. and Cuenca Grau, B. 2021. DatalogMTL with negation under stable models semantics. In Proc. of the International Conference on Principles of Knowledge Representation and Reasoning, 609\u2013618.","DOI":"10.24963\/kr.2021\/58"},{"key":"S1471068424000164_ref43","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1.14040"},{"key":"S1471068424000164_ref3","doi-asserted-by":"publisher","DOI":"10.1613\/jair.516"},{"key":"S1471068424000164_ref30","doi-asserted-by":"crossref","unstructured":"Mori, M. , Papotti, P. , Bellomarini, L. and Giudice, O. 2022. Neural machine translation for fact-checking temporal claims. In Proc. of the Fifth Fact Extraction and VERification Workshop, 78\u201382.","DOI":"10.18653\/v1\/2022.fever-1.8"},{"key":"S1471068424000164_ref28","doi-asserted-by":"publisher","DOI":"10.1007\/BF01995674"},{"key":"S1471068424000164_ref44","doi-asserted-by":"crossref","unstructured":"Wang, D. , Hu, P. , Wa\u0142\u0229ga, P. A. and Grau, B. C. 2022a. MeTeoR: Practical reasoning in Datalog with metric temporal operators. In Proc. of the AAAI Conference on Artificial Intelligence, 5906\u20135913.","DOI":"10.1609\/aaai.v36i5.20535"},{"key":"S1471068424000164_ref46","unstructured":"Yang, J. 2022. Translation of datalogMTL into PLTL, M.S. thesis, University of Oxford, UK."},{"key":"S1471068424000164_ref10","doi-asserted-by":"crossref","unstructured":"Bellomarini, L. , Nissl, M. and Sallinger, E. 2022. iTemporal: An extensible temporal benchmark generator. In 2022 IEEE 38th International Conference on Data Engineering, 2021\u20132033.","DOI":"10.1109\/ICDE53745.2022.00197"},{"key":"S1471068424000164_ref42","doi-asserted-by":"crossref","unstructured":"Wa\u0142\u0229ga, P. A. , Zawidzki, M. and Cuenca Grau, B. 2021. Finitely materialisable Datalog programs with metric temporal operators. In Proc. of the International Conference on Principles of Knowledge Representation and Reasoning, 619\u2013628.","DOI":"10.24963\/kr.2021\/59"},{"key":"S1471068424000164_ref47","doi-asserted-by":"crossref","unstructured":"Zhou, X. , Wang, F. and Zaniolo, C. 2006. Efficient temporal coalescing query support in relational database systems. In International Conference on Database and Expert Systems Applications, 676\u2013686.","DOI":"10.1007\/11827405_66"},{"key":"S1471068424000164_ref23","unstructured":"Guti\u00e9rrez-Basulto, V. , Jung, J. C. and Ozaki, A. 2016. On metric temporal description logics. In 22nd European Conference on Artificial Intelligence, 837\u2013845."},{"key":"S1471068424000164_ref26","unstructured":"Kontchakov, R. , Pandolfo, L. , Pulina, L. , Ryzhikov, V. and Zakharyaschev, M. 2016. Temporal and spatial OBDA with many-dimensional Halpern-Shoham logic. In Proc. of the International Joint Conference on Artificial Intelligence, 1160\u20131166."},{"key":"S1471068424000164_ref17","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-08867-9_22"},{"key":"S1471068424000164_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-66167-4_4"},{"key":"S1471068424000164_ref20","doi-asserted-by":"crossref","unstructured":"Cucala, D. J. T. , Wa\u0142\u0229ga, P. A. , Cuenca Grau, B. and Kostylev, E. V. 2021. Stratified negation in Datalog with metric temporal operators. In Proc. of the Thirty-Third AAAI Conference on Artificial Intelligence, 6488\u20136495.","DOI":"10.1609\/aaai.v35i7.16804"},{"key":"S1471068424000164_ref22","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2005.06.005"},{"key":"S1471068424000164_ref11","doi-asserted-by":"crossref","unstructured":"Bellomarini, L. , Sallinger, E. and Gottlob, G. 2018. The Vadalog system: Datalog-based reasoning for knowledge graphs. In Proc. of the VLDB Endowment, 975\u2013987.","DOI":"10.14778\/3213880.3213888"}],"container-title":["Theory and Practice of Logic Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1471068424000164","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,9]],"date-time":"2025-06-09T13:40:32Z","timestamp":1749476432000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068424000164\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,28]]},"references-count":47,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["S1471068424000164"],"URL":"https:\/\/doi.org\/10.1017\/s1471068424000164","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"value":"1471-0684","type":"print"},{"value":"1475-3081","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,10,28]]},"assertion":[{"value":"\u00a9 The Author(s), 2024. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (https:\/\/creativecommons.org\/licenses\/by\/4.0\/), which permits unrestricted re-use, distribution and reproduction, provided the original article is properly cited.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}