On the decidability and complexity of integrating ontologies and rules

Riccardo Rosati.
Web Semantics, volume 3, number 1, pages 41-60, 2005. ISSN 1570-8268.



We define the formal framework of r-hybrid knowledge bases (KBs) integrating ontologies and rules. A r-hybrid KB has a structural component (ontology) and a rule component. Such a framework is very general, in the sense that: (i) the construction is parametric with respect to the logic used to specify the structural component; (ii) the rule component is very expressive, since it consists of a disjunctive Datalog program, i.e., a Datalog program with negation as failure and disjunction. (iii) the rule component is constrained in its interaction with the structural component according to a safeness condition: such a safe interaction between rules and structural KB captures (and is a generalization of) several previous proposals. As a consequence, we are able to show that such a framework of r-hybrid KBs comprises many systems proposed for combining rules and Description Logics. Then, we study reasoning in r-hybrid KBs. We provide a general algorithm for reasoning in r-hybrid KBs, and prove that, under very general conditions, decidability of reasoning is preserved when we add safe disjunctive Datalog rules to a KB: in other words, if reasoning in the logic L used to specify the structural component T is decidable, then reasoning in the extension of T with safe disjunctive Datalog rules is still decidable. We also show that an analogous property holds for the complexity of reasoning in r-hybrid KBs. Our decidability and complexity results generalize in a broad sense previous results obtained in recent research on this topic. In particular, we prove that reasoning in r-hybrid KBs whose structural component is specified in the Web Ontology Language OWL-DL is decidable.

Bibtex entry:

@String{WSJ = "Web Semantics"}

author = "Rosati, Riccardo",
title = "On the decidability and complexity of integrating ontologies and rules",
journal = WSJ,
volume = 3,
number = 1,
pages = "41--60",
year = 2005,
issn = "1570-8268",

Link to electronic version of published paper