{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T15:39:31Z","timestamp":1753889971502,"version":"3.41.2"},"reference-count":1,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2014,5,21]],"date-time":"2014-05-21T00:00:00Z","timestamp":1400630400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"}],"funder":[{"DOI":"10.13039\/501100000780","name":"European Commission","doi-asserted-by":"crossref","award":["246858"],"award-info":[{"award-number":["246858"]}],"id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>Evaluating a Boolean conjunctive query Q against a guarded first-order theory\nF is equivalent to checking whether \"F and not Q\" is unsatisfiable. This\nproblem is relevant to the areas of database theory and description logic.\nSince Q may not be guarded, well known results about the decidability,\ncomplexity, and finite-model property of the guarded fragment do not obviously\ncarry over to conjunctive query answering over guarded theories, and had been\nleft open in general. By investigating finite guarded bisimilar covers of\nhypergraphs and relational structures, and by substantially generalising\nRosati's finite chase, we prove for guarded theories F and (unions of)\nconjunctive queries Q that (i) Q is true in each model of F iff Q is true in\neach finite model of F and (ii) determining whether F implies Q is\n2EXPTIME-complete. We further show the following results: (iii) the existence\nof polynomial-size conformal covers of arbitrary hypergraphs; (iv) a new proof\nof the finite model property of the clique-guarded fragment; (v) the small\nmodel property of the guarded fragment with optimal bounds; (vi) a\npolynomial-time solution to the canonisation problem modulo guarded\nbisimulation, which yields (vii) a capturing result for guarded bisimulation\ninvariant PTIME.<\/jats:p>","DOI":"10.2168\/lmcs-10(2:3)2014","type":"journal-article","created":{"date-parts":[[2014,11,14]],"date-time":"2014-11-14T09:40:42Z","timestamp":1415958042000},"source":"Crossref","is-referenced-by-count":19,"title":["Querying the Guarded Fragment"],"prefix":"10.46298","volume":"Volume 10, Issue 2","author":[{"given":"Vince","family":"B\u00e1r\u00e1ny","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2353-5230","authenticated-orcid":false,"given":"Georg","family":"Gottlob","sequence":"additional","affiliation":[]},{"given":"Martin","family":"Otto","sequence":"additional","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2014,5,21]]},"reference":[{"key":"612:not-found"}],"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/675\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/675\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T19:53:43Z","timestamp":1681242823000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/675"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,5,21]]},"references-count":1,"URL":"https:\/\/doi.org\/10.2168\/lmcs-10(2:3)2014","relation":{"is-same-as":[{"id-type":"arxiv","id":"1309.5822","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1309.5822","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2014,5,21]]},"article-number":"675"}}