{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T23:39:30Z","timestamp":1774654770211,"version":"3.50.1"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,8,17]],"date-time":"2020-08-17T00:00:00Z","timestamp":1597622400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,8,17]],"date-time":"2020-08-17T00:00:00Z","timestamp":1597622400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/S003800\/1"],"award-info":[{"award-number":["EP\/S003800\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/M025268\/"],"award-info":[{"award-number":["EP\/M025268\/"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The chase procedure is a fundamental algorithmic tool in database theory with a variety of applications. A key problem concerning the chase procedure is all-instances termination: for a given set of tuple-generating dependencies (TGDs), is it the case that the chase terminates for every input database? In view of the fact that this problem is undecidable, it is natural to ask whether known well-behaved classes of TGDs, introduced in different contexts such as ontological reasoning, ensure decidability. We consider a prominent paradigm that led to a robust TGD-based formalism, called stickiness. We show that for sticky sets of TGDs, all-instances chase termination is decidable if we focus on the (semi-)oblivious chase, and we pinpoint its exact complexity: <jats:sc>PSpace<\/jats:sc>-complete in general, and <jats:sc>NLogSpace<\/jats:sc>-complete for predicates of bounded arity. These complexity results are obtained via a graph-based syntactic characterization of chase termination that is of independent interest.<\/jats:p>","DOI":"10.1007\/s00224-020-09994-5","type":"journal-article","created":{"date-parts":[[2020,8,17]],"date-time":"2020-08-17T17:02:22Z","timestamp":1597683742000},"page":"84-121","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Semi-Oblivious Chase Termination: The Sticky Case"],"prefix":"10.1007","volume":"65","author":[{"given":"Marco","family":"Calautti","sequence":"first","affiliation":[]},{"given":"Andreas","family":"Pieris","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,8,17]]},"reference":[{"key":"9994_CR1","volume-title":"Foundations of Databases","author":"S Abiteboul","year":"1995","unstructured":"Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley, Reading, MA (1995)"},{"issue":"4","key":"9994_CR2","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1145\/320107.320112","volume":"4","author":"AV Aho","year":"1979","unstructured":"Aho, A.V., Sagiv, Y., Ullman, J.D.: Efficient optimization of a class of relational expressions. ACM Trans. Database Syst. 4(4), 435\u2013454 (1979)","journal-title":"ACM Trans. Database Syst."},{"key":"9994_CR3","unstructured":"Baget, J., Mugnier, M., Rudolph, S., Thomazo, M.: Walking the Complexity Lines for Generalized Guarded Existential Rules. In: IJCAI, pp 712\u2013717 (2011)"},{"issue":"9-10","key":"9994_CR4","doi-asserted-by":"publisher","first-page":"1620","DOI":"10.1016\/j.artint.2011.03.002","volume":"175","author":"JF Baget","year":"2011","unstructured":"Baget, J.F., Lecl\u00e8re, M., Mugnier, M.L., Salvat, E.: On rules with existential variables: walking the decidability line. Artif. Intell. 175 (9-10), 1620\u20131654 (2011)","journal-title":"Artif. Intell."},{"issue":"4","key":"9994_CR5","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1145\/1634.1636","volume":"31","author":"C Beeri","year":"1984","unstructured":"Beeri, C., Vardi, M.Y.: A proof procedure for data dependencies. J. ACM 31(4), 718\u2013741 (1984)","journal-title":"J. ACM"},{"key":"9994_CR6","doi-asserted-by":"crossref","unstructured":"Benedikt, M., Konstantinidis, G., Mecca, G., Motik, B., Papotti, P., Santoro, D., Tsamoura, E.: Benchmarking the Chase. In: PODS, pp 37\u201352 (2017)","DOI":"10.1145\/3034786.3034796"},{"key":"9994_CR7","doi-asserted-by":"crossref","unstructured":"Bourhis, P., Lecl\u0117re, M., Mugnier, M., Tison, S., Ulliana, F., Gallois, L.: Oblivious and Semi-Oblivious Boundedness for Existential Rules. In: IJCAI, pp 1581\u20131587 (2019)","DOI":"10.24963\/ijcai.2019\/219"},{"key":"9994_CR8","doi-asserted-by":"crossref","unstructured":"Calautti, M., Gottlob, G., Pieris, A.: Chase Termination for Guarded Existential Rules. In: PODS, pp 91\u2013103 (2015)","DOI":"10.1145\/2745754.2745773"},{"issue":"5","key":"9994_CR9","first-page":"396","volume":"9","author":"M Calautti","year":"2016","unstructured":"Calautti, M., Greco, S., Molinaro, C., Trubitsyna, I.: Exploiting equality generating dependencies in checking chase termination. PVLDB 9(5), 396\u2013407 (2016)","journal-title":"PVLDB"},{"key":"9994_CR10","doi-asserted-by":"crossref","unstructured":"Calautti, M., Pieris, A.: Oblivious Chase Termination: The Sticky Case. In: ICDT, pp 17:1\u201317:18 (2019)","DOI":"10.1007\/s00224-020-09994-5"},{"key":"9994_CR11","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1613\/jair.3873","volume":"48","author":"A Cal\u00ec","year":"2013","unstructured":"Cal\u00ec, A., Gottlob, G., Kifer, M.: Taming the infinite chase: query answering under expressive relational constraints. J. Artif. Intell. Res. 48, 115\u2013174 (2013)","journal-title":"J. Artif. Intell. Res."},{"key":"9994_CR12","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/j.websem.2012.03.001","volume":"14","author":"A Cal\u00ec","year":"2012","unstructured":"Cal\u00ec, A., Gottlob, G., Lukasiewicz, T.: A general Datalog-based framework for tractable query answering over ontologies. J. Web Sem. 14, 57\u201383 (2012)","journal-title":"J. Web Sem."},{"key":"9994_CR13","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/j.artint.2012.08.002","volume":"193","author":"A Cal\u00ec","year":"2012","unstructured":"Cal\u00ec, A., Gottlob, G., Pieris, A.: Towards more expressive ontology languages: the query answering problem. Artif. Intell. 193, 87\u2013128 (2012)","journal-title":"Artif. Intell."},{"key":"9994_CR14","doi-asserted-by":"publisher","first-page":"741","DOI":"10.1613\/jair.3949","volume":"47","author":"B Cuenca Grau","year":"2013","unstructured":"Cuenca Grau, B., Horrocks, I., Kro\u0307tzsch, M., Kupke, C., Magka, D., Motik, B., Wang, Z.: Acyclicity notions for existential rules and their application to query answering in ontologies. J. Artif. Intell. Res. 47, 741\u2013808 (2013)","journal-title":"J. Artif. Intell. Res."},{"key":"9994_CR15","doi-asserted-by":"crossref","unstructured":"Deutsch, A., Nash, A., Remmel, J.B.: The Chase Revisisted. In: PODS, pp 149\u2013158 (2008)","DOI":"10.1145\/1376916.1376938"},{"key":"9994_CR16","doi-asserted-by":"crossref","unstructured":"Deutsch, A., Tannen, V.: Reformulation of XML Queries and Constraints. In: ICDT, pp 225\u2013241 (2003)","DOI":"10.1007\/3-540-36285-1_15"},{"issue":"1","key":"9994_CR17","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/j.tcs.2004.10.033","volume":"336","author":"R Fagin","year":"2005","unstructured":"Fagin, R., Kolaitis, P.G., Miller, R.J., Popa, L.: Data exchange: semantics and query answering. Theor. Comput. Sci. 336(1), 89\u2013124 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"9994_CR18","doi-asserted-by":"crossref","unstructured":"Gogacz, T., Marcinkowski, J.: All-Instances Termination of Chase is Undecidable. In: ICALP, pp 293\u2013304 (2014)","DOI":"10.1007\/978-3-662-43951-7_25"},{"key":"9994_CR19","doi-asserted-by":"crossref","unstructured":"Gogacz, T., Marcinkowski, J., Pieris, A.: All-Instances Restricted Chase Termination. In: PODS. To appear (2020)","DOI":"10.1145\/3375395.3387644"},{"issue":"3","key":"9994_CR20","doi-asserted-by":"publisher","first-page":"221","DOI":"10.3233\/FI-2018-1627","volume":"157","author":"G Grahne","year":"2018","unstructured":"Grahne, G., Onet, A.: Anatomy of the chase. Fundam. Inform. 157(3), 221\u2013270 (2018)","journal-title":"Fundam. Inform."},{"issue":"11","key":"9994_CR21","first-page":"1158","volume":"4","author":"S Greco","year":"2011","unstructured":"Greco, S., Spezzano, F., Trubitsyna, I.: Stratification criteria and rewriting techniques for checking chase termination. PVLDB 4(11), 1158\u20131168 (2011)","journal-title":"PVLDB"},{"key":"9994_CR22","unstructured":"Kr\u00f6tzsch, M., Marx, M., Rudolph, S.: The Power of the Terminating Chase (Invited Talk). In: ICDT, pp 3:1\u20133:17 (2019)"},{"key":"9994_CR23","unstructured":"Kr\u00f6tzsch, M., Rudolph, S.: Extending Decidable Existential Rules by Joining Acyclicity and Guardedness. In: IJCAI, pp 963\u2013968 (2011)"},{"key":"9994_CR24","unstructured":"Lecl\u00e8re, M., Mugnier, M., Thomazo, M., Ulliana, F.: A Single Approach to Decide Chase Termination on Linear Existential Rules. In: ICDT, pp 18:1\u201318:19 (2019)"},{"key":"9994_CR25","unstructured":"Leone, N., Manna, M., Terracina, G., Veltri, P.: Efficiently Computable Datalog\u2203 Programs. In: KR (2012)"},{"issue":"2","key":"9994_CR26","doi-asserted-by":"publisher","first-page":"12:1","DOI":"10.1145\/3308448","volume":"20","author":"N Leone","year":"2019","unstructured":"Leone, N., Manna, M., Terracina, G., Veltri, P.: Fast query answering over existential rules. ACM Trans. Comput. Log. 20(2), 12:1\u201312:48 (2019)","journal-title":"ACM Trans. Comput. Log."},{"issue":"4","key":"9994_CR27","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1145\/320107.320115","volume":"4","author":"D Maier","year":"1979","unstructured":"Maier, D., Mendelzon, A.O., Sagiv, Y.: Testing implications of data dependencies. ACM Trans Database Syst. 4(4), 455\u2013469 (1979)","journal-title":"ACM Trans Database Syst."},{"key":"9994_CR28","doi-asserted-by":"crossref","unstructured":"Marnette, B.: Generalized Schema-Mappings: from Termination to Tractability. In: PODS, pp 13\u201322 (2009)","DOI":"10.1145\/1559795.1559799"},{"issue":"1","key":"9994_CR29","first-page":"970","volume":"2","author":"M Meier","year":"2009","unstructured":"Meier, M., Schmidt, M., Lausen, G.: On chase termination beyond stratification. PVLDB 2(1), 970\u2013981 (2009)","journal-title":"PVLDB"},{"key":"9994_CR30","doi-asserted-by":"crossref","unstructured":"Nenov, Y., Piro, R., Motik, B., Horrocks, I., Wu, Z., Banerjee, J.: Rdfox: a Highly-Scalable RDF Store. In: ISWC, pp 3\u201320 (2015)","DOI":"10.1007\/978-3-319-25010-6_1"},{"key":"9994_CR31","volume-title":"Computational complexity","author":"CH Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: Computational complexity. Addison-Wesley, Reading, MA (1994)"},{"key":"9994_CR32","unstructured":"Rudolph, S., Kr\u00f6tzsch, M., Hitzler, P.: All Elephants are Bigger than All Mice. In: DL (2008)"},{"key":"9994_CR33","doi-asserted-by":"crossref","unstructured":"Urbani, J., Kr\u00f6tzsch, M., Jacobs, C.J.H., Dragoste, I., Carral, D.: Efficient Model Construction for Horn Logic with Vlog - System Description. In: IJCAR, pp 680\u2013688 (2018)","DOI":"10.1007\/978-3-319-94205-6_44"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-020-09994-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-020-09994-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-020-09994-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,16]],"date-time":"2021-08-16T23:25:52Z","timestamp":1629156352000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-020-09994-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,17]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["9994"],"URL":"https:\/\/doi.org\/10.1007\/s00224-020-09994-5","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,8,17]]},"assertion":[{"value":"17 August 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}