{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,17]],"date-time":"2025-10-17T13:45:11Z","timestamp":1760708711583},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2009,8]]},"abstract":"<jats:p>\n            We study the termination problem of the chase algorithm, a central tool in various database problems such as the constraint implication problem, Conjunctive Query optimization, rewriting queries using views, data exchange, and data integration. The basic idea of the chase is, given a database instance and a set of constraints as input, to fix constraint violations in the database instance. It is well-known that, for an arbitrary set of constraints, the chase does not necessarily terminate (in general, it is even undecidable if it does or not). Addressing this issue, we review the limitations of existing sufficient termination conditions for the chase and develop new techniques that allow us to establish weaker sufficient conditions. In particular, we introduce two novel termination conditions called\n            <jats:italic>safety<\/jats:italic>\n            and\n            <jats:italic>inductive restriction<\/jats:italic>\n            , and use them to define the so-called\n            <jats:italic>T-hierarchy<\/jats:italic>\n            of termination conditions. We then study the interrelations of our termination conditions with previous conditions and the complexity of checking our conditions. This analysis leads to an algorithm that checks membership in a level of the\n            <jats:italic>T<\/jats:italic>\n            -hierarchy and accounts for the complexity of termination conditions. As another contribution, we study the problem of\n            <jats:italic>data-dependent<\/jats:italic>\n            chase termination and present sufficient termination conditions w.r.t. fixed instances. They might guarantee termination although the chase does not terminate in the general case. As an application of our techniques beyond those already mentioned, we transfer our results into the field of query answering over knowledge bases where the chase on the underlying database may not terminate, making existing algorithms applicable to broader classes of constraints.\n          <\/jats:p>","DOI":"10.14778\/1687627.1687737","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"970-981","source":"Crossref","is-referenced-by-count":31,"title":["On chase termination beyond stratification"],"prefix":"10.14778","volume":"2","author":[{"given":"Michael","family":"Meier","sequence":"first","affiliation":[{"name":"University of Freiburg, Georges-K\u00f6hler-Allee, Freiburg, Germany"}]},{"given":"Michael","family":"Schmidt","sequence":"additional","affiliation":[{"name":"University of Freiburg, Georges-K\u00f6hler-Allee, Freiburg, Germany"}]},{"given":"Georg","family":"Lausen","sequence":"additional","affiliation":[{"name":"University of Freiburg, Georges-K\u00f6hler-Allee, Freiburg, Germany"}]}],"member":"320","published-online":{"date-parts":[[2009,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1121995.1122010"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1189769.1189778"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/320107.320112"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1634.1636"},{"key":"e_1_2_1_5_1","volume-title":"Description Logics","volume":"353","author":"Cal\u00ec A.","year":"2008","unstructured":"A. Cal\u00ec , G. Gottlob , and M. Kifer . Taming the Infinite Chase: Query Answering under Expressive Relational Constraints . In Description Logics , volume 353 , 2008 . A. Cal\u00ec, G. Gottlob, and M. Kifer. Taming the Infinite Chase: Query Answering under Expressive Relational Constraints. In Description Logics, volume 353, 2008."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1514894.1514897"},{"issue":"4","key":"e_1_2_1_7_1","first-page":"187","article-title":"The Monadic Second-order Logic of Graphs II","volume":"21","author":"Courcelle B.","year":"1989","unstructured":"B. Courcelle . The Monadic Second-order Logic of Graphs II : Infinite Graphs of Bounded Width. Mathematical Systems Theory , 21 ( 4 ): 187 -- 221 , 1989 . B. Courcelle. The Monadic Second-order Logic of Graphs II: Infinite Graphs of Bounded Width. Mathematical Systems Theory, 21(4):187--221, 1989.","journal-title":"Infinite Graphs of Bounded Width. Mathematical Systems Theory"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/582095.582119"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376916.1376938"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/645505.656436"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1346330.1346334"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780100054"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/588111.588138"},{"key":"e_1_2_1_14_1","first-page":"510","volume-title":"VLDB","author":"King J. J.","year":"1981","unstructured":"J. J. King . QUIST : A System for Semantic Query Optimization in Relational Databases . In VLDB , pages 510 -- 517 , 1981 . J. J. King. QUIST: A System for Semantic Query Optimization in Relational Databases. In VLDB, pages 510--517, 1981."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543644"},{"key":"e_1_2_1_17_1","volume-title":"Extended Abstract. Proc. Alberto Mendelzon International Workshop on Foundations of Data Management","author":"Meier M.","year":"2009","unstructured":"M. Meier , M. Schmidt , and G. Lausen . Stop the Chase , Extended Abstract. Proc. Alberto Mendelzon International Workshop on Foundations of Data Management , 2009 . M. Meier, M. Schmidt, and G. Lausen. Stop the Chase, Extended Abstract. Proc. Alberto Mendelzon International Workshop on Foundations of Data Management, 2009."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.123"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/645503.656255"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1O16\/j.tcs.2004.10.033"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1687627.1687737","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:34:09Z","timestamp":1672227249000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1687627.1687737"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,8]]},"references-count":19,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,8]]}},"alternative-id":["10.14778\/1687627.1687737"],"URL":"https:\/\/doi.org\/10.14778\/1687627.1687737","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2009,8]]}}}