One of the most important current issues in Description Logic (DL) ontology
management is dealing with inconsistency, that is, the presence of contradictory
information in the ontology [
In this paper we focus on ABox inconsistency, i.e., the case of inconsistent KBs where the TBox is consistent while the ABox is inconsistent with the TBox, i.e., a subset of the assertions in the ABox contradicts a TBox assertion (or a subset of the TBox). In particular, we are interested in defining a form of automatic ABox cleaning, i.e., given K = hT , Ai, we want to identify an ABox A0 such that hT , A0i is consistent and A0 is “as close as possible” to A.
The kind of ABox cleaning we adopt is formally based on inconsistency-tolerant
semantics, which overcome the limitations of the classical DL semantics in inconsistency
management. In particular, we consider inconsistency-tolerant semantics for general
DLs recently proposed in [
We argue that the results of [
The paper that is closer to our work is [
The rest of the paper is organized as follows. In Section 2, we give some preliminaries, and in particular we introduce DL-LiteA and the definition of the IAR and the ICAR semantics. In Section 3, we present detailed algorithms for ABox cleaning in DL-LiteA. In Section 4 we present the QuAC system and report on the experiments we are currently conducting with QuAC. Finally, in Section 5 we conclude the paper. 2 2.1
The DL DL-LiteA
In this paper we consider DL ontologies (knowledge bases) specified in DL-LiteA, a
member of the DL-Lite family of tractable Description Logics [
E −→ ρ(U ) F −→ >D | T1 | · · · | Tn
V −→ U | ¬U In such rules, A, P , and U respectively denote an atomic concept (i.e., a concept name), an atomic role (i.e., a role name), and an attribute name, P − denotes the inverse of an atomic role, whereas B and Q are called basic concept and basic role, respectively. 1 http://www.dis.uniroma.it/˜quonto Furthermore, δ(U ) denotes the domain of U , i.e., the set of objects that U relates to values; ρ(U ) denotes the range of U , i.e., the set of values that U relates to objects; >D is the universal value-domain; T1, . . . , Tn are n pairwise disjoint unbounded valuedomains.
A DL-LiteA knowledge base (KB) is a pair K = hT , Ai, where T is the TBox and A the ABox. The TBox T is a finite set of assertions of the form
B v C
Q v R
E v F
U v V (funct Q) (funct U ) From left to right, the first four assertions respectively denote inclusions between concepts, roles, value-domains, and attributes. In turn, the last two assertions denote functionality on roles and on attributes. In fact, in DL-LiteA TBoxes we further impose that roles and attributes occurring in functionality assertions cannot be specialized (i.e., they cannot occur in the right-hand side of inclusions). Let B1 and B2 be basic concepts, and let Q1 and Q2 be basic roles. We call positive inclusions (PIs) assertions of the form B1 v B2, and of the form Q1 v Q2, whereas we call negative inclusions (NIs) assertions of the form B1 v ¬B2 and Q1 v ¬Q2.
A DL-LiteA ABox A is a finite set of membership assertions (ABox assertions) of the forms A(a), P (a, b), and U (a, v), where A, P , and U are as above, a and b belong to ΓO, the subset of ΓC containing object constants, and v belongs to ΓV , the subset of ΓC containing value constants, where {ΓO, ΓV } is a partition of ΓC .
The semantics of a DL-LiteA knowledge base is given in terms of first-order logic (FOL) interpretations in the usual way. An interpretation I satisfying a knowledge base K a called a model for K. In the following Mod(hT , Ai) will indicate the set of models of the KB K = hT , Ai. A knowledge base K is satisfiable if it has at least a model, otherwise it is called unsatisfiable. Given an assertion α (which is either a TBox or ABox assertion), we write K |= α if α is satisfied in every model for K.
Given a TBox T and an ABox A0, A0 is called a minimal conflict set for T if the KB hT , A0i is unsatisfiable and, for every ABox A00 such that A00 ⊂ A0, the KB hT , A00i is satisfiable. A minimal conflict set for T is called unary if its cardinality (that is, the number of assertions it contains) is 1 and is called binary if its cardinality is 2. 2.2
Inconsistency-tolerant semantics for DLs
In this section we recall the inconsistency-tolerant semantics for general DL knowledge
bases defined in [
AR-semantics The first notion of repair that we consider, called AR-repair, is a very natural one: a repair is a maximal subset of the ABox that is consistent with the TBox. Thus, an AR-repair is obtained by throwing away from A a minimal set of assertions to make it consistent with T .
Definition 1. Let K = hT , Ai be a DL KB. An AR-repair of K is a set A0 of
membership assertions such that: (i)A0 ⊆ A; (ii) Mod(hT , A0i) 6= ∅; (iii) there does not exist
2 Due to space limitations, we refer the reader to [
A00 such that A0 ⊂ A00 ⊆ A and Mod(hT , A00i) 6= ∅. The set of AR-repairs for K is denoted by AR-Rep(K). Moreover, we say that a first-order sentence φ is AR-entailed by K, written K |=AR φ, if hT , A0i |= φ for every A0 ∈ AR-Rep(K).
CAR-semantics We start by formally introducing a notion of “equivalence under consistency” for inconsistent KBs.
Given a KB K, let SK denote the signature of K, i.e., the set of concept, role, and individual names occurring in K. Given a signature S, we denote with HB(S) the Herbrand Base of S, i.e. the set of ABox assertions (ground atoms) that can be built over the signature S. Then, given a KB K = hT , Ai, we define the consistent logical consequences of K as the set clc(K) = {α | α ∈ HB(SK ) and there exists A0 ⊆ A such that Mod(hT , A0i) 6= ∅ and hT , A0i |= α}. Finally, we say that two KBs hT , Ai and hT , A i are consistently equivalent (C-equivalent) if clc(hT , Ai) = 0 clc(hT , A0i).
We argue that the notion of C-equivalence is very reasonable in settings in which the ABox (or at least a part of it) has been “closed” (in a complete or partial way) with respect to the TBox, e.g., when (some or all) the ABox assertions that are entailed by the ABox and the TBox have been added to the original ABox. This may happen, for example, when the ABox is obtained by integrating different (and locally consistent) sources, since some of these sources might have been locally closed with respect to some TBox axioms: this is very likely, for instance, if a source is an RDF graph with RDFS predicates, since many RDF systems materialize in the RDF graph the implicit triples due to the RDFS predicates.
In settings where C-equivalence makes sense, the AR-semantics is not suited to handle inconsistency. In fact, we would expect two C-equivalent KBs to produce the same logical consequences under inconsistencytolerant semantics. Unfortunately, the AR-semantics does not have this property. A simple example is the following: let T = {student v young , student v ¬worker } and let A = {student(mary), worker (mary)}, A0 = {student(mary), worker (mary), young (mary)}. It is immediate to verify that if K0 = hT , A0i, then clc(K) = clc(K0) = A0, thus K and K0 are C-equivalent, however K0 |=AR young (mary) while K 6|=AR young (mary).
To overcome the above problem, the CAR-semantics has been defined in [
Going back to the previous example, it is immediate to see that, since K and K0
are C-equivalent, the set of CAR-repairs (and hence the set of CAR-models) of K and
K0 coincide. As the above example shows, there are sentences entailed by a KB under
CAR-semantics that are not entailed under AR-semantics. Conversely, it is shown in
3 The definition provided here of the CAR-semantics is a slight simplification of the one
appearing in [
semantics, which are sound approximations of the AR-semantics and the
CARsemantics, respectively [
Definition 3. Let K = hT , Ai be a DL KB. Then: (i) The IAR-repair for K, denoted by IAR-Rep(K) is defined as IAR-Rep(K) = TA0∈AR-Rep(K) A0. (ii) The ICAR-repair for K, denoted by ICAR-Rep(K) is defined as ICAR-Rep(K) = TA0∈CAR-Rep(K) A0. (iii) We say that a first-order sentence φ is IAR-entailed (respectively, ICAR-entailed) by K, and we write K |=IAR φ (respectively, K |=ICAR φ), if hT , IAR-Rep(K)i |= φ (respectively, hT , ICAR-Rep(K)i |= φ).
Example 1. Let us consider the KB K = hT , Ai where the TBox T is the following:
T = {A v C, B v C, ∃R v B, ∃R− v D, A v ¬B, (funct R)} and the ABox A is A = {A(a), B(a), C(a), R(a, b)}. Such a KB is unsatisfiable, due to the presence of the assertions A(a) and B(a) which violate the disjointness assertion in T . The following are the standard AR-repairs of A:
AAR1 = {B(a), C(a), R(a, b)},
AAR2 = {A(a), C(a)} Then, we have clc(A) = {A(a), B(a), C(a), R(a, b), D(a)}. Therefore, the CARrepair of A are as follows:
ACAR1 = {B(a), C(a), R(a, b), D(b)},
ACAR2 = {A(a), C(a), D(b)}
Consequently, the IAR-repair and ICAR-repair are the following:
AIAR = AAR1 ∩ AAR2 = {C(a)}, AICAR = ACAR1 ∩ ACAR2 = {C(a), D(a)}
Example 2. One might conjecture that the IAR semantics collapses into a simple ABox
cleaning technique which deletes from the ABox all the assertions that participate in
conflicts with the TBox. This is actually not the case, because, as explained in [
The technique for computing the ICAR-repair of a DL-LiteA ontology hT , Ai is based
on the idea of deleting from A all the membership assertions participating in minimal
conflict sets for T . As shown in [
This property is actually crucial for tractability of reasoning under IAR and ICAR
semantics. As shown in [
We now present detailed algorithms for computing the IAR-repair and the
ICARrepair of a DL-LiteA ontology. These algorithms exploits the techniques presented in
[
In the following, we call annotated ABox assertion an expression ξ of the form hα, γi where α is an ABox assertion and γ is a value in the set {cons, ucs, bcs}. Furthermore, we call annotated ABox a set of annotated ABox assertions. The intuition behind an annotated ABox assertion ξ is that its annotation γ expresses whether the associated ABox expression α does not participate in any minimal conflict set (cons) or participates in a unary conflict set (ucs) or to a binary conflict set (bcs).
The following algorithm QuAC-ICAR computes the ICAR-repair of a DL-LiteA KB. For ease of exposition, the algorithm does not report details on the treatment of attributes, which are actually handled in a way analogous to roles. such that γ1, γ2 6= ucs do
Aann = Aann − {ξ1, ξ2} ∪ {hA(a), bcsi, hB(a), bcsi}; for each disjointness A v ¬∃R with A atomic concept such that T |= A v ¬∃R do for each pair ξ1 = hA(a), γ1i, ξ2 = hR(a, b), γ2i ∈ A0ann such that γ1, γ2 6= ucs do
Aann = Aann − {ξ1, ξ2} ∪ {hA(a), bcsi, hR(a, b), bcsi}; for each disjointness A v ¬∃R− with A atomic concept such that T |= A v ¬∃R do for each pair ξ1 = hA(a), γ1i, ξ2 = hR(b, a), γ2i ∈ A0ann such that γ1, γ2 6= ucs do
Aann = Aann − {ξ1, ξ2} ∪ {hA(a), bcsi, hR(b, a), bcsi}; for each disjointness R v ¬S with R, S atomic roles such that T |= R v ¬S do for each pair ξ1 = hR(a, b), γ1i, ξ2 = hS(a, b), γ2i ∈ A0ann such that γ1, γ2 6= ucs do
Aann = Aann − {ξ1, ξ2} ∪ {hR(a, b), bcsi, hS(a, b), bcsi}; for each disjointness R v ¬S− with R, S atomic roles such that T |= R v ¬S− do for each pair ξ1 = hR(a, b), γ1i, ξ2 = hS(b, a), γ2i ∈ A0ann such that γ1, γ2 6= ucs do Aann = Aann − {ξ1, ξ2} ∪ {hR(a, b), bcsi, hS(b, a), bcsi}; for each functionality assertion (funct R) ∈ T with R atomic role do for each pair ξ1 = hR(a, b), γ1i, ξ2 = hR(a, c), γ2i ∈ A0ann such that b 6= c and γ1, γ2 6= ucs do
Aann = Aann − {ξ1, ξ2} ∪ {hR(a, b), bcsi, hR(a, c), bcsi}; for each functionality assertion (funct R−) ∈ T with R atomic role do for each pair ξ1 = hR(b, a), γ1i, ξ2 = hR(c, a), γ2i ∈ A0ann such that b 6= c and γ1, γ2 6= ucs do
Aann = Aann − {ξ1, ξ2} ∪ {hR(b, a), bcsi, hR(c, a), bcsi}; // STEP 5: extract the ICAR repair from Aann
A0 = ∅; for each hα, consi ∈ Aann do A0 = A0 ∪ {α}; return A0 end
The algorithm QuAC-ICAR consists of five steps which can be informally described as follows. step 1 copy of A into an annotated ABox Aann . In this step, the value of the annotation is initialized to cons for all ABox assertions. step 2 detection of the unary conflict sets in Aann . For every assertion of the form ξ = hα, consi, such that {α} is a unary conflict set for T , Aann = Aann − {ξ} ∪ {hα, ucsi}, i.e., the annotation relative to α is changed to ucs. Unary conflict sets are actually detected through TBox reasoning, by looking at empty concepts and roles in T , as well as asymmetric roles, i.e., roles disjoint with their inverse. step 3 computation of the consistent logical consequences in Aann . Here, the task is to compute all ABox assertions that are entailed by T together with any T -consistent subset of A. In DL-LiteA, this actually corresponds to computing the ABox assertions that are entailed by T together with the ABox obtained from A by deleting all unary conflict sets for T . Hence, what the algorithms does is computing the ABox assertions that are logical consequence of T and of the assertions of Aann which have not been annotated as unary conflict sets in the previous step. step 4 detection of the binary conflict sets in Aann . For every pair of assertions of the form ξ1 = hα1, γ1i, ξ2 = hα2, γ2i such that γ1 6= ucs and γ2 6= ucs and {α, β} is a binary conflict set for T , Aann = Aann − {ξ1, ξ2} ∪ {hα, bcsi, hβ, bcsi}, i.e., the annotation relative to α and β is changed to bcs. As in the case of unary conflict sets, to find binary conflict sets the algorithm looks for disjoint concepts and roles in T , as well as functional roles. step 5 extraction of the ICAR-repair from Aann . The ICAR-repair can be now simply extracted from the annotated ABox Aann , by eliminating both unary conflict sets and binary conflict sets. Therefore, for every assertion of the form hα, consi in Aann , α is copied into the (non-annotated) ABox A0 which is finally returned by the algorithm.
The algorithm QuAC-IAR is very similar to QuAC-ICAR: the only difference is that
it does not execute step 3, i.e., computation of consistent logical consequences.
Correctness of the above algorithms can be proved starting from the results in [
We have implemented the above algorithms QuAC-ICAR and QuAC-IAR within the Quonto system, in a module called QuAC (the Quonto ABox Cleaner). Essentially, QuAC is a Java implementation of the above algorithms where operations on the involved ABoxes are delegated to a relational database system (DBMS). In fact, in the Quonto architecture, the management of the ABox is delegated to a DBMS: therefore, all the operations on ABox assertions of the algorithms for computing repairs are executed in QuAC by the DBMS used by Quonto, through appropriate SQL scripts.
We are currently experimenting QuAC in order to answer several open questions, among which: – the computational cost of the various steps of the algorithm QuAC-IAR and
QuAC-ICAR; – the scalability of such algorithms; – measuring the difference in terms of computational costs of the IAR semantics and the ICAR semantics; – the impact of the “degree of inconsistency” of the ABox on the computational cost of the algorithms.
The tables reported in Figure 1 and Figure 2 present some of the experimental results that we have obtained so far. The TBox used in the experiments has 30 concept names, 20 role names, 10 attribute names, and about 200 TBox assertions. The various ABoxes used have been automatically generated.
The first table presents the experimental results for a version of Quonto that uses a main memory database (H2) to handle the ABox, while the second table presents the same results when Quonto uses a standard (disk-resident) database (PostgreSQL). The results have been conducted on a Pentium i7 (2.67 GHz) CPU with 6GB RAM under Windows 7 (64 bit) operating system. We have also executed the same tests using the MySQL DBMS, with results analogous to those obtained with PostgreSQL.
In the tables, the first column reports the number of assertions in the ABox, while the second column reports the percentage of ABox assertions that participate in minimal conflict sets for the considered TBox. Moreover: – Δ1 denotes the time to create the annotated ABox; – ΔI2AR denotes the time to detect unary and binary conflict sets; –– ΔΔII23CAARRdedneontoetsetshtehteimtiemteo teoxtdreatcetctthuenIaAryRc-roenpflaiicrtfrsoemts,tchoemanpnuotetacteodnsAisBteonxt;logical consequences and detect binary conflict sets; – ΔI3CAR denotes the time to extract the ICAR-repair from the annotated ABox; –– ΔΔIICAARRisisthtehetottoatlatlitmimeetotococommppuuteteththeeIAICRA-rRep-raeipr,aii.re,.i,.eΔ.,1Δ+1 Δ+I2ΔARI2C+ARΔ+I3AΔRI3;CAR; – all times are expressed in milliseconds.
ABox size % incons. Δ1 ΔI2AR ΔI3AR ΔIAR ΔI2CAR ΔI3CAR ΔICAR (i) with both the main memory DB and the disk-resident DB, the computation of the IAR-repair (ΔIAR column) seems really scalable, while the computation of the ICAR-repair suffers from the additional step of computing logical consequences, which is computationally very expensive: its cost actually dominates the cost of all the other steps; (ii) the percentage of inconsistency, i.e., the fraction of ABox assertions that participate in minimal conflict sets, does not have a significant impact on the execution time of both algorithms; 1,840 1,840 1,840 ΔI2AR ΔI3AR ΔIAR ΔI2CAR ΔI3CAR ΔICAR (iii) using the main memory DB, most of the computation time for the IAR-repair is devoted to the detection of minimal conflict sets (i.e., ΔI2AR); conversely, using the disk-resident DB, a very large percentage of the execution time (always more than 80%) is devoted to the generation of the annotated ABox and to the extraction of the IAR-repair. This is of course due to the fact that such steps require to create and write a large number of records on the disk. On the other hand, RAM size is a bottleneck for the main memory DB (we were not able to process ABoxes with 100,000 assertions). 5
As above observed, most of the execution time of the algorithm QuAC-IAR using a diskresident DB is due to the creation of the annotated ABox (step 1) and to the creation of the IAR-repair (step 5). Thus, avoiding these steps would dramatically improve the efficiency of this algorithm.
To this aim, we observe that both the above steps could be completely skipped if the database schema used for representing the ABox would present an additional attribute for storing annotations in every relation (the usual DB representation of an ABox uses a unary relation for every concept and a binary relation for every role). This corresponds to the idea of directly using an annotated ABox instead of a standard ABox in the system. In this case, the computation of the IAR-repair could only consist of the steps 2, 3 and 4 of the algorithm QuAC-IAR. However, the choice of using an annotated ABox instead of an ABox affects query answering, since the queries evaluated on an annotated ABox should be able to filter out the assertions whose annotation is equal to cons.
We are currently experimenting whether this choice is actually feasible. Below we present a table showing the evaluation time of four queries of increasing complexity on the ABoxes considered in the previous section (in particular, the ABoxes with 5% inconsistent assertions). We show the cost of both evaluating the query on the IARrepair (represented as a standard ABox) and directly on the annotated ABox (with the further selection condition on the annotations).
These first experimental results show that, in Quonto, evaluating queries on the annotated ABox often seems computationally not much harder (and sometimes even easier) than evaluating them on the standard ABox. Therefore, a more detailed experimental analysis is needed in order to understand the conditions under which it could be convenient to only work with an annotated representation of the ABox.
Finally, it would be very interesting to compare the performance of QuAC with
a query rewriting approach. Indeed, techniques for the perfect rewriting of unions of
conjunctive queries over DL-LiteA KBs under both IAR and ICAR semantics have
been recently defined [