{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T22:10:08Z","timestamp":1755900608845,"version":"3.44.0"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,5,10]],"date-time":"2024-05-10T00:00:00Z","timestamp":1715299200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100006374","name":"Deutscher Akademischer Austauschdienst","doi-asserted-by":"publisher","award":["57616814"],"award-info":[{"award-number":["57616814"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006374","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["389792660,390696704"],"award-info":[{"award-number":["389792660,390696704"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006374","name":"Bundesministerium f\u00fcr Bildung und Forschung","doi-asserted-by":"publisher","award":["ScaDS.AI"],"award-info":[{"award-number":["ScaDS.AI"]}],"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,5,10]]},"abstract":"<jats:p>The chase is a widely implemented approach to reason with tuple-generating dependencies (tgds), used in data exchange, data integration, and ontology-based query answering. However, it is merely a semi-decision procedure, which may fail to terminate. Many decidable conditions have been proposed for tgds to ensure chase termination, typically by forbidding some kind of \"cycle'' in the chase process. We propose a new criterion that explicitly allows some such cycles, and yet ensures termination of the standard chase under reasonable conditions. This leads to new decidable fragments of tgds that are not only syntactically more general but also strictly more expressive than the fragments defined by prior acyclicity conditions. Indeed, while known terminating fragments are restricted to PTime data complexity, our conditions yield decidable languages for any k- ExpTime. We further refine our syntactic conditions to obtain fragments of tgds for which an optimised chase procedure decides query entailment in PSpace or k- ExpSpace, respectively.<\/jats:p>","DOI":"10.1145\/3651594","type":"journal-article","created":{"date-parts":[[2024,5,14]],"date-time":"2024-05-14T08:32:13Z","timestamp":1715675533000},"page":"1-17","source":"Crossref","is-referenced-by-count":0,"title":["Chase Termination Beyond Polynomial Time"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3115-7492","authenticated-orcid":false,"given":"Philipp","family":"Hanisch","sequence":"first","affiliation":[{"name":"Knowledge-Based Systems Group, TU Dresden, Dresden, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9172-2601","authenticated-orcid":false,"given":"Markus","family":"Kr\u00f6tzsch","sequence":"additional","affiliation":[{"name":"Knowledge-Based Systems Group, TU Dresden, Dresden, Germany"}]}],"member":"320","published-online":{"date-parts":[[2024,5,14]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/320083.320091"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/320107.320112"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21542-6_21"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2011.03.002"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1634.1636"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3034796"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733004.2733028"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.24963\/kr.2021\/14"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3517804.3524146"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/3611479.3611493"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2012.08.002"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/773153.773179"},{"key":"e_1_2_2_13_1","volume-title":"Proc. 26th Int. Joint Conf. on Artificial Intelligence (IJCAI'17)","author":"Carral David","year":"2017","unstructured":"David Carral, Irina Dragoste, and Markus Kr\u00f6 tzsch. 2017. Restricted Chase (Non)Termination for Existential Rules with Disjunctions. In Proc. 26th Int. Joint Conf. on Artificial Intelligence (IJCAI'17), , Carles Sierra (Ed.). ijcai.org, 922--928."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2019\/225"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.24963\/kr.2022\/11"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/2566972.2566991"},{"key":"e_1_2_2_17_1","volume-title":"LFP. In Proc. 35th Int. Colloquium on Automata, Languages, and Programming (ICALP'08)","volume":"171","author":"Dawar Anuj","year":"2008","unstructured":"Anuj Dawar and Stephan Kreutzer. 2008. On Datalog vs. LFP. In Proc. 35th Int. Colloquium on Automata, Languages, and Programming (ICALP'08); Part II (LNCS, Vol. 5126), , Luca Aceto, Ivan Damg\u00e5rd, Leslie Ann Goldberg, Magn\u00fa s M. Halld\u00f3 rsson, Anna Ing\u00f3 lfsd\u00f3 ttir, and Igor Walukiewicz (Eds.). Springer, 160--171."},{"volume-title":"Proc. 27th Symposium on Principles of Database Systems (PODS'08)","author":"Deutsch Alin","key":"e_1_2_2_18_1","unstructured":"Alin Deutsch, Alan Nash, and Jeffrey B. Remmel. 2008. The Chase Revisited. In Proc. 27th Symposium on Principles of Database Systems (PODS'08), Maurizio Lenzerini and Domenico Lembo (Eds.). ACM, 149--158."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36285-1_15"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-21541-4_10"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.10.033"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2022\/365"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733004.2733031"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43951-7_25"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/20M1377035"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.3233\/FI-2018-1627"},{"key":"e_1_2_2_27_1","unstructured":"Philipp Hanisch and Markus Kr\u00f6tzsch. 2024. Chase Termination Beyond Polynomial Time. arxiv: 2403.16712 [cs.DB]"},{"key":"e_1_2_2_28_1","volume-title":"Proc. 22nd Int. Joint Conf. on Artificial Intelligence (IJCAI'11)","author":"Kr\u00f6tzsch Markus","year":"2011","unstructured":"Markus Kr\u00f6tzsch and Sebastian Rudolph. 2011. Extending Decidable Existential Rules by Joining Acyclicity and Guardedness. In Proc. 22nd Int. Joint Conf. on Artificial Intelligence (IJCAI'11), , Toby Walsh (Ed.). AAAI Press\/IJCAI, 963--968."},{"key":"e_1_2_2_29_1","volume-title":"Proc. 22nd Int. Conf. on Database Theory (ICDT'19)","volume":"17","author":"Kr\u00f6tzsch Markus","year":"2019","unstructured":"Markus Kr\u00f6tzsch, Maximilian Marx, and Sebastian Rudolph. 2019. The Power of the Terminating Chase. In Proc. 22nd Int. Conf. on Database Theory (ICDT'19) (LIPIcs, Vol. 127), , Pablo Barcel\u00f3 and Marco Calautti (Eds.). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 3:1--3:17."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/320107.320115"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559795.1559799"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICDT.2022.13"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00778-013-0333-Y"},{"key":"e_1_2_2_34_1","volume-title":"Proc. 22nd Int. Conf. on Database Theory (ICDT'19)","author":"Thomazo Michel Micha\u00eb","year":"2019","unstructured":"Micha\u00eb l Thomazo Michel Lecl\u00e9 re, Marie-Laure Mugnier and Federico Ulliana. 2019. On Chase Termination for Linear Existential Rules. In Proc. 22nd Int. Conf. on Database Theory (ICDT'19). Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik."},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-25010-6_1"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/2832581.2832694"},{"key":"e_1_2_2_37_1","volume-title":"Proc. 25th Int. Joint Conf. on Artificial Intelligence (IJCAI'15)","author":"Rudolph Sebastian","year":"2016","unstructured":"Sebastian Rudolph and Micha\u00eb l Thomazo. 2016. Expressivity of Datalog Variants - Completing the Picture. In Proc. 25th Int. Joint Conf. on Artificial Intelligence (IJCAI'15), , Subbarao Kambhampati (Ed.). AAAI Press, 1230--1236."},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-94205-6_44"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v29i1.9404"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651594","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3651594","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T21:40:25Z","timestamp":1755898825000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651594"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,10]]},"references-count":39,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,5,10]]}},"alternative-id":["10.1145\/3651594"],"URL":"https:\/\/doi.org\/10.1145\/3651594","relation":{},"ISSN":["2836-6573"],"issn-type":[{"type":"electronic","value":"2836-6573"}],"subject":[],"published":{"date-parts":[[2024,5,10]]}}}