Efficient Query Answering over Expressive Inconsistent Description Logics

1 Introduction

Conjunctive query answering over data described using ontological knowledge is a key reasoning service for many modern applications [Motik et al., 2012; Chaussecourte et al., 2013]. Although query answering is normally defined over consistent datasets, in real-world applications the data can very often be inconsistent with respect to the axioms specified in the ontology. In this case the straightforward approach would be to try and resolve the inconsistencies by "cleaning" the dataset from the conflicting elements. However, in many occasions this might not be practical due to, e.g., the large volume of the data and the non-deterministic nature of the cleaning procedures. A second approach that has been proposed in the literature, called consistent query answering, is to devise semantics which describe which answers are "meaningful" to be returned even in the presence of the inconsistencies [Arenas et al., 1999; Bertossi, 2006]. For this reason such semantics are referred to as inconsistent-tolerant.

⇤At the time of acceptance Giorgos Stoilos was a member of NTUA supported by a Marie Curie Career Reintegration Grant within European Union's 7th Framework Programme (FP7/20072013) under REA grant agreement 303914.

Consistent query answering has recently been studied in the field of Description Logics (DLs) [Lembo et al., 2010; Rosati, 2011; Bienvenu and Rosati, 2013; Bienvenu et al., 2014]. Two important approaches, mostly due to their nice computational properties over the lightweight DL DL-Lite, consist of the so-called IAR and ICAR semantics [Lembo et al., 2010]. Despite important theoretical results and a few implemented systems [Masotti et al., 2011; Rosati et al., 2012; Bienvenu et al., 2014], designing practically efficient consistent query answering systems that could scale up to billions of data is still largely open. Especially for the ICAR semantics, only a preliminary effort was reported by Masotti et al. [2011] but the evaluation used very small proprietary datasets (of the scale of a few thousands). Furthermore, over many still lightweight DLs, like EL, ICAR-based query answering is intractable [Rosati, 2011] and, to the best of our knowledge, no approximate algorithms exist in the literature; Bienvenu and Rosati [2013] provided approximations of a different type of inconsistent-tolerant semantics called AR semantics.

In this work we present a framework for efficient query answering under both the IAR and ICAR semantics. First, we focus on the ICAR semantics and provide a query answering framework that is based on highly efficient mature data saturation (triple-store) systems. This is particularly interesting as these systems have shown to be able to handle billions of data. Moreover, their properties enable us to propose additional refinements and optimisations. Our algorithm is correct (sound and complete) for ontologies expressed in languages of the DL-Lite family. However, as mentioned, ICAR-based query answering over DLs like EL is intractable [Rosati, 2011], hence our algorithm only computes upper approximations of them. Nevertheless, its structure motivates a new type of ICAR-like semantics which we show that can be computed in polynomial time for a very large number of highly expressive DLs; none such semantics were previously known. Subsequently, we show that our framework can also be used for IAR-based query answering for ontologies expressed in the DLs DL-Lite and EL?nr [Rosati, 2011]. Finally, we have conducted an experimental evaluation obtaining encouraging results as both our approaches (IAR and ICAR) are more efficient than existing IAR-answering systems [Rosati et al., 2012; Bienvenu et al., 2014].

2 Preliminaries

We use standard notions of first-order constants, variables, atoms, satisfiability, entailment (♣=), model, substitutions (σ), etc. We also assume familiarity with datalog. For a conjunction of atoms B = ↵1 ^ ▷ ▷ ▷ ^ ↵n we often abuse notation and write B ✓ S to denote that ¶↵1↪ ▷ ▷ ▷ ↪ ↵n♦ ✓ S.

2.1 Description Logics

Description Logics (DLs) [Baader et al., 2003] constitute of a family of (mostly) decidable fragments of FOL. We use L to denote an arbitrary DL language and next we recapitulate the syntax of the DLs EL? [Baader et al., 2005], DL-Lite [Calvanese et al., 2007], and RL [Motik et al., 2009].

