Rational closure in SHIQ Laura Giordano1 , Valentina Gliozzi2 , Nicola Olivetti3 , and Gian Luca Pozzato2 1 DISIT - U. Piemonte Orientale, Alessandria, Italy - laura@mfn.unipmn.it 2 Dip. di Informatica - Univ. di Torino, Italy - {gliozzi,pozzato}@di.unito.it 3 Aix-Marseille Université, CNRS, France nicola.olivetti@univ-amu.fr Abstract. We define a notion of rational closure for the logic SHIQ, which does not enjoys the finite model property, building on the notion of rational closure introduced by Lehmann and Magidor in [24]. We provide a semantic characterization of rational closure in SHIQ in terms of a preferential semantics, based on a finite rank characterization of minimal models. We show that the rational closure of a TBox can be computed in E XP T IME using entailment in SHIQ. 1 Introduction Recently, a large amount of work has been done in order to extend the basic formalism of Description Logics (for short, DLs) with nonmonotonic reasoning features [27, 1, 10, 11, 13, 17, 21, 4, 2, 6, 26, 23]; the purpose of these extensions is that of allowing reasoning about prototypical properties of individuals or classes of individuals. In these extensions one can represent, for instance, knowledge expressing the fact that the hematocrit level is usually under 50%, with the exceptions of newborns and of males residing at high altitudes, that have usually much higher levels (even over 65%). Furthermore, one can infer that an individual enjoys all the typical properties of the classes it belongs to. As an example, in the absence of information that Carlos and the son of Fernando are either newborns or adult males living at a high altitude, one would assume that the hematocrit levels of Carlos and Fernando’s son are under 50%. This kind of inferences apply to individual explicitly named in the knowledge base as well as to individuals implicitly introduced by relations among individuals (the son of Fernando). In spite of the number of works in this direction, finding a solution to the problem of extending DLs for reasoning about prototypical properties seems far from being solved. The most well known semantics for nonmonotonic reasoning have been used to the purpose, from default logic [1], to circumscription [2], to Lifschitz’s nonmonotonic logic MKNF [10, 26], to preferential reasoning [13, 4, 17], to rational closure [6, 9]. In this work, we focus on rational closure and, specifically, on the rational closure for SHIQ. The interest of rational closure in DLs is that it provides a significant and reasonable nonmonotonic inference mechanism, still remaining computationally inexpensive. As shown for ALC in [6], its complexity can be expected not to exceed the one of the underlying monotonic DL. This is a striking difference with most of the other approaches to nonmonotonic reasoning in DLs mentioned above, with some exception such as [26, 23]. More specifically, we define a rational closure for the logic SHIQ, building on the notion of rational closure in [24] for propositional logic. This is a difference with respect to the rational closure construction introduced in [6] for ALC, which is more similar to the one by Freund [12] for propositional logic (for propositional logic, the two definitions of rational closure are shown to be equivalent [12]). We provide a semantic characterization of rational closure in SHIQ in terms of a preferential semantics, by generalizing to SHIQ the results for rational closure in ALC presented in [18]. This generalization is not trivial, since SHIQ lacks a crucial property of ALC, the finite model property [20]. Our construction exploits an extension of SHIQ with a typicality operator T, that selects the most typical instances of a concept C, T(C). We define a minimal model semantics and a notion of minimal entailment for the resulting logic, SHIQR T, and we show that the inclusions belonging to the rational closure of a TBox are those minimally entailed by the TBox, when restricting to canonical models. This result exploits a characterization of minimal models, showing that we can restrict to models with finite ranks. We also show that the rational closure construction of a TBox can be done exploiting entailment in SHIQ, without requiring to reason in SHIQR T, and that the problem of deciding whether an inclusion belongs to the rational closure of a TBox is in E XP T IME. Concerning ABox reasoning, because of the interaction between individuals (due to roles) it is not possible to separately assign a unique minimal rank to each individual and alternative minimal ranks must be considered. We end up with a kind of skeptical inference with respect to the ABox, whose complexity in E XP T IME as well. For an extended version of this paper with the proofs of the results see [19]. 2 A nonmonotonic extension of SHIQ Following the approach in [14, 17], we introduce an extension of SHIQ [20] with a typicality operator T in order to express typical inclusions, obtaining the logic SHIQR T. The intuitive idea is to allow concepts of the form T(C), whose intuitive meaning is that T(C) selects the typical instances of a concept C. We can therefore distinguish between the properties that hold for all instances of C (C v D), and those that only hold for the typical such instances (T(C) v D). Since we are dealing here with rational closure, we attribute to T properties of rational consequence relation [24]. We consider an alphabet of concept names C, role names R, transitive roles R+ ⊆ R, and individual constants O. Given A ∈ C, S ∈ R, and n ∈ N we define: CR := A | > | ⊥ | ¬CR | CR u CR | CR t CR | ∀S.CR | ∃S.CR | (≥ nS.CR ) | (≤ nS.CR ) CL := CR | T(CR ) S := R | R− As usual, we assume that transitive roles cannot be used in number restrictions [20]. A KB is a pair (TBox, ABox). TBox contains a finite set of concept inclusions CL v CR and role inclusions R v S. ABox contains assertions of the form CL (a) and S(a, b), where a, b ∈ O. The semantics of SHIQR T is formulated in terms of rational models: ordinary models of SHIQ are equipped with a preference relation < on the domain, whose intuitive meaning is to compare the “typicality” of domain elements, that is to say, x < y means that x is more typical than y. Typical instances of a concept C (the instances of T(C)) are the instances x of C that are minimal with respect to the preference relation < (so that there is no other instance of C preferred to x)4 . 4 As for the logic ALC R T in [15], an alternative semantic characterization of T can be given by means of a set of postulates that are essentially a reformulation of the properties of rational consequence relation [24]. Definition 1 (Semantics of SHIQR T). A SHIQR T model M is any structure h∆, < , Ii where: ∆ is the domain; < is an irreflexive, transitive, well-founded, and modular (for all x, y, z ∈ ∆, if x < y then x < z or z < y) relation over ∆; I is the extension function that maps each concept C to C I ⊆ ∆, and each role R to RI ⊆ ∆I × ∆I . For concepts of SHIQ, C I is defined as usual. For the T operator, we have (T(C))I = M in< (C I ), where M in< (S) = {u : u ∈ S and @z ∈ S s.t. z < u}. As for rational models in [24] (see Lemma 14), SHIQR T models can be equivalently defined by postulating the existence of a function kM : ∆ 7−→ Ord assigning an ordinal to each domain element, and then letting x < y if and only if kM (x) < kM (y). We call kM (x) the rank of element x in M. When finite, kM (x) can be understood as the length of a chain x0 < · · · < x from x to a minimal x0 (an x0 s.t. for no x0 , x0 < x0 ). Definition 2 (Model satisfying a knowledge base). Given a SHIQR T model M= h∆, <, Ii, we say that: - a model M satisfies an inclusion C v D if C I ⊆ DI ; similarly for role inclusions; - M satisfies an assertion C(a) if aI ∈ C I ; and M satisfies an assertion R(a, b) if (aI , bI ) ∈ RI . Given a KB=(TBox,ABox), we say that: M satisfies TBox if M satisfies all inclusions in TBox; M satisfies ABox if M satisfies all assertions in ABox; M is a model of KB if it satisfies both its TBox and its ABox. The logic SHIQR T, as well as the underlying SHIQ, does not enjoy the finite model property [20]. Given a KB, let F be an inclusion or an assertion. We say that F is entailed by KB, written KB |=SHIQR T F , if for all models M =h∆, <, Ii of KB, M satisfies F . Let us now introduce the notions of rank of a SHIQ concept. Definition 3 (Rank of a concept kM (CR )). Given a model M =h∆, <, Ii, we define the rank kM (CR ) of a concept CR in the model M as kM (CR ) = min{kM (x) | x ∈ CR I }. If CR I = ∅, then CR has no rank and we write kM (CR ) = ∞. Proposition 1. For any M =h∆, <, Ii, we have that M satisfies T(C) v D if and only if kM (C u D) < kM (C u ¬D). It is immediate to verify that the typicality operator T itself is nonmonotonic: T(C) v D does not imply T(C u E) v D. This nonmonotonicity of T allows to express the properties that hold for the typical instances of a class (not only the properties that hold for all the members of the class). However, the logic SHIQR T is monotonic: what is inferred from KB can still be inferred from any KB’ with KB ⊆ KB’. This is a clear limitation in DLs. As a consequence of the monotonicity of SHIQR T, one cannot deal with irrelevance. For instance, KB= {VIP v Person, T(Person) v ≤ 1 HasMarried .Person, T(VIP ) v ≥ 2 HasMarried .Person} does not entail KB |=SHIQR T T(VIP u Tall ) v ≥ 2 HasMarried .Person, even if the property of being tall is irrelevant with respect to the number of marriages. Observe that we do not want to draw this conclusion in a monotonic way from SHIQR T, since otherwise we would not be able to retract it when knowing, for instance, that typical tall VIPs have just one marriage (see also Example 1). Rather, we would like to obtain this conclusion in a nonmonotonic way. In order to obtain this nonmonotonic behavior, we strengthen the semantics of SHIQR T by defining a minimal models mechanism which is similar, in spirit, to circumscription. Given a KB, the idea is to: 1. define a preference relation among SHIQR T models, giving preference to the model in which domain elements have a lower rank; 2. restrict entailment to minimal SHIQR T models (w.r.t. the above preference relation) of KB. Definition 4 (Minimal models). Given M =h∆, <, Ii and M0 = h∆0 , <0 , I 0 i we say 0 that M is preferred to M0 (M ) v ¬C. A T-inclusion T(C) v D is exceptional for TB if C is exceptional for TB . The set of T-inclusions of TB which are exceptional in TB will be denoted as E(TB ). Given a DL KB=(TBox,ABox), it is possible to define a sequence of non increasing subsets of TBox E0 ⊇ E1 , E1 ⊇ E2 , . . . by letting E0 = TBox and, for i > 0, Ei = E(Ei−1 ) ∪ {C v D ∈ TBox s.t. T does not occurr in C}. Observe that, being KB finite, there is an n ≥ 0 such that, for all m > n, Em = En or Em = ∅. Observe also that the definition of the Ei ’s is the same as the definition of the Ci ’s in Lehmann and Magidor’s rational closure [22], except for that here, at each step, we also add all the “strict” inclusions C v D (where T does not occur in C). Definition 6 (Rank of a concept). A concept C has rank i (denoted by rank (C) = i) for KB=(TBox,ABox), iff i is the least natural number for which C is not exceptional for Ei . If C is exceptional for all Ei then rank (C) = ∞, and we say that C has no rank. The notion of rank of a formula allows to define the rational closure of the TBox of a KB. Let |=SHIQ be the entailment in SHIQ. In the following definition, by KB |=SHIQ F we mean KF |=SHIQ F , where KF does not include the defeasible inclusions in KB. Definition 7 (Rational closure of TBox). Let KB=(TBox,ABox) be a DL knowledge base. We define, TBox , the rational closure of TBox, as TBox = {T(C) v D | either rank (C) < rank (C u ¬D) or rank (C) = ∞} ∪ {C v D | KB |=SHIQ C v D}, where C and D are arbitrary SHIQ concepts. Observe that, apart form the addition of strict inclusions, the above definition of rational closure is the same as the one by Lehmann and Magidor in [24]. The rational closure of TBox is a nonmonotonic strengthening of SHIQR T. For instance, it allows to deal with irrelevance, as the following example shows. Example 1. Let TBox = {T(Actor ) v Charming}. It can be verified that T(Actor u Comic) v Charming ∈ TBox . This is a nonmonotonic inference that does no longer follow if we discover that indeed comic actors are not charming (and in this respect are untypical actors): indeed given TBox’= TBox ∪ {T(Actor u Comic) v ¬Charming}, we have that T(Actor u Comic) v Charming 6∈ TBox 0 . Furthermore, as for the propositional case, rational closure is closed under rational monotonicity [22]: from T(Actor ) v Charming ∈ TBox and T(Actor ) v Bold 6∈ TBox it follows that T(Actor u ¬Bold ) v Charming ∈ TBox . Although the rational closure TBox is an infinite set, its definition is based on the construction of a finite sequence E0 , E1 , . . . , En of subsets of TBox, and the problem of verifying that an inclusion T(C) v D ∈ TBox is in E XP T IME. Let us first prove the following proposition: Proposition 3. Let KB=(TBox,∅) be a knowledge base with empty ABox. KB |=SHIQR T CL v CR iff KB 0 |=SHIQ CL0 v CR 0 , where KB 0 , CL0 and CR 0 are polynomial encod- ings in SHIQ of KB, CL and CR , respectively. Proof. (Sketch) First of all, let us remember that rational entailment is equivalent to preferential entailment for a knowledge base only containing positive non-monotonic implications A |∼ B (see [24]).The same holds in preferential description logics with typicality. Let SHIQP T be the logic that we obtain when we remove the requirement of modularity in the definition of SHIQR T. In this logic the typicality operator has a preferential semantics [22], based on the preferential models of P rather then on the ranked models of R [22]. It is possible to prove that entailment in SHIQR T and entailment in SHIQP T are equivalent if we restrict to KBs with empty ABox, as TBox contains inclusions (positive non-monotonic implications). Hence, to prove the thesis it suffices to show that for all inclusions CL v CR in SHIQR T: KB |=SHIQP T CL v CR iff KB 0 |=SHIQ CL0 v CR 0 , for some polynomial encoding KB 0 , CL0 , CR 0 in SHIQ . The idea of the encoding exploits the definition of the typicality operator T intro- duced in [14] (for ALC), in terms of a Gödel -Löb modality 2 as follows: T(C) is defined as C u 2¬C where the accessibility relation of the modality 2 is the preference relation < in preferential models. We define the encoding KB’=(TBox’, ABox’) of KB in SHIQ as follows. First, ABox’=∅. For each A v B ∈ TBox, not containing T, we introduce A v B in TBox’. For each T(A) in occurring in the TBox, we introduce a new atomic concept 2¬A and, for each inclusion T(A) v B ∈ TBox, we add to TBox’ the inclusion: A u 2¬A v B. Furthermore, to capture the properties of the 2 modality, a new role R is introduced to represent the relation < in preferential models, and the following inclusions are introduced in TBox’: 2¬A v ∀R.(¬A u 2¬A ) and ¬2¬A v ∃R.(A u 2¬A ). 0 For the inclusion CL v CR , we let CR = CR . For a strict inclusion (CL 6= T (A)), we let CL = CL , while for a defeasible inclusion (CL = T (A)), we let CL0 = A u 2¬A . 0 It is clear that the size of KB’ is polynomial in the size of the KB. Given the above encoding, it can be proved that: KB |=SHIQP T CL v CR iff KB 0 |=SHIQ CL0 v CR 0 . 2 Theorem 2 (Complexity of rational closure over TBox). Given a TBox, the problem of deciding whether T(C) v D ∈ TBox is in E XP T IME. Proof. Checking if T(C) v D ∈ TBox can be done by computing the finite sequence E0 , E1 , . . . , En of non increasing subsets of TBox inclusions in the construction of the rational closure. Note that the number n of the Ei is O(|KB|), where |KB| is the size of the knowledge base KB. Computing each Ei = E(Ei−1 ), requires to check, for all concepts A occurring on the left hand side of an inclusion in the TBox, whether Ei−1 |=SHIQR T T(>) v ¬A. Regarding Ei−1 as a knowledge base with empty ABox, by Proposition 3 it is enough to check that Ei−1 0 |=SHIQ > t 2¬> v ¬A, which 0 requires an exponential time in the size of Ei−1 (and hence in the size of KB). If not already checked, the exceptionality of C and of C u ¬D have to be checked for each Ei , to determine the ranks of C and of C u ¬D (which can be computed in SHIQ as well). Hence, verifying if T(C) v D ∈ TBox is in E XP T IME. 2 The above proof also shows that the rational closure of a TBox can be computed simply using the entailment in SHIQ. 4 Infinite Minimal Models with finite ranks In the following we provide a characterization of minimal models of a KB in terms of their rank: intuitively minimal models are exactly those where each domain element has rank 0 if it satisfies all defeasible inclusions, and otherwise has the smallest rank greater than the rank of any concept C occurring in a defeasible inclusion T(C) v D of the KB falsified by the element. Exploiting this intuitive characterization of minimal models, we are able to show that, for a finite KB, minimal models have always a finite ranking function, no matter whether they have a finite domain or not. This result allows us to provide a semantic characterization of rational closure of the previous section to logics, like SHIQ, that do not have the finite model property. Given a model M = h∆, <, Ii, let us define the set SxM of defeasible inclusions falsified by a domain element x ∈ ∆, as SxM = {T(C) v D ∈ KD | x ∈ (C u¬D)I }}. Proposition 4. Let M = h∆, <, Ii be a model of KB and x ∈ ∆, then: (a) if kM (x) = 0 then SxM = ∅; (b) if SxM 6= ∅ then kM (x) > kM (C) for every C such that, for some D, T(C) v D ∈ SxM . Let us define KF = {C v D ∈ T Box : T does not occur in C} ∪ ABox and KD = {T(C) v D ∈ T Box}, so that KB = KF ∪ KD . Proposition 5. Let KB = KF ∪ KD and M = h∆, <, Ii be a model of KF ; suppose that for any x ∈ ∆ it holds that: - if kM (x) = 0 then SxM = ∅; - if SxM 6= ∅ then kM (x) > kM (C) for every C s.t., for some D, T(C) v D ∈ SxM . Then M |= KB. From Propositions 4 and 5, we obtain the following characterization of minimal models. Theorem 3. Let KB = KF ∪ KD , and let M = h∆, <, Ii be a model of KF . The following are equivalent: – M is a minimal model of KB – For every x ∈ ∆ it holds: (a) SxM = ∅ iff kM (x) = 0 (b) if SxM 6= ∅ then kM (x) = 1 + max{kM (C) | T(C) v D ∈ SxM }. The following proposition shows that in any minimal model the rank of each domain element is finite. Proposition 6. Let KB = KF ∪ KD and M = h∆, <, Ii a minimal model of KB, for every x ∈ ∆, kM (x) is a finite ordinal (kM (x) < ω). The previous proposition is essential for establishing a correspondence between the minimal model semantics of a KB and its rational closure. From now on, we can assume that the ranking function assigns to each domain element in ∆ a natural number, i.e. that kM : ∆ −→ N. 5 A Minimal Model Semantics for Rational Closure in SHIQ In previous sections we have extended to SHIQ the syntactic notion of rational closure introduced in [24] for propositional logic. To provide a semantic characterization of this notion, we define a special class of minimal models, exploiting the fact that, by Proposition 6, in all minimal SHIQR T models the rank of each domain element is always finite. First of all, we can observe that the minimal model semantics in Definition 4 as it is cannot capture the rational closure of a TBox. Consider the following KB = (TBox, ∅), where TBox contains: VIP v Person, T(Person) v ≤ 1 HasMarried .Person, T(VIP ) v ≥ 2 HasMarried . Person. We observe that T(VIP u Tall ) v ≥ 2 HasMarried .Person does not hold in all minimal SHIQR T models of KB w.r.t. Definition 4. Indeed there can be a model M = h∆, <, Ii in which ∆ = {x, y, z}, VIP I = {x, y}, Person I = {x, y, z}, (≤ 1 HasMarried . Person)I = {x, z}, (≥ 2 HasMarried .Person)I = {y}, Tall I = {x}, and z < y < x. M is a model of KB, and it is minimal. Also, x is a typical tallVIP in M (since there is no other tall VIP preferred to him) and has no more than one spouse, therefore T(VIP u Tall ) v ≥ 2 HasMarried .Person does not hold in M. On the contrary, it can be verified that T(VIP u Tall ) v ≥ 2 HasMarried .Person ∈ TBox . Things change if we consider the minimal models semantics applied to models that contain a domain element for each combination of concepts consistent with KB. We call these models canonical models. Therefore, in order to semantically characterize the rational closure of a SHIQR T KB, we restrict our attention to minimal canonical models. First, we define S as the set of all the concepts (and subconcepts) occurring in KB or in the query F together with their complements. In order to define canonical models, we consider all the sets of concepts {C1 , C2 , . . . , Cn } ⊆ S that are consistent with KB, i.e., s.t. KB 6|=SHIQR T C1 u C2 u · · · u Cn v ⊥. Definition 8 (Canonical model with respect to S). Given KB=(TBox,ABox) and a query F , a model M =h∆, <, Ii satisfying KB is canonical with respect to S if it contains at least a domain element x ∈ ∆ s.t. x ∈ (C1 u C2 u · · · u Cn )I , for each set of concepts {C1 , C2 , . . . , Cn } ⊆ S that is consistent with KB. Next we define the notion of minimal canonical model. Definition 9 (Minimal canonical models (w.r.t. S)). M is a minimal canonical model of KB if it satisfies KB, it is minimal (with respect to Definition 4) and it is canonical (as defined in Definition 8). Proposition 7 (Existence of minimal canonical models). Let KB be a finite knowledge base, if KB is satisfiable then it has a minimal canonical model. To prove the correspondence between minimal canonical models and the rational clo- sure of a TBox, we need to introduce some propositions. The next one concerns all SHIQR T models. Given a SHIQR T model M =h∆, <, Ii, we define a sequence M0 , M1 , M2 , . . . of models as follows: We let M0 = M and, for all i, we let Mi = h∆, i, and kMi (x) = 0 otherwise. We can prove the following: Proposition 8. Let KB= hT Box, ABoxi and let M =h∆, <, Ii be any SHIQR T model of TBox. For any concept C, if rank(C) ≥ i, then 1) kM (C) ≥ i, and 2) if T(C) v D is entailed by Ei , then Mi satisfies T(C) v D. Let us now focus our attention on minimal canonical models by proving the correspon- dence between rank of a formula (as in Definition 6) and rank of a formula in a model (as in Definition 3). The following proposition is proved by induction on the rank i: Proposition 9. Given KB and S, for all C ∈ S, if rank (C) = i, then: 1. there is a {C1 . . . Cn } ⊆ S maximal and consistent with KB such that C ∈ {C1 . . . Cn } and rank (C1 u · · · u Cn ) = i; 2. for any M minimal canonical model of KB, kM (C) = i. The following theorem follows from the propositions above: Theorem 4. Let KB=(TBox,ABox) be a knowledge base and C v D a query. We have that C v D ∈ TBox if and only if C v D holds in all minimal canonical models of KB with respect to S. 6 Rational Closure over the ABox The definition of rational closure in Section 3 takes only into account the TBox. We address the issue of ABox reasoning first by the semantical side: as for any domain element, we would like to attribute to each individual constant named in the ABox the lowest possible rank. Therefore we further refine Definition 9 of minimal canonical models with respect to TBox by taking into account the interpretation of individual constants of the ABox. Definition 10 (Minimal canonical model w.r.t. ABox). Given KB=(TBox,ABox), let M =h∆, <, Ii and M0 = h∆0 , <0 , I 0 i be two canonical models of KB which are minimal w.r.t. Definition 9. We say that M is preferred to M0 w.r.t. ABox (M