=Paper=
{{Paper
|id=Vol-477/paper-57
|storemode=property
|title=Quasi-Classical Semantics for Expressive Description Logics
|pdfUrl=https://ceur-ws.org/Vol-477/paper_1.pdf
|volume=Vol-477
|dblpUrl=https://dblp.org/rec/conf/dlog/ZhangQML09
}}
==Quasi-Classical Semantics for Expressive Description Logics==
https://ceur-ws.org/Vol-477/paper_1.pdf
Quasi-Classical Semantics for Expressive Description
Logics?
Xiaowang Zhang1,4 , Guilin Qi2 , Yue Ma3 and Zuoquan Lin1
1
School of Mathematical Sciences, Peking University, Beijing 100871, China
2
Institute AIFB, University of Karlsruhe, Karlsruhe 76131, Germany
3
Laboratoire d’Informatique de l’universit Paris-Nord (LIPN) - UMR 7030, France
4
School of Mathematical Sciences, Anhui University, Hefei 230039, China
{zxw,lzq }@is.pku.edu.cn, GQI@aifb.uni-karlsruhe.de, Yue.Ma@lipn.univ-paris13.fr
Abstract. Inconsistency handling in expressive description logics is an impor-
tant problem because inconsistency may naturally occur in an open world. In this
paper, we first present the quasi-classical semantics for description logic SHIQ,
which is based on quasi-classical logic. We show that this semantics can be used
to deal with inconsistency and that it is reduced to the standard semantics when
there is no inconsistency. Compared with the existing four-valued semantics for
description logics, it strengthens the reasoning capability in the sense that it can
satisfy some important inference rules, such as Modus Ponens. Finally, we ana-
lyze the computational complexity of consistency checking based on the quasi-
classical semantics.
1 Introduction
In an open, constantly changing and collaborative environment like the forthcoming
Semantic Web, a knowledge base (or an ontology) may well contain inconsistencies
because of many reasons, such as modeling errors, migration from other formalisms,
merging ontologies, and ontology evolution (see [1]). As the logical foundation of On-
tology Web Language (OWL), expressive description logics (for short DLs) fail to tol-
erate inconsistent data. Therefore, handling inconsistency in expressive DLs, such as
SHIQ, is becoming an important topic in recent years.
There are two fundamentally different approaches to handling inconsistency. One is
to repair inconsistency in ontologies to obtain consistent ontologies [2,3,4]. The other,
called paraconsistent approach, does not simply repair inconsistencies but applies a non-
standard reasoning to obtain meaningful answers from inconsistent ontologies [5,6]. For
the latter, having inconsistencies is treated as a natural phenomenon in realistic data and
is tolerated during reasoning, whilst inconsistencies are viewed as erroneous data for the
first approach. So far, the main idea of paraconsistent methods for handling inconsistent
ontologies [5] is based on Belnap’s four-valued semantics [7]. However their reasoning
capability is rather weak [6]. For instance, they fail in holding some important inference
rules, such as Modus Ponens, Modus Tollens and Disjunctive Syllogism. In [6], a total
negation is introduced to enable the resolution principle for paraconsistent reasoning
?
This paper is supported by the EU under the IST project NeOn.
in four-valued DLs. However, four-valued DLs with total negation still don’t satisfy
some intuitive equivalences mentioned above. The main problem of four-valued DLs
is that they can not overcome those inherent shortcomings of four-valued semantics in
reasoning [7].
To avoid shortcomings of four-valued DLs and strengthen paraconsistent reason-
ing capability, in this paper, following [8], we study a quasi-classical description logic
SHIQ (QC SHIQ for short), which is based on quasi-classical logic [9,10] and de-
scription logic (for short DL) SHIQ. We concentrate on SHIQ since it is the core of
OWL DL [11,12]. Main contributions of this paper are summarized as follows:
– QC semantics is introduced to SHIQ to handle inconsistent ontologies. It com-
poses of two kinds of semantics, namely, QC weak semantics |=w and QC strong
semantics |=s . QC weak semantics inherits the characteristics of four-valued se-
mantics and QC strong semantics redefines the interpretation for disjunction and
conjunction of concepts to make the three important inference rules hold.
– A new notion called complement of concept is introduced. We use C to denote
the complement of concept C. The semantics of an inclusion axiom defined under
the weak semantics and the strong semantics satisfy the intuitive equivalences. For
instance, I |=w C v D iff I |=w C tD(a); and I |=s C v D iff I |=s ¬C tD(a)
for any individual a.
– A QC model is defined to express a possible world under QC strong semantics. A
QC entailment based on QC model, written by “|=Q ”, between an ontology and an
axiom is presented which is shown to be able to handle inconsistency. Compared
with the four-valued DLs, QC DLs satisfy three important inference rules: Modus
Ponens (MP): {C(a), C v D} |=Q D(a), Modus Tollens (MT): {¬D(a), C v
D} |=Q ¬C(a), and Disjunctive Syllogism (DS): {¬C(a), C t D} |=Q D(a).
– Two basic query entailment problems, namely, instance checking and subsumption
checking are defined and discussed. We show that the two basic inference problems
can be reduced into the QC consistency problem.
– We prove that the complexity of deciding QC consistency for an ABox is EXPTIME-
Complete.
Compared with QC ALC studied in [13], QC SHIQ studied in this paper has the fol-
lowing significant improvements: (1) we redefine the QC strong semantics of concept
inclusion C1 v C2 so that intuitive logical equivalences w.r.t. classical negation can
be satisfied, which is not the case for QC ALC; (2) we properly introduce the weak
and strong satisfactions in QC SHIQ, which avoids redundant definition of the seman-
tics of disjunction and conjunction of concepts in QC ALC; (3) we show that instance
checking and subsumption checking can be reduced to the QC consistency problem,
which has not been achieved in QC ALC; and (4) we study the QC semantics for more
expressive language constructors than those in ALC.
The paper is organized as follows. Section 2 briefly reviews SHIQ. Section 3 in-
troduces QC semantics for SHIQ. Section 4 discusses the reasoning problems in QC
SHIQ. Section 5 concludes this paper and discusses the future work. Due to the space
limitation, proofs are omitted but are available in a technical report1 .
1
http://www.is.pku.edu.cn/˜zxw/publication/TRQCSHIQ.pdf
2 Preliminaries
In this section, we briefly review some basic notations in description logic (DL) SHIQ.
For comprehensive background reading, please refer to [11].
Let L be the language of SHIQ, which contains a set of atomic concepts (or con-
cept names), denoted by NC ; a set of individuals, denoted by NI ; and a set of role
names, denoted by NR . NR+ is a set of transitive role names in NR and R is a transi-
tive closure set of NR . We denote R = R ∪ {R− | R ∈ R} where R− is the inverse
role of R. The inverse role of R can be also taken as the inverse transformation on R.
In this way, the inverse role of R can be denoted by Inv(R), i.e., Inv(R) = R− and
Inv(R− ) = R. A role inclusion axiom is of the form R v S where roles R, S can be
inverse. A role hierarchy, denoted R, is a set of role inclusion axioms. A role R is a
sub-role of S, denoted by RvS, ∗ where “v” ∗ is the transitive-reflexive closure of v over
R ∪ {Inv(R) v Inv(S) | R v S ∈ R}. A simple role S is a role which is neither
transitive nor has any transitive sub-roles.
Concept descriptions in SHIQ are formed according to the following syntax rule:
C, D → A | > | ⊥ | ¬A | C t D | C u D | ∃R.C | ∀R.C |≥ nS.C |≤ nS.C
where > is the top concept, ⊥ is the bottom concept, A is a concept name, C, D are
concepts, R is a role, S is a simple role and n is nonnegative integer.
Let C, D be concepts, a, b individuals and R a role. In SHIQ, assertions are of
.
the form C(a) or R(a, b) or a = 6 b. A general concept inclusion axiom (GCI) is of the
form C v D. Informally, an axiom C(a) means that the individual a is an instance of
concept C, and an axiom R(a, b) means that individual a is related with individual b
via the property R. The inclusion axiom C v D means that each individual of C is an
individual of D.
A knowledge base (or ontology) comprises two components, a TBox and an ABox.
In SHIQ, a TBox includes two parts: a set of concept inclusion axioms T and a role
hierarchy R; an ABox consists of concept assertions, role assertions, and individual
inequalities.
The formal definition of the classical (model-theoretic) semantics of SHIQ is given
by means of an interpretation I = (∆I , ·I ) which consists of a non-empty domain ∆I
and a mapping ·I satisfying the conditions in Table 1, where the mapping ·I interprets
concepts as subsets of the domain and roles as binary relations on the domain ∆I .
An interpretation I satisfies a terminology T (role hierarchy R) iff for any concept
inclusion C v D (role inclusion R v S) in T (R), I is an interpretation of C v D
(R v S). In this case, I is named a model of T (R), denoted I |= T (I |= R). A
concept C is called satisfiable w.r.t. a terminology T and a hierarchy R iff there is a
model I of T and R with C I 6= ∅. A concept D subsumes a concept C w.r.t T and R
iff C I ⊆ DI holds for each model I of T and R. For an interpretation I, an element
aI ∈ ∆I is called an instance of a concept C iff aI ∈ C I . An interpretation I satisfies
an ABox A (written I |= A) if it satisfies every assertion in A. An ABox A is consistent
w.r.t. T and R iff there is a model I of T and R that satisfies each assertion in A.
Table 1. Syntax and semantics of DL SHIQ
Constructor Name Syntax Semantics
atomic concept A A AI ⊆ ∆I
abstract role R R R ⊆ ∆I × ∆I
I
individuals I o oI ∈ ∆I
trans.role R ∈ NR+ R = (RI )+
I
inverse role R− {(x, y) | (y, x) ∈ RI }
top concept > ∆I
bottom concept ⊥ ∅
conjunction C1 u C2 C1I ∩ C2I
disjunction C1 t C2 C1I ∪ C2I
negation ¬C ∆I \ C I
exists restriction ∃R.C {x | ∃y, (x, y) ∈ RI and y ∈ C I }
value restriction ∀R.C {x | ∀y, (x, y) ∈ RI implies y ∈ C I }
qualifying atleast restriction ≥ nR.C {x | ]({y.(x, y) ∈ RI } and y ∈ C I ) ≥ n}
qualifying atmost restriction ≤ nR.C {x | ]({y.(x, y) ∈ RI } and y ∈ C I ) ≤ n}
Axiom Name Syntax Semantics
concept assertion C(a) aI ∈ C I
role assertion R(a, b) (a , bI ) ∈ RI
I
concept inclusion C1 v C2 C1I ⊆ C2I
role inclusion RvS RI ⊆ S I
. .
individual inequality a=6 b aI =
6 bI
3 Quasi-Classical Description Logic SHIQ
Quasi-classical DL SHIQ is based on quasi-classical logic defined in [9] and SHIQ.
In this section, we present the syntax and the semantics of QC SHIQ.
3.1 Syntax of QC SHIQ
The syntax of QC SHIQ is almost the same as that of SHIQ. One difference is that
a new concept constructor called complement of a concept is introduced, which is the
syntax form of “total negation” in [14]. The complement of concept C is denoted by C.
The intuition behind a complement of a concept is that we want to use it to characterize
QC inconsistency, i.e., to reverse both the information of being true and of being false.
Its formal interpretation will be given in Section 3.2.
The definition of a QC ABox (resp. QC terminology, QC role hierarchy) is similar
to that of an ABox (resp. terminology, role hierarchy). The only difference is that we
allow a complement of a concept in a complex concept. A QC ontology comprises a
QC terminology, a QC role hierarchy and a QC ABox.
Given the language L of SHIQ, the language of QC SHIQ is denoted L∗ and
is defined by L∗ = L ∪ {C | C is a concept in L}. In the following, we discuss QC
SHIQ based on the language L∗ .
For an atomic concept A, we call A, ¬A, A and ¬A as concept literals. A concept
C is in Negation Normal Form (NNF) if negation (¬) occurs only in front of concept
names. A concept C is in QC NNF, if concept C is in NNF and complement only
occurs over a concept name or negation of a concept name. A role-involved literal has
the form ∀R.C or ∃R.C with C a concept in NNF. A role-involved literal has the form
∀R.C, ∃R.C, ≥ nR.C or ≤ nR.C with C a concept in QC NNF. A literal is either
a concept literal or a role-involved literal, written by L. A clause is the disjunction of
finite literals. Let L1 t · · · t Ln be a clause, then Lit(L1 t · · · t Ln ) is the set of literals
{L1 , . . . , Ln } that are in the clause. A clause is the empty clause, denoted by ♦, if it
has no literals. We define ∼ be a complementation operation such that ∼ A is ¬A and
∼ (¬A) is A.
Let L1 t· · ·tLn be a clause that includes a literal disjunct Li . The focus of L1 t· · ·t
Ln by Li , denoted ⊗(L1 t · · · t Ln , Li ), is defined as the clause obtained by removing
Li from Lit(L1 t · · · t Ln ). In the case of a clause with just one disjunct, we assume
⊗(L, L) = ⊥. For instance, given a clause L1 tL2 tL3 , ⊗(L1 tL2 tL3 , L2 ) = L1 tL3 .
3.2 Semantics of QC SHIQ
In this subsection, we define the QC semantics for QC SHIQ by introducing two
semantics, namely, QC weak semantics and QC strong semantics.
Firstly, we introduce the notion of a weak interpretation and the notion of a strong
interpretation over domain ∆I by assigning to each concept C a pair h+C, −Ci of
subsets of ∆I . Intuitively, +C is the set of elements known to belong to the extension
of C, while −C is the set of elements known to be not contained in the extension of
C. +C and −C are not necessarily disjoint or mutually complemental with respect to
the domain. The complemental set of a set S w.r.t. an interpretation I, denoted by S, is
S = ∆I \ S.
In QC SHIQ, a weak interpretation is a reformulation of a four-valued interpreta-
tion in four-valued DLs (see [6]).
Definition 1 Let I be a pair (∆I , ·I ) with ∆I as domain, where ·I is a function as-
signing elements of ∆I to individuals, subsets of ∆I × ∆I to concepts and subsets
of (∆I × ∆I )2 to roles. I is a weak interpretation in QC SHIQ if the conditions in
Table 2 are satisfied, where CiI = h+Ci , −Ci i for i = 1, 2, C I = h+C, −Ci and
RI = h+R, −Ri.
Definition 2 Let |=w be a satisfiability relation between a set of weak interpretation
and a set of axioms, called weak satisfaction. For a weak interpretation I, we define
|=w as follows, where C, C1 , C2 are concepts, R, R1 , R2 are roles and a is an individ-
ual:
(1) I |=w R1 v R2 iff +R1 ⊆ +R2 , if RiI = h+Ri , −Ri i, i = 1, 2;
(2) I |=w Trans(R) iff +R = (+R)+ , if RI = h+R, −Ri and (R+ )I = h+R+ , −R+ i;
(3) I |=w C(a) iff aI ∈ +C, C I = h+C, −Ci;
(4) I |=w R(a, b) iff (aI , bI ) ∈ +R, RI = h+R, −Ri;
(5) I |=w C1 v C2 iff +C1 ⊆ +C2 , for i = 1, 2, CiI = h+Ci , −Ci i;
.
(6) I |=w a 6= b iff aI 6= bI .
Table 2. Weak Semantics of QC SHIQ
Syntax Weak Semantics
A AI = h+A, −Ai, where +A, −A ⊆ ∆I
R R = h+R, −Ri, where +R, −R ⊆ ∆I × ∆I
I
o oI ∈ ∆I
> h∆I , ∅i
⊥ h∅, ∆I i
C1 u C2 h+C1 ∩ +C2 , −C1 ∪ −C2 i
C1 t C2 h+C1 ∪ +C2 , −C1 ∩ −C2 i
¬C (¬C)I = h−C, +Ci
I
C C = h∆I \ +C, ∆I \ −Ci
∃R.C h{x | ∃y, (x, y) ∈ +R and y ∈ +C}, {x | ∀y, (x, y) ∈ +R implies y ∈ −C}i,
∀R.C h{x | ∀y, (x, y) ∈ +R implies y ∈ +C}, {x | ∃y, (x, y) ∈ +R and y ∈ −C}i
≥ nR.C h{x | ]({y.(x, y) ∈ +R} and y ∈ +C) ≥ n}, {x | ]({y.(x, y) ∈ +R} and y 6∈ −C) < n}i
≤ nR.C h{x | ]({y.(x, y) ∈ +R} and y 6∈ −C) ≤ n}, {x | ]({y.(x, y) ∈ +R} and y ∈ +C) > n}i
In QC SHIQ, the concept inclusion under weak satisfaction is defined by the in-
ternal inclusion in four-valued DLs because other inclusion, namely, material inclusion
and strong inclusion can be transformed into internal inclusion (see [6]).
The following property shows that there exists a close relationship between weak
models and 4-models in four-valued DLs defined in [6].
Proposition 1 Let C, D be concepts, a an individual, R a role and I an interpretation
in QC SHIQ. We have
(1) I |=w C(a) iff I |=4 C(a);
(2) I |=w C v D iff I |=4 C @ D.
The following proposition shows that intuitive equivalence w.r.t. the complement of
a concept is satisfied under QC weak semantics.
Proposition 2 Let I be an interpretation and let C, D be concepts, we have
I |=w C v D iff I |=w C t D(a) for any individual a ∈ NI .
The QC weak satisfaction has the drawback that it does not satisfy some basic in-
ference rules, such as MP, MT and DS. Therefore, we define a QC strong interpretation
that redefines interpretation of disjunction of concepts and conjunction of concepts.
Definition 3 Let I be a pair (∆I , ·I ) with ∆I as the domain, where ·I is a function
assigning elements of ∆I to individuals, subsets of ∆I × ∆I to concepts and subsets
of (∆I × ∆I )2 to roles. I is a strong interpretation in QC SHIQ if the conditions in
Table 2, except conditions for conjunction of concepts and disjunction of concepts, are
satisfied and the following conditions hold, let CiI = h+Ci , −Ci i for i = 1, 2:
conjunction of concepts:
(C1 u C2 )I = h+C1 ∩ +C2 , (−C1 ∪ −C2 ) ∩ (−C1 ∪ +C2 ) ∩ (+C1 ∪ −C2 )i
disjunction of concepts:
(C1 t C2 )I = h(+C1 ∪ +C2 ) ∩ (−C1 ∪ +C2 ) ∩ (+C1 ∪ −C2 ), −C1 ∩ −C2 i
Compared with the weak interpretation, the strong interpretation of disjunction of
concepts tightens the condition that an individual is known to belong to a concept; and
the strong interpretation of conjunction of concepts is defined by relaxing the condition
that an individual known to be not contained in the extension of a concept. The strong
interpretation for the disjunction and conjunction characterizes the relationship between
concepts and individuals with holding resolution rule.
Definition 4 Let |=s be a satisfiability relation between a set of weak interpretation
and a set of axioms, called strong satisf action. For a strong interpretation I, we
define |=s as follows, where C, C1 , C2 are concepts, R, R1 , R2 are roles and a is an
individual:
(1) I |=s R1 v R2 iff +R1 ⊆ +R2 , if RiI = h+Ri , −Ri i, i = 1, 2;
(2) I |=s Trans(R) iff +R = (+R)+ , if RI = h+R, −Ri and (R+ )I = h+R+ , −R+ i;
(3) I |=s C(a) iff aI ∈ +C where C I = h+C, −Ci;
(4) I |=s R(a, b) iff (aI , bI ) ∈ +R where RI = h+R, −Ri;
(5) I |=s C1 v C2 iff −C1 ⊆ +C2 , +C1 ⊆ +C2 and −C2 ⊆ −C1 ,
for i = 1, 2, CiI = h+Ci , −Ci i;
.
(6) I |=s a 6= b iff aI 6= bI .
In Definition 4, when defining the strong satisfaction of a concept inclusion under
a QC strong interpretation, we use conditions for interpreting a concept inclusion by
internal inclusion, material inclusion and strong inclusion in four-valued DLs. By doing
so, our strong satisfaction satisfies intuitive equivalence that is falsified by four-valued
satisfaction relations.
Proposition 3 Let I be an interpretation and let C, D be concepts. We have
I |=s C v D iff I |=s ¬C t D(a) for any individual a ∈ NI .
Proposition 2 and Proposition 3 provide the theoretical base of transforming the
problem of reasoning with ABoxes and terminologies into the problem of reasoning
with ABoxes.
The following proposition provides a slightly different view on the QC semantics
of disjunction of concepts.
Proposition 4 Let C1 and C2 be two concepts and a be an individual. We have
I |=s C1 t C2 (a) iff for some Ci , aI ∈ +Ci and aI 6∈ −Ci ; or
for all Ci , aI ∈ +Ci and aI ∈ −Ci ;
where CiI = h+Ci , −Ci i and i = 1, 2.
Proposition 5 Let I be an interpretation and φ be an axiom in QC SHIQ respectively.
If I |=s φ then I |=w φ.
Proposition 5 shows that a strong model is a weak model. However, the converse
does not hold. For instance, given an ABox A = {C(a), ¬C(a)}. We can construct an
interpretation I such that aI ∈ +C, aI ∈ −C and aI 6∈ +D where C I = h+C, −Ci
and DI = h+D, −Di. Then I 6|=s C t D(a) because I 6|=s D(a). Clearly, I |=w
C t D(a).
Proposition 6 Let C be a concept, R a role and n a natural number. For any QC weak
( or QC strong) interpretation I, we have
(1) (¬(≤ nR.C))I = (> nR.C)I ;
(2) (¬(≥ nR.C))I = (< nR.C)I ;
(3) (∃R.C)I = (≥ 1R.C)I ;
(4) (∀R.C)I = (< 1R.¬C)I .
Proposition 7 Let A be a concept name, C, D concepts, a, b individuals, R a role and
n a natural number in QC SHIQ. If I is a QC weak or QC strong interpretation, then
the follows properties hold.
(1) I |=x A(a) iff I 6|=x A(a) (6) I |=x >(a) iff I |=x ⊥(a)
(2) I |=x A(a) iff I |=x A(a) (7) I |=w C t D(a) iff I |=w C u D(a)
(3) I |=x ¬A(a) iff I |=x ¬A(a) (8) I |=w C u D(a) iffI |=w C t D(a)
(4) I |=x (∀R.C)(a) iff I |=x ∃R.C(a) (9) I |=x (≥ nR.C)(a) iff I |=x ≤ n-1R.C(a)
(5) I |=x (∃R.C)(a) iff I |=x ∀R.C(a) (10) I |=x (≤ nR.C)(a) iff I |=x ≥ n+1R.C(a)
where |=x is a place-holder for both |=w and |=s .
Definition 5 Given a QC ontology O and an axiom φ in SHIQ, we say O quasi-
classically entails (for short QC entails) φ, denoted by O |=Q φ, iff for every interpre-
tation I, for any axiom ψ of O if I |=s ψ then I |=w φ. In this case, |=Q is called a
quasi-classical entailment (relation) (for short QC entailment) between O and φ.
The following example shows that |=Q is non-trivializable in the sense that when
an ontology O is classically inconsistent.
Example 1 Given an ABox A = {B(a), ¬B(a)} and a concept name A in QC SHIQ.
It is clear that A is classically inconsistent. However A |=Q A(a) does not hold. This
is because there exists an interpretation I such that aI ∈ +B and aI ∈ −B where
B I = h+B, −Bi. So I |=s B u ¬B(a), but I 6|=w A(a) since A(a) does not occur in
A.
The following proposition shows that |=Q satisfies the resolution rule.
Proposition 8 Let C, D, E be concepts and a be an individual.
{C t D(a), ¬C t E(a)} |=Q D t E(a).
By Proposition 8, |=Q satisfies three important inferences: MP, MT and DS.
Example 2 Suppose O is an empty QC ontology.
(1) Consider the concept At¬A. We have O 6|=Q At¬A(a), since O strongly satisfies
every formula in O, but O does not weakly satisfy A t ¬A(a).
(2) Consider the concept A t A. We have O |=Q A t A(a), since O strongly satisfies
every axiom in O and O |=w A(a) or O |=w A(a), i.e., O |=w A t A(a).
Example 2 shows that, for some concept name A in QC SHIQ, the concept A t A
can be considered as the top concept > under QC entailment. However, this is not the
case for concept A t ¬A.
In the following, we show that some properties of QC entailment satisfied in QC
propositional logic (see [9]) still hold in QC SHIQ.
Proposition 9 Given a QC ontology O, axioms φ, ψ, two concepts C, D and an indi-
vidual a, the following properties hold.
(1) (Reflexivity) O ∪ {φ} |=Q φ.
(2) (Monotonicity) if O |=Q φ then O ∪ {ψ} |=Q φ.
(3) (And-introduction) if O |=Q C(a) and O |=Q D(a) then O |=Q C u D(a).
(4) (Or-elimination) if O ∪ {C(a)} |=Q φ and O ∪ {D(a)} |=Q φ then O ∪ {C t
D(a)} |=Q φ.
The following proposition shows that QC entailment is weaker than classical entail-
ment in SHIQ.
Proposition 10 Let O be an ontology and φ be an axiom in SHIQ.
If O |=Q φ then O |= φ.
The converse of Proposition 10 does not hold. In Example 1, A |= φ for any axiom
because A is classically inconsistent while A 6|=Q A(a).
Proposition 11 Let O be an ontology and φ be an axiom in SHIQ.
If O |=4 φ then O |=Q φ.
In QC SHIQ, a strong interpretation I satisfies a terminology T (role hierarchy
R) iff I |=s C v D (R v S) for each C v D in T (R v S in R). In this case, I is
called a QC model of T , written I |=s T (a QC model of R, written I |=s R). A strong
interpretation I satisfies an ABox A iff I |=s φ for each assertion φ in A, where φ is
.
one of the following forms: C(a), R(a, b), a =6 b. In this case, I is called a QC model
of A, written I |=s A.
The following proposition shows the close relationship between the QC entailment
and the QC model.
Proposition 12 Let O be a QC ontology, C, D two concepts and a an individual.
(1) O |=Q C(a) iff there is no any QC model of O ∪ {C(a)}.
(2) O |=Q C v D iff there is no any QC model of O ∪ {C u D(t)} for some new
individual t not occurring in O.
4 Reasoning in Quasi-Classical Description Logic SHIQ
4.1 The QC Consistency Problem
In QC SHIQ, a concept C is QC satisfiable w.r.t. a QC ABox A if there exists a QC
model I of A such that I |=s C(a) for some individual a, and QC unsatisfiable w.r.t.
A otherwise. A concept C is QC satisfiable w.r.t. a QC role hierarchy R and a QC
terminology T if there exists a QC model I of R and T such that I |=s C(a) for
some individual a, and QC unsatisfiable w.r.t. R and T otherwise. A QC ABox A is
QC consistent if there exists a QC model I of A, and QC inconsistent otherwise. A QC
ABox A is QC consistent w.r.t. a QC role hierarchy R and a QC terminology T if there
exists a QC model I of R and T such that I is a QC model of A, and QC inconsistent
w.r.t. R and T otherwise.
We are able to show that the complexity of QC consistency checking in QC SHIQ
is in the same level as that of satisfiability check in SHIQ.
Proposition 13 Checking QC consistency of a QC SHIQ ABox w.r.t. a QC role hier-
archy R and a QC terminology T is EXPTIME-Complete.
4.2 The Inference Problems
In QC SHIQ, there are two basic inference problems given as follows.
– instance checking: an individual a is called a QC instance of a concept C w.r.t. a
QC ABox A iff for any QC model I of A, I is a QC model of C(a).
– subsumption: a concept C QC subsumes a concept D w.r.t. a QC role hierarchy R
and a QC terminology T iff for any QC model I of R and T , I is a QC model of
C v D.
Proposition 14 Given a QC SHIQ ontology O, two concepts C, D and an individual
a, we have
(1) O |=Q C(a) iff O ∪ {C(a)} is QC inconsistent.
(2) O |=Q C v D iff O ∪ {C u D(t)} is QC inconsistent for some new individual t not
occurring in O.
Proposition 14 shows that two basic inference problems can be reduced to the prob-
lem of QC consistency checking.
5 Conclusions
In this paper, we presented QC SHIQ to handle inconsistency in SHIQ. The syntax
of SHIQ was extended by introducing the notion of the complement of a concept.
QC semantics was defined by two kinds of semantics: weak semantics and strong se-
mantics. We showed that both of them satisfy some important inference rules. A QC
entailment relation based on strong interpretations and weak interpretations was intro-
duced and we showed that this entailment relation satisfies some desirable properties.
We introduced the notion of QC consistency of a QC ontology and two basic QC en-
tailment problems and showed that these two entailment problems can be reduced to
the problem of QC consistency checking. Furthermore, we showed that QC consistency
problem of ABoxes is EXPTIME-Complete. As a future work, following [8], we will
develop an algorithm based on the classical tableau for querying. In the other direc-
tion, we will consider employing a classical DL reasoner, such as KAON2 or Pellet,
to implement paraconsistent reasoning based on QC semantics. Further, we will also
consider introducing QC semantics into more expressive DLs such as SHOIN (D).
References
1. Bell, D.A., Qi, G., Liu, W.: Approaches to inconsistency handling in description-logic based
ontologies. In: Proc. of OTM Workshops’07, Portugal, 2007
2. Schlobach, S., Cornet, R.: Non-standard reasoning services for the debugging of description
logic terminologies. In: Proc.of IJCAI’03, Mexico, 2003, Morgan Kaufmann (2003) 355–
362
3. Huang, Z., van Harmelen, F., ten Teije, A.: Reasoning with inconsistent ontologies. In: Proc.
of IJCAI’05, Scotland, UK, 2005, Professional Book Center (2005) 454–459
4. Qi, G., Yang, F.: A survey of revision approaches in description logics. In: Proc. of DL’08,
Germany, 2008. CEUR Workshop Proceedings 353, CEUR-WS.org (2008)
5. Straccia, U.: A sequent calculus for reasoning in four-valued description logics. In: Proc. of
TABLEAUX ’97, France, 1997. LNCS 1227, Springer (1997) 343–357
6. Ma, Y., Hitzler, P., Lin, Z.: Paraconsistent reasoning for expressive and tractable description
logics. In: Proc. of DL’08, Germany, 2008. CEUR Workshop Proceedings 353, CEUR-
WS.org (2008)
7. Belnap, N.D.: A useful four-valued logic. Modern uses of multiple-valued logics (1977)
7–73
8. Zhang, X., Xiao, G., Lin, Z.: A tableau algorithm for handling inconsistency in OWL. In:
Proc. of ESWC’09, Greece, 2009. LNCS 5554, Springer (2009) 399–413
9. Besnard, P., Hunter, A.: Quasi-classical logic: Non-trivializable classical reasoning from
incosistent information. In: Proc. of ECSQARU’95, Switzerland, 1995. LNCS 946, Springer
(1995) 44–51
10. Hunter, A.: Reasoning with contradictory information using quasi-classical logic. J. Log.
Comput. 10(5) (2000) 677–703
11. Horrocks, I., Sattler, U., Tobies, S.: Practical reasoning for expressive description logics. In:
Proc. of LPAR’99, Georgia, 1999. LNCS 1705, Springer (1999) 161–180
12. Baader, F., Nutt, W.: Basic description logics. In: The Description Logic Handbook: Theory,
Implementation, and Applications. (2003) 43–95
13. Zhang, X., Lin, Z.: Paraconsistent reasoning with quasi-classical semantics in alc. In: Proc.
of RR’08, Germany, 2008. LNCS 5341, Springer (2008) 222–229
14. Ma, Y., Hitzler, P., Lin, Z.: Algorithms for paraconsistent reasoning with owl. In: Proc. of
ESWC’07, Austria, 2007. LNCS 4519, Springer (2007) 399–413
15. Patel-Schneider, P.F.: A four-valued semantics for terminological logics. Artif. Intell. 38(3)
(1989) 319–351
16. Baader, F., Hollunder, B.: A terminological knowledge representation system with complete
inference algorithms. In: Proc. of PDK’91, Germany, 1991. LNCS 567, Springer (1991)
67–86