{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T16:54:10Z","timestamp":1759683250924},"reference-count":28,"publisher":"Cambridge University Press (CUP)","issue":"4-5","license":[{"start":{"date-parts":[[2012,9,5]],"date-time":"2012-09-05T00:00:00Z","timestamp":1346803200000},"content-version":"unspecified","delay-in-days":66,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory and Practice of Logic Programming"],"published-print":{"date-parts":[[2012,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p><jats:italic>Datalog<\/jats:italic>is one of the best-known rule-based languages, and extensions of it are used in a wide context of applications. An important<jats:italic>Datalog<\/jats:italic>extension is Disjunctive<jats:italic>Datalog<\/jats:italic>, which significantly increases the expressivity of the basic language. Disjunctive<jats:italic>Datalog<\/jats:italic>is useful in a wide range of applications, ranging from Databases (e.g., Data Integration) to Artificial Intelligence (e.g., diagnosis and planning under incomplete knowledge). However, in recent years an important shortcoming of<jats:italic>Datalog<\/jats:italic>-based languages became evident, e.g. in the context of data-integration (consistent query-answering, ontology-based data access) and Semantic Web applications: The language does not permit any generation of and reasoning with unnamed individuals in an obvious way. In general, it is weak in supporting many cases of existential quantification. To overcome this problem,<jats:italic>Datalog<\/jats:italic><jats:sup>\u2203<\/jats:sup>has recently been proposed, which extends traditional<jats:italic>Datalog<\/jats:italic>by existential quantification in rule heads. In this work, we propose a natural extension of Disjunctive<jats:italic>Datalog<\/jats:italic>and<jats:italic>Datalog<\/jats:italic><jats:sup>\u2203<\/jats:sup>, called<jats:italic>Datalog<\/jats:italic><jats:sup>\u2203,\u02c5<\/jats:sup>, which allows both disjunctions and existential quantification in rule heads and is therefore an attractive language for knowledge representation and reasoning, especially in domains where ontology-based reasoning is needed. We formally define syntax and semantics of the language<jats:italic>Datalog<\/jats:italic><jats:sup>\u2203,\u02c5<\/jats:sup>, and provide a notion of instantiation, which we prove to be adequate for<jats:italic>Datalog<\/jats:italic><jats:sup>\u2203,\u02c5<\/jats:sup>. A main issue of<jats:italic>Datalog<\/jats:italic><jats:sup>\u2203<\/jats:sup>and hence also of<jats:italic>Datalog<\/jats:italic><jats:sup>\u2203,\u02c5<\/jats:sup>is that decidability is no longer guaranteed for typical reasoning tasks. In order to address this issue, we identify many decidable fragments of the language, which extend, in a natural way, analog classes defined in the non-disjunctive case. Moreover, we carry out an in-depth complexity analysis, deriving interesting results which range from Logarithmic Space to Exponential Time.<\/jats:p>","DOI":"10.1017\/s1471068412000257","type":"journal-article","created":{"date-parts":[[2012,9,5]],"date-time":"2012-09-05T11:28:45Z","timestamp":1346844525000},"page":"701-718","source":"Crossref","is-referenced-by-count":11,"title":["Disjunctive datalog with existential quantifiers: Semantics, decidability, and complexity issues"],"prefix":"10.1017","volume":"12","author":[{"given":"MARIO","family":"ALVIANO","sequence":"first","affiliation":[]},{"given":"WOLFGANG","family":"FABER","sequence":"additional","affiliation":[]},{"given":"NICOLA","family":"LEONE","sequence":"additional","affiliation":[]},{"given":"MARCO","family":"MANNA","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2012,9,5]]},"reference":[{"key":"S1471068412000257_ref28","doi-asserted-by":"crossref","unstructured":"Mugnier M.-L. 2011. Ontological query answering with existential rules. In Proceedings of the 5th RR International Conference. 2\u201323.","DOI":"10.1007\/978-3-642-23580-1_2"},{"key":"S1471068412000257_ref26","doi-asserted-by":"crossref","unstructured":"Marnette B. 2009. Generalized schema-mappings: from termination to tractability. In Proceedings of the 28th PODS Symposium. 13\u201322.","DOI":"10.1145\/1559795.1559799"},{"key":"S1471068412000257_ref23","doi-asserted-by":"crossref","unstructured":"Leone N. , Gottlob G. , Rosati R. , Eiter T. , Faber W. , Fink M. , Greco G. , Ianni G. , Ka\u0142ka E. , Lembo D. , Lenzerini M. , Lio V. , Nowicki B. , Ruzzi M. , Staniszkis W. and Terracina G. 2005. The INFOMIX system for advanced integration of incomplete and inconsistent data. In Proceedings of the 24th ACM SIGMOD International Conference on Management of Data. 915\u2013917.","DOI":"10.1145\/1066157.1066286"},{"key":"S1471068412000257_ref22","first-page":"382","volume-title":"Proceedings of the 24th DL International Workshop","author":"Kollia","year":"2011"},{"key":"S1471068412000257_ref21","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90081-3"},{"key":"S1471068412000257_ref20","unstructured":"Hustadt U. , Motik B. and Sattler U. 2004. Reducing SHIQ- Descrption logic to disjunctive datalog programs. In Proceedings of the 9th KR International Conference. 152\u2013162."},{"key":"S1471068412000257_ref19","first-page":"1158","article-title":"Stratification criteria and rewriting techniques for checking chase termination","volume":"4","author":"Greco","year":"2011","journal-title":"PVLDB"},{"key":"S1471068412000257_ref18","doi-asserted-by":"publisher","DOI":"10.2307\/2586808"},{"key":"S1471068412000257_ref15","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.10.033"},{"key":"S1471068412000257_ref14","doi-asserted-by":"publisher","DOI":"10.1145\/261124.261126"},{"key":"S1471068412000257_ref8","first-page":"255","volume-title":"Reasoning Web","author":"Calvanese","year":"2009"},{"key":"S1471068412000257_ref24","unstructured":"Leone N. , Manna M. , Terracina G. and Veltri P. 2012. Efficiently computable datalog\u2203 programs. In Proceedings of the 13th KR International Conference, Forthcoming. Long version: www.mat.unical.it\/kr2012\/shy.pdf."},{"key":"S1471068412000257_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/s10817-007-9078-x"},{"key":"S1471068412000257_ref11","volume-title":"Datalog Reloaded. First International Workshop, Datalog 2010. Revised Selected Papers","author":"Gottlob","year":"2011"},{"key":"S1471068412000257_ref12","doi-asserted-by":"crossref","unstructured":"Deutsch A. , Nash A. and Remmel J. 2008. The chase revisited. In Proceedings of the 27th PODS Symposium 149\u2013158.","DOI":"10.1145\/1376916.1376938"},{"key":"S1471068412000257_ref6","unstructured":"Cal\u00ec A. , Gottlob G. and Pieris A. 2010b. Query answering under non-guarded rules in Datalog\u00b1. In Proceedings of the 4th RR International Conferences, vol. 6333. 1\u201317."},{"key":"S1471068412000257_ref4","doi-asserted-by":"crossref","unstructured":"Cal\u00ec A. , Gottlob G. and Lukasiewicz T. 2009. A general datalog-based framework for tractable query answering over ontologies. In Proceedings of the 28th PODS Symposium. 77\u201386.","DOI":"10.1145\/1559795.1559809"},{"key":"S1471068412000257_ref25","doi-asserted-by":"publisher","DOI":"10.1145\/320107.320115"},{"key":"S1471068412000257_ref1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1004275029985"},{"key":"S1471068412000257_ref16","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2010.04.011"},{"key":"S1471068412000257_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00220-0"},{"key":"S1471068412000257_ref27","first-page":"970","article-title":"On chase termination beyond stratification","volume":"2","author":"Meier","year":"2009","journal-title":"PVLDB"},{"key":"S1471068412000257_ref13","doi-asserted-by":"publisher","DOI":"10.1145\/976706.976708"},{"key":"S1471068412000257_ref17","doi-asserted-by":"crossref","unstructured":"Gottlob G. , Leone N. and Scarcello F. 1999. Hypertree decompositions and tractable queries. In Proceedings of the 18th PODS Symp. 21\u201332.","DOI":"10.1145\/303976.303979"},{"key":"S1471068412000257_ref2","doi-asserted-by":"crossref","unstructured":"Barany V. , Gottlob G. and Otto M. 2010. Querying the guarded fragment. In Proceedings of the 25th Annual IEEE Symposium on LICS. 1\u201310.","DOI":"10.1109\/LICS.2010.26"},{"key":"S1471068412000257_ref3","unstructured":"Cal\u00ec A. , Gottlob G. and Kifer M. 2008. Taming the infinite chase: Query answering under expressive relational constraints. In Proceedings of the 11th KR International Conference. 70\u201380. Revised version: http:\/\/dbai.tuwien.ac.at\/staff\/gottlob\/CGK.pdf."},{"key":"S1471068412000257_ref5","first-page":"554","article-title":"Advanced processing for ontological queries","volume":"3","author":"Cal\u00ec","year":"2010","journal-title":"PVLDB"},{"key":"S1471068412000257_ref7","doi-asserted-by":"crossref","unstructured":"Cal\u00ec A. , Gottlob G. and Pieris A. 2011. New expressive languages for ontological query answering. In Proceedings of the 25th AAAI Conference on AI. 1541\u20131546.","DOI":"10.1609\/aaai.v25i1.7957"}],"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\/S1471068412000257","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,25]],"date-time":"2023-06-25T15:37:21Z","timestamp":1687707441000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068412000257\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,7]]},"references-count":28,"journal-issue":{"issue":"4-5","published-print":{"date-parts":[[2012,7]]}},"alternative-id":["S1471068412000257"],"URL":"https:\/\/doi.org\/10.1017\/s1471068412000257","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"value":"1471-0684","type":"print"},{"value":"1475-3081","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,7]]}}}