We introduce a notion of rational closure for the logic SHIQ based on the well-known rational closure by Lehmann and Magidor [21]. 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. The growing interest of defeasible inference in ontology languages has led, in the last years, to the definition of many non-monotonic extensions of Description Logics (DLs) [23, 11, 19, 2, 20]. The best known semantics for nonmonotonic reasoning have been used to the purpose, from default logic [1], to circumscription [2], to Lifschitz's logic MKNF [10, 22], to preferential reasoning [4, 15], and to rational closure [5]. In this work, we focus on rational closure and, specifically, on the rational closure for S HIQ. Rational closure provides a significant and reasonable nonmonotonic inference mechanism for DLs, still remaining computationally inexpensive. As shown for ALC in [5], 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 the exception of some of them, such as [22, 20]. In particular, we define a rational closure for the logicS HIQ building on the notion of rational closure in [21] 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]. We provide a semantic characterization of rational closure in S HIQ in terms of a preferential semantics, generalizing to S HIQ the results for rational closure for ALC in [16]. This generalization is not trivial, since S HIQ lacks a crucial property of ALC, the finite model property. Our construction exploits an extension of S HIQ with a typicality operator T, that selects the most typical instances of a concept C, thus allowing defeasible inclusions of the form T(C) v D (the typical Cs are Ds) together with the standard (strict) inclusions C v D (all the Cs are Ds). We define aminimal model semantics and a notion of minimal entailment for the resulting logic, S HIQRT, 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 ? G. L. Pozzato is partially supported by the project ODIATI#1 “Ontologie, DIAgnosi e TIpicalit a` nelle logiche descrittive” of the local research funds 2013 by the Universit a` degli Studi di Torino - part B, supporting young researchers.
restrict to models with finite ranks. We can show that the rational closure construction of a TBox can be done exploiting entailment in SHIQ, without requiring to reason in SHIQRT, and that the problem of deciding if an inclusion belongs to the rational closure of a TBox is EXPTIME-complete. This abstract is based on the full paper [17]. 2
Following the approach in [13, 15], we define an extension, SHIQRT, of the logic SHIQ [18] introducing a typicality operator T to distinguish defeasible inclusions of the form T(C) v D, defining the (defeasible) properties of typical instances ofC, from strict properties of all instances of C (C v D).
We consider an alphabet of concept names C, role names R, transitive roles R+ ⊆ R, and individual constants O. Given A ∈ C, R ∈ 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 [18]. A KB is a pair (TBox, ABox). TBox contains a finite set of concept inclusionsCL 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 SHIQRT 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 members of a concept C, that is members of T(C), are the members x of C that are minimal with respect to this preference relation (s.t. there is no other member of C more typical than x).
hΔ, <, Ii where: Δ is the domain; < is an irreflexive, transitive, well-founded, and modular (for all x, y, z in Δ, if x < y then either x < z or z < y) relation over Δ; I is the extension function that maps each concept C to CI ⊆ Δ, and each role R to RI ⊆ ΔI × ΔI . For concepts of SHIQ, CI is defined as usual. For the T operator, we have (T(C))I = M in<(CI ), where M in<(S) = {u : u ∈ S and @z ∈ S s.t. z < u}. SHIQRT models can be equivalently defined by postulating the existence of a function kM : Δ 7−→ Ord , and then letting x < y if and only if kM(x) < kM(y). We call kM(x) the rank of element x in M. The rank kM(x) can be understood as the maximal length of a chain x0 < · · · < x from x to a minimal x0 (s.t. for no x0, x0 < x0). Observe that because of modularity all chains have the same length.
Definition 2 (Model satisfying a knowledge base). Given a SHIQRT model M= hΔ, <, Ii, we say that: - a model M satisfies an inclusion C v D if CI ⊆ DI ; similarly for role inclusions; - M satisfies an assertion C(a) if aI ∈ CI ; 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 satisfies KB if it satisfies both its TBox and its ABox.
Given a KB, we say that an inclusion CL v CR is derivable from KB, written KB |=SHIQRT CL v CR, if CLI ⊆ CRI holds in all models M =hΔ, <, Ii satisfying KB; similarly for role inclusions. We also say that an assertion CL(a), with a ∈ O, is derivable from KB, written KB |=SHIQRT CL(a), if aI ∈ CLI holds in all models M =hΔ, <, Ii satisfying KB.
Given a model M =hΔ, <, Ii, we define therank k (CR) of a concept CR in the model M as kM(CR) = min{kM(x) | x ∈ CRI }. If CMRI = ∅, then CR has no rank and we write kM(CR) = ∞. It is immediate to verify that: 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).
The typicality operator T itself is nonmonotonic, i.e., T(C) v D does not imply T(C u E) v D. This nonmonotonicity of T allows us 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 SHIQRT 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 SHIQRT, one cannot deal with irrelevance. For instance, one cannot derive from KB= {VIP v Person, T(Person) v ≤ 1 HasMarried .Person, T(VIP ) v ≥ 2 HasMarried .Person} that KB |=SHIQRT T(VIP u Tall ) v ≥ 2 HasMarried .Person, even if the property of being tall is irrelevant with respect to the number of marriages.
In order to overcome this weakness, we strengthen the semantics of SHIQRT by defining a minimal models mechanism which is similar, in spirit, to circumscription. Given a KB, the idea is to: 1. define apreference relation among SHIQRT models, giving preference to the model in which domain elements have a lower rank; 2. restrict entailment to minimal SHIQRT models (w.r.t. the above preference relation) of KB. Definition 3 (Minimal models). Given M =hΔ, <, Ii and M0 = hΔ0, <0, I0i, M is preferred to M0 (M <FIMS M0) if (i) Δ = Δ0, (ii) CI = CI0 for all concepts C, and (iii) for all x ∈ Δ, kM(x) ≤ kM0 (x) whereas there is y ∈ Δ s.t. kM(y) < kM0 (y). Given a KB, we say that M is a minimal model of KB w.r.t. <FIMS if it is a model satisfying KB and there is no M0 model satisfying KB s.t. M0 <FIMS M. Differently from [15], the notion of minimality here is based on the minimization of the ranks of the worlds, rather then on the minimization of formulas of a specific kind. It can be proved that a consistent KB has at least one minimal model and that satisfiability in SHIQRT is in EXPTIME such as satisfiability inSHIQ.
The logic SHIQRT, as well as the underlying logic SHIQ, does not enjoy the finite model property. However, we can prove that in any minimal model therank of each domain element is finite, which 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. 3
In this section, we extend to Description Logics the notion of rational closure proposed by Lehmann and Magidor [21] for the propositional case. Given the typicality operator, the typicality assertion T(C) v D plays the role of the conditional assertion C |∼ D in Lehmann and Magidor’s rational logic R.
concept. C is said to be exceptional for TB if and only if TB |=SHIQRT T(>) 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 ⊇ 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 = ∅. The definition of the Ei’s is similar the definition of the Ci’s in Lehmann and Magidor’s rational closure [21] except for the addition of strict inclusions.
Definition 5 (Rank of a concept). A concept C has rank i (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 us to define the rational closure of the TBox of a KB. We write KB |=SHIQ F to mean that F holds in all models of SHIQ. Definition 6 (Rational closure of TBox). Let KB=(TBox,ABox). 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}.
The rational closure of TBox is a nonmonotonic strengthening of SHIQRT which allows us to deal with irrelevance, as the following example shows. Let TBox = {T(Actor ) v Charming }. It can be verified thatT(Actor u Comic) v Charming ∈ TBox . This nonmonotonic inference does no longer follow if we discover that indeed comic actors are not charming (and in this respect are untypical actors): indeed given TBox0= TBox ∪ {T(Actor u Comic) v ¬Charming }, we have that T(Actor u Comic) v Charming 6∈ TBox 0. Also, as for the propositional case, rational closure is closed under rational monotonicity: from T(Actor ) v Charming ∈ TBox and T(Actor ) v Bold 6∈ TBox it follows that T(Actor u ¬Bold ) v Charming ∈ TBox .
of deciding whether T(C) v D ∈ TBox is in EXPTIME.
The proof of this result in [17] shows that the rational closure of a TBox can be computed using entailment in SHIQ, through a linear encoding of SHIQRT entailment. EXPTIME-completeness follows from the EXPTIME-hardness result for SHIQ [18]. 4
To provide a semantic characterization of this notion, we define a special class of minimal models, exploiting the fact that in all minimal SHIQRT models the rank of each domain element is always finite. First of all, we observe that the minimal model semantics in Definition 3 as it is cannot capture the rational closure of a TBox.
Consider the TBox containing: 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 SHIQRT models of KB w.r.t. Definition 3. Indeed there can be a model M = hΔ, <, Ii in which Δ = {x, y, z}, VIP I = {x, y}, PersonI = {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 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 thatT(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. Let S be the set of all the concepts (and subconcepts) occurring in KB or in the query F together with their complements.
Definition 7 (Canonical model). 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 consistent with KB, i.e. KB 6|=SHIQRT C1 u C2 u · · · u Cn v ⊥. In order to semantically characterize the rational closure of a SHIQRT KB, we restrict our attention to minimal canonical models. Existence of minimal canonical models can be proved for any (finite) satisfiable KB. Let us first introduce the following proposition, which defines a correspondence between the rank of a formula in the rational closure and the rank of a formula in a model (the proof is by induction on the rank i): Proposition 2. 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 2. 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. 5
In this work we have proposed an extension of the rational closure defined by Lehmann and Magidor to the Description Logic SHIQ, taking into account both TBox reasoning (ABox reasoning is addressed in [17]). There is a number of closely related proposals.
In [13, 15] nonmonotonic extensions of ALC with the typicality operator T have been proposed, whose semantics of T is based on the preferential logic P. The notion of minimal model adopted here is completely independent from the language and is determined only by the relational structure of models.
The first notion of rational closure for DLs was defined by Casini and Straccia in
[
The rational closure construction in itself can be applied to any description logic.
As future work, we aim to extend it and its semantic characterization to stronger logics,
such as SHOIQ, for which the correspondence between the rational closure and the
minimal canonical model semantics of the previous sections cannot be established
straightforwardly, due to the interaction of nominals with number restrictions. Also, we
aim to consider a finer semantics where models are equipped with several preference
relations; in such a semantics it might be possible to relativize the notion of typicality,
whence to reason about typical properties independently from each other. The aim is
to overcome some limitations of rational closure, as done in [
98(1-2), 209–235 (1998) 13. Giordano, L., Gliozzi, V., Olivetti, N., Pozzato, G.L.: ALC+T: a preferential extension of
Description Logics. Fundamenta Informaticae 96, 1–32 (2009) 14. Giordano, L., Gliozzi, V., Olivetti, N., Pozzato, G.L.: A minimal model semantics for nonmonotonic reasoning. In: Luis Farin˜as del Cerro, Andreas Herzig, J.M. (ed.) Proc. of JELIA 2012. LNAI, vol. 7519, pp. 228–241. Springer-Verlag, Toulouse, France (Sptember 2012) 15. Giordano, L., Gliozzi, V., Olivetti, N., Pozzato, G.L.: A NonMonotonic Description Logic for
Reasoning About Typicality. Artificial Intelligence 195, 165–202 (2013) 16. Giordano, L., Gliozzi, V., Olivetti, N., Pozzato, G.L.: Minimal Model Semantics and Rational Closure in Description Logics . In: Eiter, T., Glim, B., Kazakov, Y., Krtzsch, M. (eds.) Proc. of Description Logics (DL 2013). CEUR Workshop Proc., vol. 1014, pp. 168 – 180. 17. Giordano, L., Gliozzi, V., Olivetti, N., Pozzato, G.L.: Rational Closure in SHIQ. In: DL 2014, 27th International Workshop on Description Logics. To appear (2014) 18. Horrocks, I., Sattler, U., Tobies, S.: Practical reasoning for very expressive description logics.
Logic Journal of the IGPL 8(3), 239–263 (2000) 19. Ke, P., Sattler, U.: Next Steps for Description Logics of Minimal Knowledge and Negation as Failure. In: Baader, F., Lutz, C., Motik, B. (eds.) Proc. of Description Logics. CEUR Workshop Proceedings, vol. 353. CEUR-WS.org, Dresden, Germany (May 2008) 20. Krisnadhi, A.A., Sengupta, K., Hitzler, P.: Local closed world semantics: Keep it simple, stupid! In: Proc. of Description Logics (DL 2011). CEUR Workshop Proceedings, vol. 745. 21. Lehmann, D., Magidor, M.: What does a conditional knowledge base entail? Artificial Intelligence 55(1), 1–60 (1992) 22. Motik, B., Rosati, R.: Reconciling Description Logics and rules. J. of the ACM 57(5) (2010) 23. Straccia, U.: Default inheritance reasoning in hybrid kl-one-style logics. In: Bajcsy, R. (ed.) Proc. of IJCAI 1993, pp. 676–681. Morgan Kaufmann, Chambe´ry, France (August 1993)