{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T06:31:29Z","timestamp":1780381889293,"version":"3.54.1"},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,7]]},"abstract":"<jats:p>Existential rules, a.k.a. dependencies in databases, and Datalog+\/- in knowledge representation and reasoning recently, are a family of important logical languages widely used in computer science and artificial intelligence. Towards a deep understanding of these languages in model theory, we establish model-theoretic characterizations for a number of existential rule languages such as (disjunctive) embedded dependencies, tuple-generating dependencies (TGDs), (frontier-)guarded TGDs and linear TGDs. All these characterizations hold for the class of arbitrary structures, and most of them also work on the class of finite structures. As a natural application of these results, complexity bounds for the rewritability of above languages are also identified.<\/jats:p>","DOI":"10.24963\/ijcai.2020\/269","type":"proceedings-article","created":{"date-parts":[[2020,7,8]],"date-time":"2020-07-08T08:12:10Z","timestamp":1594195930000},"page":"1940-1946","source":"Crossref","is-referenced-by-count":2,"title":["Model-theoretic Characterizations of Existential Rule Languages"],"prefix":"10.24963","author":[{"given":"Heng","family":"Zhang","sequence":"first","affiliation":[{"name":"Tianjin University, Tianjin, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yan","family":"Zhang","sequence":"additional","affiliation":[{"name":"Western Sydney University, NSW, Australia"},{"name":"Huazhong University of Science and Technology, Hubei, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Guifei","family":"Jiang","sequence":"additional","affiliation":[{"name":"Nankai University, Tianjin, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"10584","event":{"name":"Twenty-Ninth International Joint Conference on Artificial Intelligence and Seventeenth Pacific Rim International Conference on Artificial Intelligence {IJCAI-PRICAI-20}","theme":"Artificial Intelligence","location":"Yokohama, Japan","acronym":"IJCAI-PRICAI-2020","number":"28","sponsor":["International Joint Conferences on Artificial Intelligence Organization (IJCAI)"],"start":{"date-parts":[[2020,7,11]]},"end":{"date-parts":[[2020,7,17]]}},"container-title":["Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence"],"original-title":[],"deposited":{"date-parts":[[2020,7,8]],"date-time":"2020-07-08T22:14:12Z","timestamp":1594246452000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ijcai.org\/proceedings\/2020\/269"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2020,7]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/ijcai.2020\/269","relation":{},"subject":[],"published":{"date-parts":[[2020,7]]}}}