DL-Lite restricts EL? by allowing only for concepts of the form A or 9R▷>; however, R in DL-Lite can also be the inverse of a role of the form S- and we can also have inclusions of the form S v R or S v ≻R for S↪ R roles. Finally, roughly speaking, RL is defined as those DL axioms that can be translated (by simple syntactic transformations) into datalog. For example, 9R▷A v B is an RL axiom since it corresponds to the datalog rule R(x↪ y) ^ A(y) ! B(x), while A v 9R▷> is not, as it corresponds to A(x) ! R(x↪ f(x)).

The set of EL?-concepts is inductively defined by the grammar: C := ? ♣ A ♣ C1 u C2 ♣ 9R▷C, where A (R) is called atomic concept (role) and C(i) are EL?-concepts. An EL?-TBox T is a finite set of inclusions of the form C1 v C2 with C1↪C2 EL?-concepts. Inclusions of the form C1 u C2 v ? (also written as C1 v ≻C2) are called negative and the rest positive. We will also refer to EL?nr, a syntactic restriction of EL? defined by Rosati [2011].

An ABox A is a finite set of assertions of the form A(a) or R(a↪ b) where a↪ b are constants called individuals. A is consistent w.r.t. some TBox T if there exists a model for T [A; otherwise it is inconsistent. Finally, we will use T + to denote all the positive inclusions of a TBox T .

2.2 Queries and Query Answering

A conjunctive query (CQ) is an expression of the form 9~y▷φ(~x↪ ~y), where φ is a conjunction of function-free atoms containing only variables from ~x (called answer variables) or from ~y (called existential variables). A union of conjunctive queries (UCQ) is a set of CQs all having the same number of answer variables. A tuple of constants ~a is a certain answer of a query Q over T [ A if T [ A ♣= 9~y▷φ(~a↪ ~y). We denote with cert(Q↪ T [ A) all the certain answers of Q over T [A.

Query answering can be realised via a technique known as query rewriting [Calvanese et al., 2007] which we recall next.

Definition 1. Let Q be a CQ and let T be a TBox. A datalog rewriting (or simply rewriting) R for Q, T is a pair hRQ↪RDi, where RQ is a UCQ, RD is a datalog program, and for each ABox A consistent w.r.t. T we have:

If RD = ; then R is called UCQ rewriting and instead of hRQ↪ ;i we simply use RQ to identify the rewriting.

A DL L is called datalog rewritable if for every L-TBox T a datalog program RD exists such that for every query Q without existential variables R = h¶Q♦↪RDi is a datalog rewriting for Q↪ T .

All DLs mentioned above are datalog rewritable.

2.3 RL query answering systems

Definition 2. An RL ABox-saturation system ans is a procedure that takes as input a TBox T , an ABox A, and a CQ Q and returns a set of tuples ans(Q↪ T [A) = cert(Q↪As), where As ◆ A, called saturation, contains all assertions ↵ such that T ♣rl [ A ♣= ↵.

Since RL-axioms correspond to datalog rules, to perform query answering systems that support this DL follow a datalog-like saturation approach based on the RL fragment of some TBox T , which in the following we denote by T ♣rl.

Most systems known to us, like GraphDB, Oracle's Semantic Graph, and RDFox are RL ABox-saturation systems.

2.4 Inconsistency-tolerant Query Answering

In order to return meaningful answers even from inconsistent datasets, consistent query answering has been introduced in the areas of databases and ontologies. Next, we recapitulate the so-called IAR and ICAR semantics [Lembo et al., 2011].

Definition 3. For a TBox T and an ABox A let clc(T ↪ A) = ¶↵ ♣ some consistent subset S ✓ A exists s.t. T [ S ♣= ↵♦. The Intersection Closed ABox Repair (ICAR) of T [ A is defined to be the intersection of all subsets A0 ✓ clc(T ↪A) that are consistent w.r.t. T and no other A00 consistent w.r.t. T exists s.t. A0 ⇢ A00 ✓ clc(T ↪A).

Let Q be a CQ and let Aic be the ICAR of T [ A. A tuple ~a is an ICAR-answer of Q w.r.t. T [ A if ~a 2 cert(Q↪ T [Aic ). We denote by cert ic (Q↪ T [A) all ICARanswers of Q w.r.t. T [ A. The IAR semantics and answers (denoted by cert ia (Q↪ T [A)) are defined similarly by replacing clc(T ↪ A) with A.

An algorithm to compute IAR-/ICAR-answers over DLLite-TBoxes was presented by Lembo et al. [2011]: Let R be a UCQ rewriting for some query Q and TBox T . Evaluating R over A would return spurious IAR-/ICAR-answers; hence each Q 2 R needs to be extended with proper negative atoms which will guarantee that only answers that are supported by the intersection of all repairs are returned. Roughly speaking, for each atom A(x) that appears in Q if T ♣= A v ≻B then ≻B(x) is added to Q. We denote this procedure by ref(R↪ T ) and illustrate it with an example; for details please see [Lembo et al., 2011, Section 7.2.2].

Example 4. Consider the following TBox and ABox:

as well as query Q = B(x). Clearly, A is inconsistent w.r.t. T (e.g., due to ¶B(e)↪B0 (e)↪B v ≻B0 ♦), however, we have cert ia (Q↪ T [ A) = ¶c♦ and cert ic (Q↪ T [ A) = ¶a↪ c♦ ("a" is an ICAR-answer since B(a) 2 clc(T ↪A)). Now, RQ = ¶B(x)↪ 9y▷P(x↪ y)♦ is a UCQ rewriting for Q↪ T . Then, ref(RQ↪ T ) returns the following set:

It is easy to see that if we evaluate ref(RQ↪ T ) on A we obtain ¶c♦, i.e., the IAR-answers; notice how the negative atom

≻B0 (x) prevents "e" from being returned as an answer. Finally, to obtain the ICAR-answers, a rewriting algorithm is applied a second time over ref(RQ↪ T ) returning the set:

Evaluating the above over Awill indeed return ¶a↪ c♦. }

3 Efficient ICAR-Answering Over DL-Lite

Interestingly, the saturation computed by ABox-saturation systems given T and Amost likely consists of an approximation of clc(T ↪A). Hence, these systems could (potentially) be used for efficiently computing ICAR-answers.

Example 5. Consider T ↪ A, and Q from Example 4 as well as some RL ABox-saturation system ans. Since T + is an RLTBox, over T + [A ans will compute the saturation As = A[ ¶B(a)↪ B(c)♦. Moreover, ref(¶Q♦↪ T ) = ¶B(x) ^ ≻B0 (x)♦ which evaluated over As returns the set ¶a↪ c♦, i.e., precisely the ICAR-answers. Note that since we want to compute answers in the presence of inconsistencies rather than allow ans to report them, we discarded the negative inclusions and considered how ans behaves over T + [ A. 1 }

However, in TBoxes that contain non-RL-axioms such systems will miss certain (ICAR-)answers. To overcome this issue we consider the TBox completion framework introduced by Stoilos et al. [2011; 2014]. Intuitively, in many cases "materialising" certain entailed axioms of the TBox "helps" the RL system compute all certain answers even over non-RL-TBoxes. We recall this notion next.

Moreover, let Q be some arbitrary CQ. If a rewriting hRQ↪RDi for Q↪ T exists then we have: cert(Q↪ T [A) ✓ ans(RQ↪ T [ C [ A).

Definition 6 ([Stoilos et al., 2011; Stoilos, 2014]). Let T be a TBox and let ans be an RL ABox-saturation system. A completion of T for ans is a set of axioms C such that T ♣= C and for every ABox A consistent w.r.t. T and for every CQ Q without existential variables we have: cert(Q↪ T [A) ✓ ans(Q↪ T [ C [ A).

Example 7. Consider again T ↪A, and Q from Example 4 extended to T 0 and A0 as follows:

Clearly, cert ic (Q↪ T 0 [ A0 ) = cert ic (Q↪ T [ A) [ ¶f♦. Consider also an RL ABox-saturation system ans. Since T ♣rl = ¶9P v B♦ there are clearly ABoxes for which ans will miss answers of Q. For example, we have f 2 cert(Q↪ T 0 [ ¶C(f)♦) but f 62 ans(Q↪ T 0 [ ¶C(f)♦) since T ♣rl [¶C(f)♦ 6♣= B(f). Hence, the ICAR-answer "f" cannot be computed by the procedure we illustrated in Example 5.

However, consider the completion C = ¶C v B♦ of T for ans. Then, over T ♣rl [ C [ A system ans will compute the saturation As = A [ ¶B(f)♦ since T ♣rl [ C [ A ♣= B(f). Finally, evaluating B(x)^≻B0 (x) over As returns the desired ICAR-answers, i.e., the set ¶a↪ c↪ f♦. }

1 For this reason, in the following, when we write T ♣rl we mean T +♣rl ▷

Consequently, completion and RL ABox-saturation systems can be used to efficiently compute the ICAR-answers over DL-Lite TBoxes. A minor technical issue is that we first need to remove all inconsistent singleton assertions.

Definition 8. Let T be a L-TBox and A and ABox, then we denote by cr(A↪ T ) the subset of A that is obtained by removing from A all assertions ↵ 2 A such that the set T [ ¶↵♦ is inconsistent.

Our previous claims are formalised next.

Theorem 9. Let Q be a CQ, let T be a DL-Lite-TBox, let A be an ABox and let hRQ↪RDi be a rewriting for Q↪ T . Let also ans be an RL ABox-saturation system and let T C = T + [ C for C a completion of T for ans. Then,

Note that for DL-Lite TBoxes, completions for RL systems and rewritings for any conjunctive query always exist. Hence, our result is of high practical relevance.

3.1 Additional Optimisations

Interestingly, as the following example shows, the use of ABox-saturation systems allows us to further simplify the structure of the query returned by the procedure ref.

Example 10. Consider the following TBox and ABox:

Consider now an RL ABox-saturation system ans. For ans we have C = ; and over A [ T + it will compute As = A [ ¶A(a)↪ A(b)↪ A0 (b)♦. As can be seen, due to A0 (b) 2 As and ≻A0 (x) in Q0 we can drop atom ≻B0 (x). Indeed, evaluating Q00 = B(x) ^≻A0 (x) over As computes ; as required. }

and consider also the query Q = B(x). Then, we have ref(Q↪ T ) = ¶Q0 ♦, where Q0 = B(x) ^ ≻A0 (x) ^ ≻B0 (x), which evaluated over A returns ;. Note that both of the negative atoms are needed in the query; ≻A0 (x) to exclude individual "a" and ≻B0 (x) to exclude "b".

It follows that some negative atoms added by ref can be discarded.

Definition 11. Let T be a L-TBox and let Q be a CQ. An atom ≻A(x) in Q is called covered if there exists some other atom ≻B(x) in Q such that T ♣= A v B. An atom ≻R(x↪ y) in Q is called covered if there exists some other atom ≻A(x), ≻A(y), ≻S(x↪ y), or ≻S(y↪ x) in Q such that T ♣= 9R v A, 9R- v A, R v S, or R v S-, respectively. We denote with min(Q↪ T ) the query derived from Q by removing all the covered atoms. Moreover, for a UCQ R we define refmin(R↪ T ) = SQ02ref(R↪T ) ¶min(Q0 ↪ T )♦.

Theorem 12. Let Q be a CQ, let T be a DL-Lite-TBox, let A be an ABox and let hRQ↪RDi be a rewriting for Q↪ T . Let also ans be an RL ABox-saturation system and let T C = T + [ C for C a completion of T for ans. Then,

As we will see in the evaluation section, the above minimisation improves performance significantly.

Algorithm 1 ApproxAns(T ↪ A)

• Input: TBox T , ABox A; Output: Saturation As 1: As := cr(A↪ T ) 2: P := toRules(T +♣rl) 3: while No new assertions are added to As do 4: At := ; 5: for all B ! H 2 P s.t. Bσ ✓ As for some σ do 6: if Bσ is consistent w.r.t. T do 7: At := At [ ¶Hσ♦ 8: As := As [At 9: return As

4 ICAR-Answering Over Expressive DLs

Even for DLs with polynomial data complexity, like EL?, query answering under the ICAR semantics has been shown to be CONP-hard [Rosati, 2011] and tractability cannot be recovered even after syntactic restrictions [Rosati, 2011].

Our approach can form the basis for approximate algorithms for computing ICAR-based answers over more expressive DLs. However, as the following example shows, directly applying it can provide with counterintuitive results.

Example 13. Consider the following EL?-TBox T = ¶A u B v C↪ A u B v ?♦, ABox A = ¶A(a)↪ B(a)♦, and query Q = C(x). Clearly, we have clc(T ↪ A) = A and hence cert ic (Q↪ T [ A) = ;.

Now, since T ♣rl = ¶AuB v C♦ any RL ABox-saturation system ans would compute for T + [ A the saturation As = A [ ¶C(a)♦. Finally, since ref(Q↪ T ) = ¶Q♦ then we will have cert(ref(Q↪ T )↪ As) = ¶a♦. }

Consequently, in the case of more expressive languages, ABox-saturation systems compute far too many assertions and hence answers. To control them one has to either extend the ref procedure to include additional negative atoms (e.g., ≻A(x) ^ ≻B(x) in the previous example) or prevent some assertions from being derived in the first place (e.g., C(a)).

We follow the second approach and propose Algorithm 1 which saturates the input ABox over the RL fragment of the given TBox by also taking into account the negative inclusions. More precisely, the algorithm first translates the RL fragment of T + into datalog rules P and then saturates A using P. However, every time some rule of P "fires" (Line 5), before adding the conclusion Hσ to the saturation, in Line 6, it performs a consistency check in order to restrict the amount of assertions that are derived by the saturation procedure.

Clearly, over DL-Lite-TBoxes T Algorithm 1 computes clc(T ↪ A) for any A.

Proposition 14. Let T be a DL-Lite-TBox, let A be an ABox, and let Q be a CQ. Let also ans be some RL ABox-saturation system and C a completion of T for ans. Then, clc(T ↪A) = ApproxAns(T [ C↪A).

However, for more expressive DLs the algorithm approximates clc(T ↪ A) from above.

Theorem 15. Let T be a L-TBox, let ans be an RL ABoxsaturation system, and let C be a completion of T for ans. Then, we have clc(T ↪ A) ✓ ApproxAns(T [ C↪ A)

To make Algorithm 1 exact, i.e., compute clc(T ↪A), for every assertion Hσ inferred at Line 5 one should check if some subset A0 of the original ABox A consistent w.r.t. T exists such that T [A0 ♣= Bσ (and hence also T [A0 ♣=Hσ). In contrast, our algorithm provides a kind of "local" check to decide whether Hσ can be added to As, i.e., it checks if Bσ is consistent w.r.t. the current set of assertions (saturation).

Example 16. Consider the following TBox and ABox:

Then we have clc(T ↪ A) = A [ ¶B(a)♦ but, in contrast, Algorithm 1 would first compute and add B(a) to the saturation As and also compute C(a) due to the consistent subset ¶A(a)↪ B(a)♦ ✓ As. }

Based on the above, we feel that it is intuitive to introduce an extension of function clc which is mostly characterised by our approximate algorithm.

As can be seen, if we explicitly add B(a) to A then we would also have C(a) 2 clc(T ↪A). In other words, materialising consistently entailed assertions can strictly increase the set computed by clc (and hence also the ICAR-answers), something that is not true under the standard first-order semantics where for every ⌃ and φ such that ⌃ ♣= φ, ⌃ and ⌃ [ ¶φ♦ are equivalent.

Definition 17. Let T be a L-TBox and let A be an ABox. We define clc+(T ↪ A) to be the minimal set of assertions satisfying the following conditions:

• ÷ cr(A↪ T) ✓ clc+(T ↪A)

Differently than clc, in clc+ any consistently entailed assertion can be used to support the entailment of other assertions. Hence, the following property follows easily.

• ÷ If some A0 ✓ clc+(T ↪A) consistent w.r.t. T exists such that T [A0 ♣= ↵, then clc+(T ↪A) contains ↵.

Proposition 18. For a L-TBox T and ABox A we have clc(T ↪ A) ✓ clc+(T ↪ A).

Moreover, in contrast to clc, for many DLs clc+ can be computed in polynomial time.

Theorem 19. Let L be some DL such that deciding consistency of ABoxes can be done in polynomial time and L is also datalog rewritable. Then, for every L-TBox T and ABox A clc+(T ↪ A) can be computed in polynomial time with respect to the size of the data.

The following is an immediate consequence of Theorem 19 and various results in datalog rewritability of tractable HornDLs [Calvanese et al., 2007; P´erez-Urbina et al., 2010; Hustadt et al., 2005] as well as highly expressive non-Horn DLs [Kaminski et al., 2014].

Corollary 20. Let L be any of the following DLs:

• ÷ markable-SHI or ALCHI that is simple w.r.t. disjunctive predicates [Kaminski et al., 2014].
• ÷ DL-Lite, ELHI?, or Horn-SHIQ; or

Then, for every L-TBox T and ABox A, clc+(T ↪A) can be computed in polynomial time with respect to the size of A.

Algorithm 2 ABoxIARRepair(T ↪ A)

• 1: A := cr(A↪ T )

Input: TBox T , ABox A; Output: IAR of T [ A

• 2: Φ := ;
• 4: for all R v ≻S 2 T do add query ⇡(S) ^ ⇡(R) to Φ
• 3: for all C v ≻D 2 T do add query ⇡(C) ^ ⇡(D) to Φ
• 5: for all Qφ 2 Φ do
• 7: for all Q0φ 2 Rφ and all σ s.t. Q0φσ ✓ A do
• 6: Compute a UCQ rewriting Rφ for Qφ↪ T
• 8: Remove Q0φσ fromA
• 9: return A

Concluding this section we note that the output of Algorithm 1 can (possibly) be used to compute some upper approximation of the ICAR-answers. More precisely, for some CQ Q we can compute a rewriting hRQ↪RDi for Q↪ T (if it exists) and then calculate cert(ref(RQ↪ T )↪As). However, note that ref would also be an approximation as, to the best of our knowledge, it has only been defined for DL-Lite.

5 Efficient QA under the IAR Semantics

Concluding our technical contributions we show that our framework can also be used to compute IAR-answers. More precisely, by the results of Section 3 and the results by Rosati [2011] we have the following.

Proposition 21. Let T be a L-TBox, let A be an ABox, let Q be a CQ, and let Aia be the IAR of T [ A. Let also ans be an RL ABox-saturation system, let C be a completion of T for ans and let hRQ↪RDi be a rewriting for Q↪ T . Then, we have cert ia (Q↪ T [ A) = ans(RQ↪ T [ C [ Aia ).

For DL-Lite TBoxes, an algorithm to compute Aia was proposed and implemented in [Rosati et al., 2012]. This algorithm annotates all assertions in A and then updates their annotation if they violate some negative inclusions of T . All assertions whose annotation changed are finally removed.

Since completions of DL-Lite and EL TBoxes for RL ABox-saturation systems always exist [Stoilos et al., 2011] and Rosati [2011] showed that for TBoxes expressed in DLLite and EL?nr the IAR Aia of some ABox can be computed in time polynomially w.r.t. the size of A, it follows that our approach can compute the IAR-answers over these languages effectively by exploiting practically scalable RL systems. Unfortunately, even in these cases computing Aia can still be difficult and time-consuming if A is very large.

Inspired by the techniques in [Lembo et al., 2015] we propose a different algorithm that is based on query rewriting and not on ABox annotation; this is depicted in Algorithm 2. The algorithm builds a special query for each negative inclusion in T ; ⇡ maps a concept A to A(x), role R to R(x↪ y) and a concept 9R to 9y▷R(x↪ y). Then, a rewriting for Qφ↪ T is computed and each member of the rewriting is evaluated over A. If some of these queries match to assertions in A, then these should be removed from A as they violate the negative inclusion.

Proposition 22. For a given DL-Lite-TBox T and ABox A, ABoxIARRepair(T ↪A) returns an IAR of T [A.

Algorithm 2 is amenable to an important optimisation. Instead of evaluating Q0φ over A (Lines 7-8) we can proceed as follows: at a pre-processing step we can evaluate all atomic queries A(x) and R(x↪ y) separately and cache their answers and the assertions of A that these atoms have a match. Then, to compute the answers of Q0φ over A we can use the precomputed partial answers of each atom.

6 Evaluation

We implemented our ICAR- (both the standard and the optimised one) and IAR-answering approaches into the prototype system SaQAI 2 (Saturation based Query Answering under Inconsistencies); in the following the various versions of SaQAI (standard/optimised ICAR and IAR) are called SaQ ic ↪ SaQ ic op , and SaQ ia , respectively. Unfortunately, implementing Algorithm 1 would either require modifying the internals of an ABox-saturation system or implementing one from scratch. Our system uses GraphDB [Kiryakov et al., 2010] as an ABox-saturation system, Hydrowl [Stoilos, 2014] to compute completions, and Rapid [Trivela et al., 2015] for rewriting.

For the evaluation we used the experimental setting proposed in [Bienvenu et al., 2014] which consists of a DL-Lite version of the LUBM920 ontology [Lutz et al., 2013] extended with additional negative inclusions, a set of test queries, and several inconsistent ABoxes. We use the same ABox and query names as in [Bienvenu et al., 2014]. For example, Amn indicates an ABox containing data for n universities and inconsistencies added with probability m. Due to space limitations we will present results only for some of the test queries and for the larger datasets. To the best of our knowledge no available ICAR-answering system exists (we could not obtain the preliminary system reported in [Masotti et al., 2011]), hence we compared against CQApri [Bienvenu et al., 2014] and QuID [Rosati et al., 2012], two IAR-answering systems.

Computing a completion of LUBM920 for GraphDB was done only once and required less than 5 seconds. Moreover, no unsatisfiable concepts were detected, hence cr(Amn ↪ T ) also completed in less than a second.

Table 1 presents the results for all considered approaches and tools. In the table we have grouped together number of answers, pre-processing times (note that different systems can perform different pre-processing tasks) and query evaluation. Column Sat denotes loading time of T [ C [Amn into GraphDB and computation of the saturation As ◆ Amn . First, we can note that, as expected, in many queries our ICARanswering approach returned far more answers than CQApri (SaQ ia returned the same IAR-answers as CQApri, however, QuID returned different answers indicating some kind of bug but we did not investigate further). There are actually cases where CQApri returns 0 answers whereas our approach returns some answers to the input query. Second, we can observe that our optimisations in Section 3.1 are indeed quite relevant and improved performance of our ICAR-answering approach significantly. This is because, in most cases refmin (which SaQ ic op uses) computes queries containing much fewer negative atoms than ref; e.g., in query q1 it computes 32

2 http://image.ece.ntua.gr/⇠etsalap/SaQAI

whereas ref computes 353 negative atoms. Third, although SaQ ic op computes more answers (the ICAR-answers) than the other systems, it is significantly faster in nearly all queries compared to QuID and CQApri with only noticeable exception query q4. Nevertheless, besides the fact that our system computes more involved semantics, for the same query over ABox A2e-1 20 CQApri run out of memory and QuID failed to load the dataset within 90 minutes.

Finally, our method for computing the IAR-answers is also significantly more efficient than QuID and CQApri. First, our ABox repairing method is several orders of magnitude faster than QuID which is based on the ABox annotation algorithm in [Rosati et al., 2012] (recall that QuID actually did not manage to load the largest ABox A2e-1 20 ) and is also much faster than the pre-processing step of CQApri. Second, after the repairing step and due to Proposition 21 our system computes the IAR-answers by standard query evaluation using GraphDB (since the ABox is repaired the ref procedure is not required) and this takes in all cases just a fewmilliseconds in contrast to QuID and CQApri that still require several seconds to evaluate the queries they have computed and construct the IAR-answers. All in all both our approaches are much more efficient and robust.

7 Conclusions

We proposed a framework for efficient and scalable IAR- and ICAR-answering over inconsistent Description Logic knowledge bases which is based on mature data saturation technologies. The approach is exact for both semantics over DL-Lite and for the IAR semantics over EL?nr ontologies. For more expressive DLs we proposed an algorithm that computes an approximation of ICAR-answers but which characterises a new family of semantics that can be computed in polynomial time for a very large family of DLs. Our experiments provided with encouraging results as both of our approaches are more efficient and robust compared to the state-of-the-art.