On the Complexity of Ontological Reasoning under Disjunctive Existential Rules

Georg Gottlob, Marco Manna, Michael Morak, Andreas Pieris

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Ontology-based data access is an emerging yet powerful technology that allows to enhance a classical relational database with an ontology in order to infer new intensional knowledge. Recently, Datalog+/- was introduced with the purpose of providing tractable reasoning algorithms for expressive ontology languages. In this framework, Datalog is extended by features such as existential quantification in rule heads, and at the same time the rule syntax is restricted to guarantee decidability, and also tractability, of relevant reasoning tasks. In this paper, we enrich Datalog even more by allowing not only existential quantification but also disjunction in rule heads, and we investigate the complexity of reasoning under the obtained formalism.
Original languageEnglish
Title of host publicationMathematical Foundations of Computer Science 2012 - 37th International Symposium, MFCS 2012, Bratislava, Slovakia, August 27-31, 2012. Proceedings
PublisherSpringer Berlin Heidelberg
Number of pages18
ISBN (Electronic)978-3-642-32589-2
ISBN (Print)978-3-642-32588-5
Publication statusPublished - 2012

Publication series

NameLecture Notes in Computer Science (LNCS)
PublisherSpringer Berlin Heidelberg
ISSN (Print)0302-9743

Fingerprint Dive into the research topics of 'On the Complexity of Ontological Reasoning under Disjunctive Existential Rules'. Together they form a unique fingerprint.

Cite this