=Paper=
{{Paper
|id=Vol-1949/invited2
|storemode=property
|title=None
|pdfUrl=https://ceur-ws.org/Vol-1949/invited2.pdf
|volume=Vol-1949
}}
==None==
https://ceur-ws.org/Vol-1949/invited2.pdf
Reasoning about exceptions in ontologies: a skeptical
preferential approach (Extended Abstract)
Laura Giordano
DISIT, University of Piemonte Orientale “Amedeo Avogadro” - Italy -
laura.giordano@uniupo.it
1 Introduction
Reasoning about exceptions in ontologies is nowadays one of the challenges the de-
scription logics community is facing, a challenge which is at the very roots of the de-
velopment of non-monotonic reasoning in the 80s. Many non-monotonic extensions of
Description Logics (DLs) have been developed incorporating non-monotonic features
from most of the non-monotonic formalisms in the literature [1, 10, 12, 19, 5, 4, 7, 24,
11, 3, 20, 6, 18, 15, 16], or defining new constructions and semantics such as in [2].
The abstract describes a preferential approach for dealing with exceptions in de-
scription logics [14], where a typicality operator is used to select the typical (or most
preferred) instances of a concept. This approach, as well as the preferential approach
in [5], has been developed along the lines of the preferential semantics introduced by
Kraus, Lehmann and Magidor [21, 22].
We focus on the rational closure for DLs [7, 9, 6, 16] and, in particular, on the con-
struction developed in [16], which is semantically characterized by minimal preferential
models. While the rational closure provides a simple and efficient approach for reason-
ing with exceptions, exploiting polynomial reductions to standard DLs [13], the rational
closure does not allow an independent handling of the inheritance of different defeasi-
ble properties of concepts so that, if a subclass of C is exceptional for a given aspect, it
is exceptional tout court and does not inherit any of the typical properties of C.
To cope with this problem Lehmann [23] introduced the notion of the lexicographic
closure, which was extended to DLs by Casini and Straccia [8], while in [17] Gliozzi
proposed a semantic approach in which models are equipped with several preference
relations. The lexicographic closure allows for stronger inferences with respect to ratio-
nal closure, computing the defeasible consequences in the lexicographic closure may
require to compute several alternative bases [23](namely, consistent sets of defeasible
inclusions which are maximal with respect to some specificity ordering).
In this extendedabstract we propose an alternative notion of closure, the skeptical
closure, which can be regarded as a skeptical variant of the lexicographic closure. It is a
refinement of rational closure which allows for stronger inferences, but it is weaker than
the lexicographic closure and its computation does not require to generate all the alter-
native maximally consistent bases. The construction is based on the idea of building a
single base, i.e. a single maximal consistent set of defeasible inclusions, starting with
the defeasible inclusions with highest rank and progressively adding less specific inclu-
sions, if consistent, but excluding the defeasible inclusions which produce a conflict at
a certain stage without considering alternative consistent bases.
Laura Giordano
2 The rational closure
We briefly recall the logic ALC + TR which is at the basis of a rational closure con-
struction proposed in [16] for ALC. The idea underlying ALC + TR is that of extend-
ing the standard ALC with concepts of the form T(C), whose intuitive meaning is that
T(C) selects the typical instances of a concept C, to distinguish between the proper-
ties that hold for all instances of concept C (C ⊑ D), and those that only hold for
the typical such instances (T(C) ⊑ D). The ALC + TR language is defined as fol-
lows: CR := A | ⊤ | ⊥ | ¬CR | CR ⊓ CR | CR ⊔ CR | ∀R.CR | ∃R.CR , and
CL := CR | T(CR ), where A is a concept name and R a role name. A KB is a pair
(TBox, ABox). TBox contains a finite set of concept inclusions CL ⊑ CR . ABox con-
tains a finite set of assertions of the form CR (a) and aRb, for a, b individual names.
The semantics of ALC + TR is defined in terms of rational models: ordinary models of
ALC are equipped with a preference relation < on the domain, whose intuitive meaning
is to compare the “typicality” of domain elements: x < y means that x is more typical
than y. The instances of T(C) are the instances of concept C that are minimal with
respect to <. We refer to [16] for a detailed description of the semantics and we denote
by |=ALC+TR entailment in ALC + TR .
In [16] the rational closure construction has been defined for ALC + TR , extending
to DLs the notion of rational closure introduced by Lehmann and Magidor [22]. The
definition is based on the notion of exceptionality. Roughly speaking T(C) ⊑ D holds
in the rational closure of K if C is less exceptional than C ⊓ ¬D. We shortly recall this
construction of the rational closure of a TBox and we refer to [16] for full details.
Definition 1 (Exceptionality of concepts and inclusions). Let E be a TBox and C a
concept. C is exceptional for E if and only if E |=ALC+TR T(⊤) ⊑ ¬C. An inclusion
T(C) ⊑ D is exceptional for E if C is exceptional for E. The set of inclusions in TBox
which are exceptional for E will be denoted by E(E).
Given a TBox, it is possible to define a sequence of non increasing subsets of TBox
ordered according to the exceptionality of the elements E0 ⊇ E1 ⊇ E2 . . . by letting
E0 = TBox and, for i > 0, Ei = E(Ei−1 ) ∪ {C ⊑ 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 = ∅. A concept C has rank i (denoted rank (C) = i) for TBox, 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) = ∞ (C has no rank). Rational closure builds on this notion of exceptionality:
Definition 2 (Rational closure of TBox). Let KB = (TBox, ABox) be a DL knowl-
edge base. The rational closure of TBox is defined as: TBox = {T(C) ⊑ D |
either rank (C) < rank (C ⊓ ¬D) or rank (C) = ∞} ∪ {C ⊑ D | KB |=ALC+TR
C ⊑ D}, where C and D are ALC concepts.
Exploiting the fact that entailment in ALC + TR can be polynomially encoded into
entailment in ALC, it is easy to see that deciding if an inclusion T(C) ⊑ D belongs to
the rational closure of TBox is a problem in E XP T IME [16].
Example 1. Let K = {T(Student ) ⊑ ¬Pay Taxes, T(WStudent ) ⊑ Pay Taxes,
T(Student ) ⊑ Young, WStudent ⊑ Student} be a knowledge base stating that typ-
ical students do not pay taxes, but typical working students (which are students) do pay
Reasoning about exceptions in ontologies
taxes and that typical students are young. It is possible to see that E0 = {T(Student ) ⊑
¬Pay Taxes, T(Student ) ⊑ Young, WStudent ⊑ Student }, E1 = {T(WStudent )
⊑ Pay Taxes, WStudent ⊑ Student} and that the defeasible inclusions T(Student ⊓
Italian) ⊑ ¬Pay Taxes and T(WStudent ⊓ Italian) ⊑ Pay Taxes both belong, as
expected, to the rational closure of K, as being Italian is irrelevant with respect to being
or not a typical student. However, we cannot conclude that T(Student ) ⊑ Y oung : con-
cept WStudent is exceptional w.r.t. Student concerning the property of paying taxes
and, hence, it does not inherit any defeasible property of Student.
In the example above the rational closure is too weak to infer that typical working
students, as typical student, are young. The lexicographic closure [23] strengthens the
rational closure and allows to conclude that typical working students are young. The
property of typical students of being toung is inherited by working students, as it is
consistent with all the other (strict or defeasible) properties of working students.
3 From the lexicographic to the skeptical closure
Given a concept B, one wants to identify the defeasible properties of the B-elements.
Assume that the rational closure of the knowledge base K has already been constructed
and that k is the rank of concept B in the rational closure. The typical B elements
are clearly compatible with all the defeasible inclusions in Ek , but they might satisfy
further defeasible inclusions with lower ranks, i.e. those included in E0 , E1 , . . . , Ek−1 .
In general, there may be alternative maximal sets of defeasible inclusions compatible
with B, among which one would prefer those that maximize the number of defeasible
inclusions with higher rank. This is indeed what is done by the lexicographic closure
[23], which considers alternative maximally preferred sets of defaults called ”bases”,
which, roughly speaking, maximize the number of defaults of higher ranks with respect
to those lower ranks (degree of seriousness), and where situations which violate a num-
ber of defaults with a certain rank are considered to be less plausible than situations
which violates a lower number of defaults with the same rank. In general, there may be
exponentially many alternative sets of defeasible inclusions (bases) which are maximal
and consistent for a given concept, and the lexicographic closure has to consider all of
them to check if a defeasible inclusion is accepted. Instead, in the following, we aim
at defining a construction which skeptically builds a single set of defeasible inclusions
compatible with B.
Let S B be the set of typicality inclusions T(C) ⊑ D in K which are individually
compatible with B (with respect to Ek ), that is
S B = {T(C) ⊑ D ∈ TBox | Ek ∪ {T(C) ⊑ D} 6|=ALC+TR T(⊤) ⊑ ¬B}.
Clearly, although each defeasible inclusion in S B is compatible with B, it might be the
case that overall set S B is not compatible with B, i.e., Ek ∪S B |=ALC+TR T(⊤) ⊑ ¬B.
When compatible with B, S B is the unique maximal basis with respect to the seri-
ousness ordering [23]. Let δ(Ei ) denote the set of defeasible inclusions in Ei . When
S B is not compatible with B, we cannot use the defeasible inclusions in S B to derive
conclusions about typical B elements. In this case, we can either use just the defeasible
inclusions in Ek , as in the rational closure, or we can additionally use all the defeasible
B
inclusions in Sk−1 ∈ δ(Ek−1 ), with rank k − 1, provided they are compatible with B
Laura Giordano
B
and Ek and, possibly, we can add all the defeasible inclusions in Sk−2 ∈ δ(Ek−2 ) (with
B
rank k − 2) provided they are compatible with B, Ek and Sk−1 , and so on for lower
ranks. This leads to the construction below. For each rank j of the rational closure con-
struction, let SjB be a set of the defeasible inclusions in Ej as follows: SjB = {T(C) ⊑
B B B
D ∈ δ(Ej ) | Ek ∪ Sk−1 ∪ Sk−2 ∪ . . . ∪ Sj+1 ∪ {T(C) ⊑ D} 6|=ALC+TR T(⊤) ⊑ ¬B}
B
Informally, Sj is the set of the defeasible inclusions with rank j, which are not (indi-
vidually) overridden by defeasible inclusions with higher ranks (from j + 1 to k).
Definition 3. Let B be a concept such that rank (B) = k. We define the skeptical
closure S sk,B of B as follows: S sk,B = Ek ∪ Sk−1
B B
∪ Sk−2 ∪ . . . ∪ ShB , where h is the
least integer j such that 0 ≤ j ≤ k − 1 and Ek ∪ Sk−1 ∪ Sk−2 ∪ . . . ∪ SjB 6|=ALC+TR
B B
T(⊤) ⊑ ¬B, if such a j exists; S sk,B = Ek , otherwise.
Intuitively, S sk,B contains, for each rank j, all the defeasible inclusions having rank
j which are compatible with B and with the more specific defeasible inclusions (with
B B B
rank > j). As Sh−1 is not included in the skeptical closure, Ek ∪ Sk−1 ∪ Sk−2 ∪...∪
B B
Sh ∪ Sh−1 |=ALC+TR T(⊤) ⊑ ¬B i.e., the set Sh−1 contains conflicting defeasible
B
inclusions which are not overridden by more specific ones. The inclusions in Sh−1 (and,
similarly, all the defeasible inclusions with rank lower than h − 1) are not added to the
skeptical closure of B. Let us now define when a defeasible inclusion is derivable from
the skeptical closure of a TBox.
Definition 4. Let T(B) ⊑ D be a query and let k = rank (B) be the rank of concept
B in the rational closure. T(B) ⊑ D is derivable from the skeptical closure of TBox if
S sk,B |=ALC+TR T(⊤) ⊑ (¬B ⊔ D).
The identification of the defeasible inclusions in S sk,B requires a number of entail-
ment checks which is linear in the number of defeasible inclusions in TBox. In Ex-
ample 1 the inclusion T(WStudent ) ⊑ Young is derivable from the skeptical clo-
sure of TBox, as WStudent has rank 1 and inclusion T(Student ) ⊑ Young in E0
is compatible with WStudent. No other inclusions in δ(E0 ) are compatible with E1 .
Instead, the inclusion T(WStudent ) ⊑ Young is not derivable from the skeptical
closure of the KB K ′ = {T(Student ) ⊑ ¬Pay Taxes, T(Worker ) ⊑ Pay Taxes,
T(Student ) ⊑ Young, WStudent ⊑ Student ⊓ Worker }. as S0WStudent is not com-
patible with WStudent (w.r.t. E1 ), due to the conflicting defaults concerning tax pay-
ment for Worker and Student (both with rank 0). Hence, the defeasible property that
typical students are young is not inherited by typical working students.
Notice that, the property that typical working students are young is accepted in the
lexicographic closure of K ′ , as there are two bases (the one including T(Student ) ⊑
¬Pay Taxes and the other T(Worker ) ⊑ Pay Taxes), both containing T(Student )
⊑ Young. The skeptical closure is indeed weaker than the lexicographic closure. Also,
while in the logic DLN [2], given the knowledge base K ′ , the concept WStudent has an
inconsistent prototype, in the skeptical closure one cannot conclude that T(WStudent)
⊑ ⊥ and, using the terminology in [2], the conflict is “silently removed”. In this respect,
the skeptical closure appears to be weaker than DLN , although it shares with DLN (and
with lexicographic closure) a notion of overriding. Detailed comparisons and the study
of the semantics underlying the skeptical closure will be subject of future work.
Reasoning about exceptions in ontologies
References
1. F. Baader and B. Hollunder. Priorities on defaults with prerequisites, and their application in
treating specificity in terminological default logic. J. Autom. Reasoning , 15(1):41–68, 1995.
2. P. A. Bonatti, M. Faella, I. Petrova, and L. Sauro. A new semantics for overriding in descrip-
tion logics. Artif. Intell., 222:1–48, 2015.
3. P. A. Bonatti, M. Faella, and L. Sauro. Defeasible inclusions in low-complexity dls. J. Artif.
Intell. Res. (JAIR), 42:719–764, 2011.
4. P. A. Bonatti, Carsten Lutz, and Frank Wolter. The Complexity of Circumscription in DLs.
Journal of Artificial Intelligence Research (JAIR), 35:717–773, 2009.
5. K. Britz, J. Heidema, and T. Meyer. Semantic preferential subsumption. KR 2008, pages
476–484, Sidney, Australia, September 2008. AAAI Press.
6. G. Casini, T. Meyer, I. J. Varzinczak, , and K. Moodley. Nonmonotonic Reasoning in De-
scription Logics: Rational Closure for the ABox. DL 2013, CEUR, vol. 1014, pp. 600–615.
7. G. Casini and U. Straccia. Rational Closure for Defeasible Description Logics. JELIA 2010,
volume 6341 of LNCS, pages 77–90, Helsinki, Finland, September 2010. Springer.
8. G. Casini and U. Straccia. Lexicographic Closure for Defeasible Description Logics. In
Proc. of Australasian Ontology Workshop, vol.969, pages 28–39, 2012.
9. G. Casini and U. Straccia. Defeasible inheritance-based description logics. Journal of Artifi-
cial Intelligence Research (JAIR), 48:415–473, 2013.
10. F. M. Donini, D. Nardi, and R. Rosati. Description logics of minimal knowledge and negation
as failure. ACM Transactions on Computational Logic (ToCL), 3(2):177–225, 2002.
11. T. Eiter, G. Ianni, T. Lukasiewicz, and R. Schindlauer. Well-founded semantics for descrip-
tion logic programs in the semantic web. ACM Trans. Comput. Log., 12(2):11, 2011.
12. T. Eiter, G. Ianni, T. Lukasiewicz, R. Schindlauer, and H. Tompits. Combining answer set
programming with description logics for the semantic web. Artif. Intell., 172(12-13):1495–
1539, 2008.
13. L. Giordano and V. Gliozzi. Encoding a preferential extension of the description logic SROIQ
into SROIQ. In Proc. ISMIS 2015, volume 9384 of LNCS, pages 248–258. Springer, 2015.
14. L. Giordano, V. Gliozzi, N. Olivetti, and G. L. Pozzato. Preferential Description Logics. of
LPAR 2007, volume 4790 of LNAI, pages 257–272, Yerevan, Armenia, October 2007.
15. L. Giordano, V. Gliozzi, N. Olivetti, and G. L. Pozzato. A NonMonotonic Description Logic
for Reasoning About Typicality. Artificial Intelligence, 195:165–202, 2013.
16. L. Giordano, V. Gliozzi, N. Olivetti, and G. L. Pozzato. Semantic characterization of rational
closure: from propositional logic to description logics. Artif. Intell., 226:1–33, 2015.
17. V. Gliozzi. A strengthening of rational closure in DLs: reasoning about multiple aspects. DL
2016, CoRR abs/1604.00301, April 22-25, 2016, Cape Town.
18. G. Gottlob, A. Hernich, C. Kupke, and T. Lukasiewicz. Stable model semantics for guarded
existential rules and description logics. In Proc. KR 2014, 2014.
19. P. Ke and U. Sattler. Next Steps for Description Logics of Minimal Knowledge and Nega-
tion as Failure. In F. Baader, C. Lutz, and B. Motik, editors, DL 2008, CEUR Workshop
Proceedings, volume 353, Dresden, Germany, May 2008. CEUR-WS.org.
20. M. Knorr, P. Hitzler, and F. Maier. Reconciling owl and non-monotonic rules for the semantic
web. In ECAI 2012, page 474479, 2012.
21. S. Kraus, D. Lehmann, and M. Magidor. Nonmonotonic reasoning, preferential models and
cumulative logics. Artificial Intelligence, 44(1-2):167–207, 1990.
22. D. J. Lehmann and M. Magidor. What does a conditional knowledge base entail? Artificial
Intelligence, 55(1):1–60, 1992.
23. D. J. Lehmann. Another perspective on default reasoning. Ann. Math. Artif. Intell., 15(1):61–
82, 1995.
24. B. Motik and R. Rosati. Reconciling Description Logics and rules. J. ACM, 57(5), 2010.