Inconsistency handling in expressive description logics is an important 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 analyze the computational complexity of consistency checking based on the quasiclassical semantics.
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 Ontology Web Language (OWL), expressive description logics (for short DLs) fail to tolerate 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 nonstandard 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 reasoning 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 description 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 composes of two kinds of semantics, namely, QC weak semantics |=w and QC strong semantics |=s. QC weak semantics inherits the characteristics of four-valued semantics 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
following significant improvements: (
The paper is organized as follows. Section 2 briefly reviews SHIQ. Section 3 introduces 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
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 concept 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 transitive 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 R v∗S, 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 CI 6= ∅. A concept D subsumes a concept C w.r.t T and R iff CI ⊆ 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 ∈ CI . 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. Constructor Name
Syntax atomic concept A abstract role R individuals I trans.role inverse role
A R o R ∈ NR+
R−
Semantics
AI ⊆ ΔI RI ⊆ ΔI × ΔI
oI ∈ ΔI
RI = (RI )+ {(x, y) | (y, x) ∈ RI } ΔI top concept > bottom concept ⊥ ∅ conjunction C1 u C2 C1I ∩ C2I disjunction C1 t C2 C1I ∪ C2I negation ¬C ΔI \ CI exists restriction ∃R.C {x | ∃y, (x, y) ∈ RI and y ∈ CI } value restriction ∀R.C {x | ∀y, (x, y) ∈ RI implies y ∈ CI } qualifying atleast restriction ≥ nR.C {x | ]({y.(x, y) ∈ RI } and y ∈ CI ) ≥ n} qualifying atmost restriction ≤ nR.C {x | ]({y.(x, y) ∈ RI } and y ∈ CI ) ≤ n}
Axiom Name concept assertion
role assertion concept inclusion
role inclusion individual inequality
Syntax C(a) R(a, b) C1 v C2 R v S
. a 6= b
Semantics aI ∈ CI (aI , bI ) ∈ RI
C1I ⊆ C2I RI ⊆ SI aI 6=. bI 3
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
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 L1t· · ·tLn be a clause that includes a literal disjunct Li. The focus of L1t· · ·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 L1tL2tL3, ⊗(L1tL2tL3, L2) = L1tL3. 3.2
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 interpretation in four-valued DLs (see [6]).
Definition 1 Let I be a pair (ΔI , ·I ) with ΔI as 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 weak interpretation in QC SHIQ if the conditions in Table 2 are satisfied, where CI = h+Ci, −Cii for i = 1, 2, CI = h+C, −Ci and i 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
individual:
(
In QC SHIQ, the concept inclusion under weak satisfaction is defined by the internal 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 fourv-alued 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
(
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 inference 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, −Cii 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 ∩ −C2i
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:
(
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, −Cii and i = 1, 2.
Proposition 5 Let I be an interpretation and φ be an axiom in QC S HIQ 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 CI = 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
(
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.
(
Definition 5 Given a QC ontology O and an axiom φ in SHIQ, we say O quasiclassically entails (for short QC entails) φ, denoted by O |=Q φ, iff for every interpretation 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 BI = 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.
(
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
individual a, the following properties hold.
(
The following proposition shows that QC entailment is weaker than classical entailment 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.
(
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 hierarchy 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
(
Proposition 14 shows that two basic inference problems can be reduced to the problem of QC consistency checking. 5
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 semantics. We showed that both of them satisfy some important inference rules. A QC entailment relation based on strong interpretations and weak interpretations was introduced 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 entailment 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 direction, 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).