{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T22:00:52Z","timestamp":1747173652629,"version":"3.40.5"},"reference-count":42,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2020,6,30]],"date-time":"2020-06-30T00:00:00Z","timestamp":1593475200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Theory and Practice of Logic Programming"],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The chase procedure for existential rules is an indispensable tool for several database applications, where its termination guarantees the decidability of these tasks. Most previous studies have focused on the skolem chase variant and its termination analysis. It is known that the restricted chase variant is a more powerful tool in termination analysis provided a database is given. But all-instance termination presents a challenge since the critical database and similar techniques do not work. In this paper, we develop a novel technique to characterize the activeness of all possible cycles of a certain length for the restricted chase, which leads to the formulation of a framework of parameterized classes of the finite restricted chase, called <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S1471068420000101_inline1.png\"\/><jats:tex-math>\n$k$-$\\mathsf{safe}(\\Phi)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> rule sets. This approach applies to any class of finite skolem chase identified with a condition of acyclicity. More generally, we show that the approach can be applied to the hierarchy of <jats:italic>bounded rule sets<\/jats:italic> previously only defined for the skolem chase. Experiments on a collection of ontologies from the web show the applicability of the proposed methods on real-world ontologies.<\/jats:p>","DOI":"10.1017\/s1471068420000101","type":"journal-article","created":{"date-parts":[[2020,6,30]],"date-time":"2020-06-30T07:50:21Z","timestamp":1593503421000},"page":"4-50","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["Restricted Chase Termination for Existential Rules: A Hierarchical Approach and Experimentation"],"prefix":"10.1017","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7618-094X","authenticated-orcid":false,"given":"ARASH","family":"KARIMI","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"HENG","family":"ZHANG","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JIA-HUAI","family":"YOU","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2020,6,30]]},"reference":[{"doi-asserted-by":"publisher","key":"S1471068420000101_ref28","DOI":"10.1016\/0012-365X(92)90282-K"},{"unstructured":"Baget, J.-F. 2004. Improving the forward chaining algorithm for conceptual graphs rules. In Proceedings of the Ninth International Conference on Principles of Knowledge Representation and Reasoning. AAAI Press, 407\u2013414.","key":"S1471068420000101_ref2"},{"unstructured":"Baget, J.-F. , Garreau, F. , Mugnier, M.-L. and Rocher, S. 2014a. Extending acyclicity notions for existential rules. In Proceedings of the 21st European Conference on Artificial Intelligence. IOS Press, 39\u201344.","key":"S1471068420000101_ref3"},{"unstructured":"Baget, J.-F. , Lecl\u00e8re, M. , Mugnier, M.-L. and Salvat, E. 2009. Extending decidable cases for rules with existential variables. In Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence, 677\u2013682.","key":"S1471068420000101_ref7"},{"unstructured":"Cali, A. , Gottlob, G. , Lukasiewicz, T. , Marnette, B. and Pieris, A. 2010. Datalog+\/-: A family of logical knowledge representation and query languages for new applications. In Proceedings of the Twenty-Fifth Annual IEEE Symposium on Logic in Computer Science. IEEE, 228\u2013242.","key":"S1471068420000101_ref15"},{"doi-asserted-by":"publisher","key":"S1471068420000101_ref24","DOI":"10.1016\/j.tcs.2004.10.033"},{"doi-asserted-by":"publisher","key":"S1471068420000101_ref40","DOI":"10.1016\/S0022-0000(70)80006-X"},{"unstructured":"Deutsch, A. , Nash, A. and Remmel, J. 2008. The chase revisited. In Proceedings of the Twenty-Seventh ACM Symposium on Principles of Database Systems. ACM, 149\u2013158.","key":"S1471068420000101_ref22"},{"doi-asserted-by":"publisher","key":"S1471068420000101_ref29","DOI":"10.1016\/0743-1066(95)00051-K"},{"unstructured":"Carral, D. , Feier, C. , Grau, B. C. , Hitzler, P. and Horrocks, I. 2014. EL-ifying ontologies. In Proceedings of the7th International Joint Conference on Automated Reasoning. LNCS, vol. 8562. Springer, 464\u2013479.","key":"S1471068420000101_ref18"},{"unstructured":"Grau, B. C. , Horrocks, I. , Kr\u00f6tzsch, M. , Kupke, C. , Magka, D. , Motik, B. and Wang, Z. 2013. Acyclicity notions for existential rules and their application to query answering in ontologies. Journal of Artificial Intelligence Research 47, 741\u2013808.","key":"S1471068420000101_ref27"},{"unstructured":"Matentzoglu, N. and Parsia, B. 2014. The Manchester OWL Corpus (MOWLCorp), original serialisation.","key":"S1471068420000101_ref37"},{"doi-asserted-by":"publisher","key":"S1471068420000101_ref26","DOI":"10.3233\/FI-2018-1627"},{"unstructured":"Beeri, C. and Vardi, M. Y. 1981. The implication problem for data dependencies. In Proceedings of the 8th International Colloquium on Automata, Languages, and Programming. LNCS, vol. 115. Springer, 73\u201385.","key":"S1471068420000101_ref9"},{"unstructured":"Rutenburg, V. 1986. Complexity of generalized graph coloring. In Proceedings of the International Symposium on Mathematical Foundations of Computer Science. LNCS, vol. 233. Springer, 573\u2013581.","key":"S1471068420000101_ref39"},{"unstructured":"Calautti, M. , Gottlob, G. and Pieris, A. 2015. Chase termination for guarded existential rules. In Proceedings of the 34th ACM Symposium on Principles of Database Systems. ACM, 91\u2013103.","key":"S1471068420000101_ref13"},{"unstructured":"Kr\u00f6tzsch, M. , Marx, M. and Rudolph, S. 2019. The power of the terminating chase. In Proceedings of the Twenty-Second International Conference on Database Theory. LIPIcs, vol. 127. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 3:1\u20133:17.","key":"S1471068420000101_ref42"},{"unstructured":"Fagin, R. , Kolaitis, P. G. , Miller, R. J. and Popa, L. 2003. Data exchange: Semantics and query answering. In Proceedings of the 9th International Conference on Database Theory. LNCS, vol. 2572. Springer, 207\u2013224.","key":"S1471068420000101_ref23"},{"unstructured":"Onet, A. 2013. The chase procedure and its applications in data exchange. In Data Exchange, Integration, and Streams. Dagstuhl Follow-Ups, vol. 5. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 1\u201337.","key":"S1471068420000101_ref38"},{"doi-asserted-by":"publisher","key":"S1471068420000101_ref10","DOI":"10.1145\/1634.1636"},{"volume-title":"Foundations of Databases: The Logical Level","year":"1995","author":"Abiteboul","key":"S1471068420000101_ref1"},{"unstructured":"Zhang, H. , Zhang, Y. and You, J.-H. 2015. Existential rule languages with finite chase: Complexity and expressiveness. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence. AAAI Press, 1678\u20131685.","key":"S1471068420000101_ref41"},{"unstructured":"Baget, J.-F. , Lecl\u00e8re, M. , Mugnier, M.-L. , Rocher, S. and Sipieter, C. 2015. Graal: A toolkit for query answering with existential rules. In Proceedings of the International Symposium on Rules and Rule Markup Languages for the Semantic Web. LNCS, vol. 9202. Springer, 328\u2013344.","key":"S1471068420000101_ref6"},{"unstructured":"Cuenca Grau, B. , Horrocks, I. , Kr\u00f6tzsch, M. , Kupke, C. , Magka, D. , Motik, B. and Wang, Z. 2013. Acyclicity notions for existential rules and their application to query answering in ontologies. Journal of Artificial Intelligence Research 47, 741\u2013808.","key":"S1471068420000101_ref19"},{"unstructured":"Baget, J.-F. , Gutierrez, A. , Leclere, M. , Mugnier, M.-L. , Rocher, S. and Sipieter, C. 2015. Datalog+, RuleML and OWL 2: Formats and translations for existential rules. In Proceedings of the RuleML 2015 Challenge (Challenge+ DC@ RuleML). CEUR Workshop Proceedings, vol. 1417. CEUR-WS.org.","key":"S1471068420000101_ref5"},{"unstructured":"Benedikt, M. , Konstantinidis, G. , Mecca, G. , Motik, B. , Papotti, P. , Santoro, D. and Tsamoura, E. 2017. Benchmarking the chase. In Proceedings of the 36th ACM Symposium on Principles of Database Systems. ACM, 37\u201352.","key":"S1471068420000101_ref11"},{"unstructured":"Calautti, M. and Pieris, A. 2019. Oblivious chase termination: The sticky case. In Proceedings of the Twenty-Second International Conference on Database Theory. LIPIcs, vol. 127. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 17:1\u201317:18.","key":"S1471068420000101_ref14"},{"unstructured":"Carral, D. , Dragoste, I. , Gonz\u00e1lez, L. , Jacobs, C. , Kr\u00f6tzsch, M. and Urbani, J. 2019. Vlog: A rule engine for knowledge graphs. In Proceedings of the16th International Semantic Web Conference. LNCS, vol. 11779. Springer, 19\u201335.","key":"S1471068420000101_ref16"},{"doi-asserted-by":"publisher","key":"S1471068420000101_ref25","DOI":"10.1145\/3375395.3387644"},{"doi-asserted-by":"publisher","key":"S1471068420000101_ref31","DOI":"10.1137\/0217058"},{"unstructured":"Kr\u00f6tzsch, M. and Rudolph, S. 2011. Extending decidable existential rules by joining acyclicity and guardedness. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. IJCAI\/AAAI, 963\u2013968.","key":"S1471068420000101_ref33"},{"unstructured":"Karimi, A. , Zhang, H. and You, J.-H. 2018. Restricted chase termination: A hierarchical approach and experimentation. In Proceedings of the 2nd International Joint Conference on Rules and Reasoning. LNCS, vol. 11092. Springer, 98\u2013114.","key":"S1471068420000101_ref32"},{"unstructured":"Marnette, B. 2009. Generalized schema-mappings: from termination to tractability. In Proceedings of the Twenty-Eighth ACM Symposium on Principles of Database Systems. ACM, 13\u201322.","key":"S1471068420000101_ref36"},{"doi-asserted-by":"publisher","key":"S1471068420000101_ref30","DOI":"10.3233\/SW-2011-0025"},{"doi-asserted-by":"publisher","key":"S1471068420000101_ref35","DOI":"10.1137\/S0097539797322140"},{"unstructured":"Baget, J.-F. , Garreau, F. , Mugnier, M.-L. and Rocher, S. 2014b. Revisiting chase termination for existential rules and their extension to nonmonotonic negation. In Proceedings of the 15th International Workshop on Non-Monotonic Reasoning (NMR 2014).","key":"S1471068420000101_ref4"},{"unstructured":"Carral, D. , Dragoste, I. and Kr\u00f6tzsch, M. 2017. Restricted chase (non) termination for existential rules with disjunctions. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence. ijcai.org, 922\u2013928.","key":"S1471068420000101_ref17"},{"unstructured":"Lecl\u00e8re, M. , Mugnier, M.-L. , Thomazo, M. and Ulliana, F. 2019. A single approach to decide chase termination on linear existential rules. In Proceedings of Twenty-Second International Conference on Database Theory. LIPIcs, vol. 127. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 18:1\u201318:19.","key":"S1471068420000101_ref34"},{"doi-asserted-by":"publisher","key":"S1471068420000101_ref8","DOI":"10.1016\/j.artint.2011.03.002"},{"key":"S1471068420000101_ref12","first-page":"27:1","article-title":"Guarded-based disjunctive tuple-generating dependencies","volume":"4","author":"Bourhis","year":"2016","journal-title":"ACM Transactions on Database Systems 41"},{"doi-asserted-by":"publisher","key":"S1471068420000101_ref20","DOI":"10.1145\/502807.502810"},{"unstructured":"Delivorias, S. , Lecl\u00e8re, M. , Mugnier, M.-L. and Ulliana, F. 2018. On the k-boundedness for existential rules. In Proceedings of the 2nd International Joint Conference on Rules and Reasoning. LNCS, vol. 11092. Springer, 48\u201364.","key":"S1471068420000101_ref21"}],"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\/S1471068420000101","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,21]],"date-time":"2020-12-21T12:48:42Z","timestamp":1608554922000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068420000101\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,30]]},"references-count":42,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["S1471068420000101"],"URL":"https:\/\/doi.org\/10.1017\/s1471068420000101","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"type":"print","value":"1471-0684"},{"type":"electronic","value":"1475-3081"}],"subject":[],"published":{"date-parts":[[2020,6,30]]},"assertion":[{"value":"Copyright \u00a9 The Author(s), 2020. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}