The need for extending Description Logics (DLs) with nonmonotonic features has led, in the last decade, to the development of many extensions of DLs, obtained by combining them with the most well-known formalisms for nonmonomtnic reasoning [24, 2, 9, 11, 13, 16, 15, 18, 6, 4, 8, 23, 19, 7, 3] to deal with defeasible reasoning and inheritance, to allow for prototypical properties of concepts and to combine DLs with nonmonotonic rule-based languages [11, 10, 19, 17]. In this work we study a preferential extension of the logic SROE L(u; ), introduced by Kro¨tzsch [21], which is a low-complexity description logic of the E L family [1] that includes local reflexivity, conjunction of roles and concept products and is at the basis of OWL 2 EL. Our extension is based on Kraus, Lehmann and Magidor (KLM) preferential semantics [20], and, specifically, on ranked models [22]. We call the logic SROE L(u; )RT and define notions of rational and minimal entailment for it. The semantics of ranked interpretations for DLs was first studied in [6], where a rational extension of ALC is developed allowing for defeasible concept inclusions of the form C@D. In this work, following [14, 16], we extend the language of SROE L(u; ) with typeicality concepts T(C), whose instances are intended to be the typical C elements. Defeasible inclusions T(C) v D mean that “the typical C elements are Ds”. Here, however, as in [5, 12], typicality concepts can freely occur in concept inclusions. The language is then more general than in [16], where minimal ranked models have been shown to provide a semantic characterization to rational closure for ALC, which extends the rational closure by Lehmann and Magidor [22]. Alternative constructions of rational closure for ALC have been proposed in [8, 7]. All such constructions regard languages only containing strict or defeasible inclusions (i.e., in the language with typicality concepts, T(C ) may only occur in inclusions T(C ) v D and in assertions). In this work we define a Datalog translation for SROE L(u; )RT which builds on the materialization calculus in [21], and, for typicality reasoning, is based on properties of ranked models, showing that instance checking under rational entailment is polynomial. While this result has the consequence that the Rational Closure (based on the definition in [16]) can be computed in polynomial time, we show that, for general SROE L(u; )RT KBs, deciding instance checking under minimal entailment is CONP-hard (while minimal entailment coincides with Rational Closure for ALC). The notion of concept in SROE L(u; ), as defined by Kro¨tzsch [21], is extended with typicality concepts. We let NC be a set of concept names, NR a set of role names and NI a set of individual names. A concept in SROE L(u; ) is defined as follows: C := A j > j ? j C u C j 9r:C j 9S:Self j fag where A 2 NC and r 2 NR. We introduce a notion of extended concept CE as follows:
CE := C j T(C) j CE u CE j 9S:CE where C is a SROE L(u; ) concept; i.e., extended concepts include typicality concepts T(C), which can occur in conjunctions and existential restrictions, but T cannot be nested.
A KB is a triple (TBox ; RBox ; ABox ). TBox contains a finite set of general
concept inclusions (GCI) C v D, where C and D are extended concepts; RBox (as in [
Following [
Definition 1. A SROE L(u; )RT interpretation M is any structure h ; <; I i where: (i) and I are a domain and an interpretation function as in a SROE L(u; ) interpretations; (ii) < is an irreflexive, transitive, well-founded and modular relation over ; (iii) the interpretation of concept T(C) is defined as follows: (T(C))I = M in<(CI ), where M in<(S) = fu : u 2 S and @z 2 S s.t. z < ug. An irreflexive and transitive relation < is well-founded if, for all S , for all x 2 S, either x 2 M in<(S) or 9y 2 M in<(S) such that y < x. It is modular if, for all x; y; z 2 , x < y implies x < z or z < y.
As in [
T(Student u Italian)(luigi); T(Student u Young )(paul)g
Standard DL inferences hold for T(C) concepts and T(C) v D inclusions. For
instance, we can conclude that Mario is a typical student (by (e)) and young (by (d)).
However, by the properties of defeasible inclusions, Luigi, who is a typical Italian
student, and Paul, who is a typical young student, both inherit the property of typical
students of being math haters. In this logic we cannot conclude that all typical young
Italians have black hair (and that Luigi has black hair), according to Rational
Monotonicity in [
Reasoning in a Rational Extension of SROEL(u; ) (Extended Abstract) To supports such a stronger nonmonotonic inference, a minimal model semantics (and minimal entailment) is needed to select the interpretations where individuals are as typical as possible (see below).
A normal form can be defined for SROE L(u; )RT knowledge bases. A KB is in
normal form if it admits axioms of a SROE L(u; ) KB in normal form, and axioms
of the form: A v T(B) and T(B) v C with A; B; C 2 NC . Extending the results in
[
For normalized KBs, the Datalog materialization calculus for SROE L(u; )
proposed by Kro¨tzsch [
Theorem 1. Instance checking under rational entailment in SROE L(u; )RT can be decided in polynomial time for normalized KBs.
Exploiting the approach presented in [
We now consider the notion of minimal canonical model in [
Definition 3 (Canonical models). A model M = h ; <; Ii of K is canonical if, for each set of SROE L(u; )RT concepts fC1; C2; : : : ; Cng S consistent with K (i.e., s.t. K 6j=sroelrt C1 u C2 u : : : u Cn v ?), there exists a domain element x 2 such that x 2 (C1 u C2 u : : : u Cn)I .
Among canonical models, we select the minimal ones according to the following preference relation over the set of ranked interpretations. An interpretation M =h ; <; Ii is preferred to M0 = h 0; <0; I0i (M M0) if: = 0; CI = CI0 for all concepts C; for all x 2 , kM(x) kM0 (x), and there exists y 2 such that kM(y) < kM0 (y). Definition 4 (Minimal entailment). M is a minimal canonical model of K if it is a canonical model of K and it is minimal among all the canonical models of K wrt. the preference relation . Given a query F , F is minimally entailed by K, written K j=min F if, for all minimal canonical models M of K, M satisfies F . Under minimal entailment, in Example 1 we can conclude 9hasHair :fBlack g(luigi ) and T(Young u Italian) v 9hasHair :fBlack g.
Theorem 2. Instance checking in SROE L(u; )RT under minimal entailment is CONPhard.
The proof is based on a reduction from tautology checking of propositional 3DNF formulae to instance checking in SROE L(u; )RT.
For KBs which only allow typicality concepts to occur on the left hand side of
typicality inclusions, and are in the language of ALC, the result in [