Querying expressive DL Ontologies under the ICAR semantics Despoina Trivela1 , Giorgos Stoilos2 , and Vasilis Vassalos1 . 1 : Athens University of Economics and Business, Athens, Greece. 2 : Babylon Health London, SW3 3DD, UK. Abstract. Inconsistency-tolerant semantics, like the ICAR semantics, have been proposed to perform query answering over inconsistent DL knowledge bases. In the current paper we propose a general framework for ICAR-answering over arbitary Horn-DLs that is based on rewriting. We describe conditions for termination of our rewriting algorithm and show that existing techniques and results on UCQ-rewritability can be used to check if they are satisfied for a given input ontology and query. 1 Introduction Query answering over ontologies expressed in Description Logics (DL) has re- cieved significant attention from both a practical and a theoretical perspective. In the vast majority of works, the problem has been studied over datasets that are consistent w.r.t. the ontology [9, 17, 12, 20]. However, in real-world applications this is not always the case, e.g. in data integration applications the data deriving from disparse sources may contradict the ontological axioms. A straightforward approach to perform consistent query answering would be to first remove the conflicting elements from the datasets. However, this is not always possible as the data may be reside in distributed or access restricted data sources, or be subject to frequent and diverse modifications. To address this issue, inconsistency-tolerant semantics have been proposed that describe which answers are meaningful to be returned in the presence of inconsistent data. Examples of such semantics are the IAR, ICAR, AR seman- tics [15, 14] that are based on the notion of the repair, that is a maximal (w.r.t. inclusion) consistent subset of the original dataset. The IAR and ICAR semantics have shown to have better computational properties since the query evaluation problem over DL-Lite ontologies is in AC0 w.r.t. data complexity [16], while it is in coNP for the AR semantics. However, computing answers using inconsistency- tolerant semantics has been proved quite difficult for DLs more expressive than DL-Lite. More precisely, Rosati [18] showed that the problem of IAR and ICAR- answering is at least coNP-hard w.r.t. data complexity for almost all well-known DLs from EL⊥ to SHIQ. Moreover, in the EL⊥nr fragment of EL⊥ where query answering is tractable for the IAR semantics, the problem remains in coNP for the ICAR semantics. Consequently, important research results on consistent query answering [18, 7, 16, 3, 22] focus on fragments of DL-Lite. However, in [22] a practical system was proposed for the ICAR and IAR semantics that com- putes upper approximations for DLs more expressive than DL-Lite. Moreover, an algorithm for IAR-answering was proposed in [21] that can handle arbitary DLs but need not terminate. Despite the work presented in [22] the problem of designing practical ICAR-answering algorithms for expressive DLs is open. In the current paper we extend our previous work of [21] and study ICAR- answering over expressive DL ontologies. More precisely, we present a general framework for ICAR-answering that is based on query rewriting. Our rewriting algorithm has as a starting point the one presented in [15]. Given an input query and ontology expressed in a Horn-DL if our algorithm terminates, it computes a datalog program, extended with negation, that can be evaluated over the initial dataset to compute the ICAR-answers. Based on our analysis and previous results [21] we describe the conditions that ensure termination of our algorithm. The termination conditions are related to the notion of UCQ-rewritability that has been studied quite extensively in DLs [1, 4, 11]. Consequently, we are able to provide positive results for instance queries and ontologies expressed in semi- acyclic-EL⊥ [5], as well as UCQ-rewritable queries over ontologies expressed in EL⊥nr . For DLs and queries for which the termination conditions are not generally satisfied, we exploit previous works [6, 8, 11] and provide an approach to check termination over a fixed input ontology and query. This allows us to design a framework for ICAR-answering over expressive Horn-DLs. Finally, we have conducted a preliminary evaluation of our approach. We obtained positive results showing that it is possible to perform ICAR-answering even in the case of DLs for which the problem is in general intractable. 2 Preliminaries Description Logics A DL knowledge base (KB) K consists of a TBox T , and an ABox A, K = T ∪ A. T and A are constructed from the countable and pairwise disjoint sets C, R, and I of atomic concepts (unary predicates), atomic roles (binary predicates), and individuals (constants). An ABox A is a finite set of assertions of the form A(a) or R(a, b) where a, b ∈ I. A TBox T is a set of DL axioms. An EL⊥ concept is inductively defined by the syntax: C := > | ⊥ | A | C1 u C2 | ∃R.C, where A ∈ C and R ∈ R 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. DL-LiteR (or simply DL-Lite) restricts EL⊥ by allowing concepts of the form A, and ∃R.>; R in DL- Lite can also be the inverse of a role of the form S − and we can also have role inclusions of the form S v R or S v ¬R for S, R roles. An ABox A is consistent w.r.t. some TBox T if there exists a model for the KB K = T ∪ A; otherwise it is inconsistent. The semantics of DLs can be given by a well-known translation to First-Order Logic (FOL) [2]. Table 1 presents the translation of EL⊥ and DL-Lite axioms to first order clauses (inverse roles have been omitted). In the following we assume that the TBox axioms are translated into FOL. Table 1: Translation of DL axioms into FOL DL Axiom Clause BvA A(x) ← B(x) A u B v ⊥ ⊥ ← A(x) ∧ B(x) B1 u B2 v A A(x) ← B1 (x) ∧ B2 (x) A v ∃R.B R(x, f (x)) ← A(x), B(f (x)) ← A(x) ∃R v A A(x) ← R(x, y) ∃R.B v A A(x) ← R(x, y) ∧ B(x) P vR R(x, y) ← P (x, y) P v ¬R ⊥ ← R(x, y) ∧ P (x, y) Datalog and Conjunctive Queries A disjunctive datalog clause r (also called rule) is a function-free clause of the form ∀~x, ~y (ψ(~x) ← φ(~x, ~y )) where φ(~x, ~y ) is a conjunction of positive or negative atoms called the body of the clause and ψ(~x) is a disjunction of positive atoms called its head. For simplicity we will omit variable quantifiers and write ψ(~x) ← φ(~x, ~y ). A datalog clause is a disjunctive datalog clause where the head contains a single atom. A Horn-clause is a datalog clause where the body contains only positive atoms. A (disjunctive) datalog program P is a finite set of (disjunctive) datalog clauses. We consider Herbrand models over all constants from P. We say that a model M of P is minimal if there is no model M0 of P such that M0 is a subset of M. A positive ground atom D(~a) is entailed by P iff all minimal models of P contain D(~a); a negative ground atom ¬D(~a) is entailed by P iff D(~a) is not icluded in the minimal models of P. The evaluation of P over an ABox A is the set of ground atoms entailed by the program P ∪ A. A conjunctive query (CQ) Q is a datalog clause with head predicate Q. The variables occuring in Q are called answer variables. A boolean query Q is a CQ with no answer variables. An instance query is a CQ of the form Q(x) ← A(x) (we often simply write A(x)). A UCQ is a finite set of CQs. A tuple of constants ~a is a certain answer of Q over a KB K = T ∪ A if the arity of ~a agrees with the arity of Q and T ∪ A |= Q(~a), where Q(~a) denotes the boolean query obtained by replacing the answer variables with ~a. We use cert(Q, T ∪ A) to denote all certain answers of Q w.r.t. K = T ∪ A. Definition 1. Let T be a TBox and Q a CQ. A datalog-rewriting (or simply rewriting) of Q w.r.t. T is a datalog program R such that for any ABox A consistent w.r.t. T we have T ∪ A |= Q(~a) iff R ∪ A |= Q(~a), or in case Q is boolean T ∪ A |= Q iff R ∪ A |= Q. We say that a query Q is datalog-rewritable w.r.t. T if there exists a datalog-rewriting R of Q w.r.t. T ; if R is a UCQ, then Q is called UCQ-rewritable w.r.t. T . V V Note that we will refer to a clause of the form H(~s) ← i αi ∧ j ¬Bj , where αi are positive atoms and Bj are conjunctions of positive atoms, as a datalog clause. Indeed V such V a clause is equisatisfiable to a datalog program that inlcudes H(~s) ← i αi ∧ j ¬βj and βj ← Bj , for all j, where βj are positive atoms. Inconsistency-tolerant Semantics Definitions 2 and 3 recapitulate some of the notions used in the IAR and ICAR semantics [15]. Defintion 4 formalises the notion of the rewriting under the IAR and ICAR semantics. Definition 2. Consider a TBox T and ABox A we define the consistent logical consequences of T , A as the set clc(T , A) = {a | some S ⊆ A exists s.t. T ∪S |= a and S is consistent w.r.t. T }, where we use a to denote an assertion. Definition 3. A repair of a set of assertions S w.r.t. a TBox T is any maximal (w.r.t. set inclusion) subset of S that is consistent w.r.t. T . – We use Air to denote the intersection of all repairs of A w.r.t. T . Let Q be a CQ and let K = T ∪ A be a KB. A tuple of constants ~a is called an IAR- answer of Q over K if ~a ∈ cert(Q, T ∪ Air ). We use certir (Q, T ∪ A) to denote the set of all IAR-answers of Q over K and we also write T ∪ A |=ir Q(~a). – We use Aicar to denote the intersection of all repairs of clc(T , A). Let Q be a CQ and let K = T ∪ A be a KB. A tuple of constants ~a is called a ICAR- answer of Q over K if ~a ∈ cert(Q, T ∪ Aicar ). We use certicar (Q, T ∪ A) to denote the set of all ICAR-answers of Q over K and we also write T ∪A |=icar Q(~a). Definition 4. Given a TBox and a CQ Q, an IAR-rewriting Rir of Q w.r.t. T is a datalog program such that for every ABox A we have T ∪ A |=ir Q(~a) iff Rir ∪ A |= Q(~a). Similarly, for an ICAR-rewriting Ricr we have T ∪ A |=icr Q(~a) iff Ricr ∪ A |= Q(~a). 3 Towards an ICAR-answering algorithm The problem of answering queries under the ICAR semantics was first investi- gated in [15] where a rewriting approach was presented for DL-Lite. Given an input TBox and query, the proposed algorithm computes a rewriting of the query that can be evaluated over any ABox to obtain the ICAR-answers. Example 1 illustrates the approach of [15]. Example 1. Let T be the DL-Lite TBox T = {C(x) ← A(x), ⊥ ← A(x) ∧ B(x)}, Q the query Q = Q(x) ← C(x) and A the ABox A = {A(a), B(a)}. A has two repairs, that is {A(a)} and {B(a)}, and hence Air = ∅. It is not hard to verify that clc(T , A) = {C(a), A(a), B(a)}. Moreover, clc(T , A) has two repairs, that is {A(a), C(a)} and {B(a), C(a)} and hence Aicar = {C(a)}. Therefore, cert(Q, T ∪ Aicar ) = {a} and by definition of the ICAR-answers it holds that certicar (Q, T ∪ A) = {a}. In the first step, the algorithm in [15] computes the rewriting R of Q, T under the standard semantics, R = {Q(x) ← C(x), Q(x) ← A(x)}. Then, it extends the queries in R with the appropriate negative atoms, R0 = {Q(x) ← C(x), Q(x) ← A(x) ∧ ¬B(x)}. The negative atoms in R0 guarantee that the evaluation of R0 over A will only return answers from Air . Indeed, atom ¬B(x) prevents Q(x) ← A(x) ∧ ¬B(x) from binding with A(a) which is not included in Air . At next step, the algorithm applies the rewriting procedure (under the standard semantics) once more on the elements of R0 (only on the positive atoms) to obtain R00 = R0 ∪ {Q(x) ← A(x)} that captures the assertions in clc(T , A). When Q(x) ← A(x) of R00 is evaluated over A we obtain the ICAR-answer {a}, cert(R00 , A) = certicar (Q, T ∪ A). ♦ A hybrid approach for ICAR-answering was presented in [22] that employs a rewriting, as well as an ABox saturation procedure. More precisely, given an input query Q, a TBox T , and an ABox A, the algorithm in [22] exploits existing approaches [13, 19] to compute the saturated ABox, that is the set of the assertions entailed from A and the axioms of T that can be translated into datalog. Then, it evaluates the IAR-rewriting of Q, T over the saturated A. The algorithm supports DL-Lite and it can be used to compute upper approximations of the ICAR-answers for more expressive DLs. Example 2. Consider the following EL⊥ TBox T , the query Q = Q(x) ← C(x) and the ABox A = {A(a), B(a)}. T = { C(x) ← A(x) ∧ K(x) K(x) ← B(x) ⊥ ← A(x) ∧ B(x)} It is not hard to verify that clc(T , A) = {A(a), B(a), K(a)} and that Aicar = {K(a)}. Hence, certicar (Q, T ∪ A) = ∅. By applying the technique of [22] we first compute the saturation of A, As = {C(a), A(a), B(a), K(a)} and the IAR-rewriting, Rir = {Q(x) ← C(x), Q(x) ← A(x) ∧ K(x) ∧ ¬B(x), Q(x) ← A(x) ∧ B(x) ∧ ¬B(x)}. When we evaluate Q(x) ← C(x) of Rir over As we yield {a} which is not an ICAR-answer. Notice that the saturated ABox As is an upper approximation of clc(T , A). ♦ ICAR-answering over DL-Lite is FO-rewritable, and therefore in AC0 in data complexity. However, it was shown that for more expressive DLs, consistent query answering under the ICAR is no longer tractable; actually, it is already coNP-hard in data complexity in EL⊥nr [18]. Identifying DLs for which ICAR- answering is tractable is quite challenging. It was shown by Rosati [18] that tractability of IAR-answering does not imply tractability of ICAR-answering and the reason is the need to compute clc. Despite the theoretical studies over the ICAR semantics [15, 18], there are no algorithms for ICAR-answering over expressive DLs. In the following example we attempt to employ the rewriting approach presented in [15] for an input TBox expressed in EL⊥ . Example 3. Consider the TBox T and query Q of Example 2. In the first step, we compute the IAR-rewriting of Q, T . For this purpose, we apply the IAR- rewriting algorithm presented in [21] that takes as input an arbitary DL TBox. Rir = { Q(x) ← C(x) (1) Q(x) ← A(x) ∧ K(x) ∧ ¬(A(x) ∧ B(x)) (2) Q(x) ← A(x) ∧ B(x) ∧ ¬(A(x) ∧ B(x))} (3) Next, by following the same approach as in [15], we apply a rewriting procedure on the elements of Rir ingoring their negative part (we omit clause (3)): (1) Q(x) ← A(x) ∧ K(x) (4) Q(x) ← A(x) ∧ B(x) (5) (2) Q(x) ← A(x) ∧ B(x) ∧ ¬(A(x) ∧ B(x)) (6) Finally, we construct the set R0 = Rir ∪ {(4), (5)}. Notice that when Q(x) ← A(x) ∧ B(x) of R0 is evaluated over A we obtain Q(a), but {a} is not in certicar (Q, T , A); hence R0 is not an ICAR-rewriting. In order to fix this issue, one could check if the clause ⊥ ← A(x) ∧ B(x) is entailed from T to decide whether Q(x) ← A(x) ∧ B(x) is included in the ICAR-rewriting. In particular, since T |= ⊥ ← A(x) ∧ B(x), any set of the form {A(a), B(a)} is inconsistent w.r.t. T , and hence it cannot be used to infer an assertion included in clc(T , A). Consequently, the clause Q(x) ← A(x) ∧ B(x) that bounds to assertions of the form {A(a), B(a)} cannot be used to yield an ICAR-answer. In the same spirit, the clause Q(x) ← A(x) ∧ K(x) should be included in the output ICAR-rewriting since it holds that T 6|= ⊥ ← A(x)∧K(x). By eliminating (5) from R0 we obtain the ICAR-rewriting Ricr = Rir ∪ {(4)}. ♦ Example 4. Consider the following TBox T , query Q(x) ← A(x) and ABox A = {R(a, b), K(b), R(b, a)}. T = { A(x) ← R(x, y) ∧ K(y) (7) A(x) ← R(x, y) ∧ A(y) (8) ⊥ ← K(x) ∧ R(x, y)} (9) We first compute the IAR-rewriting of Q w.r.t. T by applying the calculus of [21]: Rir = { Q(x) ← A(x) (10) A(x) ← R(x, y) ∧ K(y) ∧ ¬(R(x, y) ∧ K(x)) ∧ ¬(R(y, z) ∧ K(y))(11) A(x) ← R(x, y) ∧ A(y) ∧ ¬(R(x, y) ∧ K(x))} (12) Next, we apply a rewriting procedure on the elements of Rir : (10), (12) A(x) ← R(x, y) ∧ K(y) (7) A(x) ← R(x, y) ∧ A(y) (8) In line with the Example 4 notice that for the clauses (7),(8) in R0 it holds that T 6|= ⊥ ← R(x, y) ∧ K(y), T 6|= ⊥ ← R(x, y) ∧ A(y). However, R0 = Rir ∪ {(7), (8)} is not an ICAR-rewriting. Indeed, when we evaluate (7) over A we obtain A(a) and because of (8) we derive A(b). However, b is not an ICAR- answer since A(b) ∈ / clc(T , A). This is because to derive A(b) we have used {R(a, b), K(b), R(b, a)} which is inconsistent w.r.t. T . ♦ As illustrated in Example 4 in order to introduce a recursive clause of the form A(x) ← R(x, y) ∧ A(y) in the ICAR-rewriting it is not sufficient to examine if T 6|= ⊥ ← R(x, y) ∧ A(y); since the concept A participates in a recursion, there is an infinite number of negative clauses for which we should examine if they are entailed from T . Intuitively, this is the reason for the co-NP data complexity [18] of the ICAR-answering problem: if the input query contains concepts involved in some recursion (such as concept A in our example), then the number of ABox assertions that can be used to infer an assertion in clc(T , A) is unbounded. 4 ICAR-rewriting over expressive DLs Based on the ideas presented in Section 3 we propose an algorithm for ICAR- rewriting over a TBox expressed in an arbitary DL. Definition 5 describes the notion of the negative closure that was used in [21] to obtain the IAR-rewriting. Intuitively, the negative closure Tcn of a TBox T is a finite set of negative clauses that can capture the negative clauses entailed from T . We use Tcn to examine if the condition described in Example 3 holds. V T , denoted by TVcn , is a finite set Definition 5. A negative closure of a TBox of negativeVclauses suchVthat T |= ⊥ ← βi iff some ⊥ ← αi in Tcn exists with ⊥ ← αi |= ⊥ ← βi . Algorithm 1 ICAR-Rewriting Input: a CQ Q and a L-TBox T 1: Compute a negative closure Tcn of T 2: Compute the IAR-rewriting Rir of Q w.r.t. T . 3: Ricr := Rir V 4: for H(~s) ← i αi ∧ j ¬βj ∈ Rir do V V 5: Compute a UCQ-rewriting V 0 Rα of Q(~s) ← i αi w.r.t. T 6: for each Q(~s) ← i αi ∈ Rα do if for every clause C ∈ TcnVit holdsVC 6|= ⊥ ← i αi0 then V 7: icr icr 0 8: R = R ∪ {H(~s) ← i αi ∧ j ¬βj } 9: end if 10: end for 11: end for 12: return Ricr Algorithm 1 computes the IAR-rewriting Rir (line (2)) by applying the proce- dure presented in [21]. Then, in order to build the set Ricr , it applies a rewriting procedure on the elements of Rir by neglecting their negative part. More pre- ir cisely, for the positive body atoms αV i of every element in R , it constructs the UCQ-rewriting of the query Q(~s) ← i αi (lines (4)-(5)). Condition in line (7) is necessary, as explained in Section 3, in order to only retrieve facts from clc(T , A) when evaluating Ricr over A. Example 5. Consider the following EL⊥ TBox T and query Q(x) ← A(x). T = {A(x) ← R(x, y) ∧ B(y) (13) B(x) ← C(x) (14) ⊥ ← B(x) ∧ K(x)} (15) In the first step, Algorithm 1 computes the IAR-rewriting of Q: Rir = { Q(x) ← A(x) (16) A(x) ← R(x, y) ∧ B(y) ∧ ¬(B(y) ∧ K(y)) (17) A(x) ← R(x, y) ∧ C(y) ∧ ¬(C(y) ∧ K(y))} (18) Next, by considering the clauses (16), (17), (18) in Rir it computes the UCQ- rewriting of Q(x) ← A(x), Q(x) ← R(x, y) ∧ B(y), Q(x) ← R(x, y) ∧ C(y): (16) Q(x) ← R(x, y) ∧ B(y) (19) Q(x) ← R(x, y) ∧ C(y) (20) (17) A(x) ← R(x, y) ∧ C(y) ∧ ¬(B(y) ∧ K(y)) (21) The negative closure of T is Tcn = {⊥ ← B(x) ∧ K(x), ⊥ ← C(x) ∧ K(x)}. Therefore, the clauses ⊥ ← R(x, y) ∧ B(y), and ⊥ ← R(x, y) ∧ C(y) are not entailed by Tcn and condition in line (7) is satisfied. Finally, Algorithm 1 outputs Ricr = Rir ∪ {(19), (20), (21)} that is an ICAR-rewriting of Q w.r.t. T . ♦ Theorem 1. Let T be a L TBox where L is a Horn-DL, and let Q be a CQ. If Q is UCQ-rewritable w.r.t. T and there exists a negative closure Tcn of T , then Algorithm 1 terminates and computes the ICAR-rewriting of Q w.r.t. T . Proof. (sketch) In [21] it was shown that if there exists a negative closure of T , and Q is datalog rewritable, then there always exists an IAR-rewriting Rir of Q w.r.t. T (Theorem 6). Therefore, if there exists a negative closure of T and a UCQ-rewriting R of Q w.r.t. T , then there also exists an IAR-rewriting of Q w.r.t. T , and Algorithm 1 terminates. To prove correctness of Algorithm 1 we first show that Ricr ∪ A |= Q(~a) iff Rir ∪ clc(A) |= Q(~a). By definition of Rir it holds that Rir ∪ clc(A) |= Q(~a) iff R ∪ clc(A) |=ir Q(~a). Finally, by definition of Aicar we conclude that Ricr ∪ A |= Q(~a) iff R ∪ A |=icr Q(~a). t u 5 Positive Results for ICAR-answering In this section we exploit results on UCQ-rewritability of queries over a range of DLs and the ICAR-rewriting approach presented in Section 4, to provide positive results for ICAR-answering over Horn-DLs that do not fall into the DL-Lite fragment. The authors in [5] showed that instance queries over semi-acyclic-EL⊥ TBoxes are always UCQ-rewritable. Moreover, in [21] it was shown that there always ex- ists a negative closure for a semi-acyclic-EL⊥ TBox. Theorem 2 follows. Theorem 2. Let T be a semi-acyclic-EL⊥ TBox and let Q be an instance query. Then, on input T and Q, Algorithm 1 terminates and computes an ICAR- rewriting of Q w.r.t. T . In [18] the EL⊥nr fragment of EL⊥ was studied and in [21] it was shown that there always exists a negative closure of an EL⊥nr TBox. Therefore, although the problem of ICAR-answering of CQs over EL⊥nr TBoxes is in general intractable, for a given UCQ-rewritable CQ we obtain the following result. Theorem 3. Let T be a EL⊥nr TBox and let Q be a CQ that is UCQ-rewritable. Then, on input T and Q Algorithm 1 terminates and computes an ICAR- rewriting of Q w.r.t. T . To check if a given query is UCQ-rewritable we can exploit results in UCQ- rewritability of queries over DLs that are not always UCQ-rewritable [6, 4, 11]. The authors in [6] study UCQ-rewritability of a given instance query over Horn- DLs, like EL⊥ , ELI ⊥ and Horn-SHIF. These results were used to design a practical algorithm for checking UCQ-rewritability of instance queries [11]. Sub- sequently, the system of [11] was extended to support rooted CQs [10]. Moreover, one can also check if a negative closure Tcn exists for a given TBox, T , by using the condition presented in [21]. This condition is described in Lemma 1. Intuitively, the non-existence of Tcn is related to concepts in the negative clauses of T that participate in some recursion. Lemma 1. Let T be a L TBox where L is a Horn-DL. Let the set of concepts S = {Ai (x) | ⊥ ← A1 (x) ∧ . . . ∧ Am (x) ∈ T }. If every instance query Q(x) ← Ai (x) in S is UCQ-rewritable w.r.t. T and consistent ABoxes, then there exists a negative closure Tcn of T . Therefore, given an TBox T expressed in a Horn-DL one can decide on the existence of a negative closure by using the system of [11] to check UCQ- rewritability of all relevant instance queries described in Lemma 1. Moreover, the system of [11] can be used to check UCQ-rewritability of the input query Q. If the conditions of Theorem 1 are satisfied, Algorithm 1 can be used to obtain an ICAR-rewriting of Q, T . 6 Evaluation We have created a prototype system to perform a preliminary experimental eval- uation of the proposed framework. Our system is based on the implementation of Algorithm 1. At first step, the UCQ-rewritability of the input query Q is ex- amined by using the system Grind [10]. Next, our system uses the IAR-rewriting framework implemented in [21] to decide if there exists a negative closure of the input TBox T and if so, to compute an IAR-rewriting of Q and T . If Q is not UCQ-rewritable, or if a negative closure cannot be computed for T , then the system reports that it cannot output an ICAR-rewriting. Otherwise, it proceeds tR |Ricr | q ¬ max avg tR |Rir | q ¬ max avg 1 889 44 623 96% 7 6.5 17 037 98 119 96% 50 1 1 025 21 171 96% 7 6.4 32 213 101 646 96% 50 1 1 140 21 170 96% 7 6.5 15 651 101 620 96% 2 1.1 1 091 21 927 96% 14 6.7 1 049 3 511 92% 2 1.1 1314 22 694 96% 7 6.5 1 701 31 80% 50 50 envo MOHSE 129 75 86% 4 4.0 1 923 3 66% 2 2.0 1 441 21 932 97% 7 6.5 1 269 43 72% 50 50.0 1 126 21 170 96% 7 6.5 1 314 43 51% 50 50 2 538 21 170 96% 7 6.5 2 9375 98115 96% 50 21.5 2 385 21 934 96% 7 6.5 34 318 98115 96% 50 21 194 285 7% 7 4.2 178 351 82 885 80% 6 1.0 148 406 5% 7 3.2 175 581 82 885 80% 6 1.6 85 13 100% 13 4.1 172 970 82 886 80% 6 1.57 88 29 100% 4 2.8 36 33 36% 6 1.7 51 307 7% 7 4.2 176 622 83 884 80% 6 1.0 FBbi Not-Galen 72 9 100% 10 2.8 176 102 82 886 80% 6 1.0 90 555 54% 7 3.5 171 392 82 885 80% 5 1.0 76 295 51% 1 1.0 32 41 51% 1 1.0 56 280 8% 7 4.2 132 558 82 885 80% 6 1.0 90 547 53% 7 3.9 170 489 82 885 80% 6 1.0 Table 2: Results for computation of IAR-rewritings. in computing the ICAR-rewriting Ricr as described in lines 3-10. The whole sys- tem currently supports ontologies expressed in EL⊥ which is the DL supported by the current implementation of Grind. To generate our experimental setting we examined the ontologies ENVO, FBbi, MOHSE, NBO, Not-Galen that were used in [10] to evaluate Grind. We did not consider SO as it was reported in [21] that a negative closure cannot be constructed for this ontology. The ontologies ENVO and FBbi include negative axioms. For the rest ontologies, that is MOHSE and Not-Galen, we manually added negative axioms. For this purpose we tried to use concepts that appear in different levels in the concepts hierarchy, so that these affect large or small parts of the ontology. Each ontology used in [10] came with 10 handcrafted queries. Among them we used only those queries that include concepts involved in some negative axiom and for which the Grind system reported they are UCQ- rewritable. We have also manually constructed test queries that each one of them contains at least one body atom that uses a concept or role involved in a negative axiom. More precisely, for an axiom of the form B v ¬C we have constructed queries Q(x) ← A(x) and Q(x) ← D(x) such that T |= A v B and T |= B v D. Overall, for each ontology we used 10 test queries that satisfy the UCQ-rewritability condition. Our results are depicted in Table 2. Columns tR , |Rir | and q ¬ present the time to obtain the ICAR-rewriting in ms, the number of clauses in the output rewriting, and the percentage of the clauses in the output that contain a negative part. Finally columns max and avg present the maximum and average number of negative atoms in the elements of the rewriting. In most cases the ICAR- rewriting was obtained within a few seconds. In contrast, in the case of Not- Galen the time to compute the rewriting was up to 3 minutes. This is because, the rewriting procedure (described in line 5, Algorithm 1) was applied on every element of the IAR-rewriting which was quite large for almost all test queries. One could avoid the several calls of the rewriting procedure and exploit the rewritings that have already been constructed during the IAR-rewriting process. For example, for an input TBox T = {A(x) ← A1 (x), ⊥ ← A(x) ∧ B(x)} and query Q = Q(x) ← A(x) ∧ C(x) the IAR-rewriting is of the form Rir = {Q(x) ← A(x) ∧ C(x) ∧ ¬(A(x) ∧ B(x)) ∧ ¬(A1 (x) ∧ B(x)), Q(x) ← A1 (x) ∧ C(x) ∧ ¬(A1 (x) ∧ B(x))} and to obtain Rir the standard rewriting R = {Q(x) ← A(x) ∧ C(x), Q(x) ← A1 (x) ∧ C(x)} must be computed. Therefore, to construct the ICAR-rewriting one could make use of R instead of applying anew rewriting procedure on every element of Rir . Our implementation does not involve such optimisations however we feel that they could reduce the rewriting times. Regarding the size of the output rewriting, one could design optimisations to eliminate the redudant elements from the output, Ricr . For example, the clause Q(x) ← A1 (x) ∧ C(x) ∧ ¬(A(x) ∧ B(x)) ∧ ¬(A1 (x) ∧ B(x)) is subsumed by Q(x) ← A1 (x) ∧ C(x) ∧ ¬(A1 (x) ∧ B(x)) and hence the former can be discarded from Ricr . Further work is required in that respect to reduce the size of Ricr . Finally, the number of negative conjuncts in the elements of the rewriting was quite small (up to 50). Note that the evaluation in [22] showed that triple- store systems can handle a large number of negative atoms (even more than one hundred). In conclusion, in most cases we have been able to obtain within reasonable time an ICAR-rewriting for our test ontologies and queries. Summarizing, our evaluation results show that we were able, in most cases, to compute an ICAR-rewriting for the given TBoxes for which the problem is in general intractable. Moreover, computing the ICAR-rewriting can be done relatively efficiently and the number of negative atoms added in the clauses was usually quite small. 7 Conclusions In this work we have provided a general framework for ICAR-answering for arbitary Horn-DLs. We have presented an algorithm that takes as an input a TBox and a query; if it terminates, it outputs a datalog program, that can be used to compute the ICAR-answers. We described the termination condition of our algorithm and showed that the tractability results hold for the semi- acyclic-EL⊥ . Furthermore, in cases of inputs that do not satisfy the termination condition in general, we can exploit recent results to check termination. Our experiments provided encouraging results as in almost all cases we were able to compute an ICAR-rewriting in reasonable time. Further experimental evaluation to examine whether the conditions apply in practice is left for future work. References 1. Alessandro Artale, Diego Calvanese, Roman Kontchakov, and Michael Za- kharyaschev. The DL-Lite Family and Relations. Journal of Artificial Intelligence Research, 36:1–69, 2009. 2. Franz Baader, Deborah L. McGuinness, Daniele Nardi, and Peter F. Patel- Schneider. The Description Logic Handbook: Theory, implementation and applica- tions. Cambridge University Press, 2002. 3. Meghyn Bienvenu, Camille Bourgaux, and François Goasdoué. Querying Incon- sistent Description Logic Knowledge Bases under Preferred Repair Semantics. In AAAI, pages 996–1002, 2014. 4. Meghyn Bienvenu, Peter Hansen, Carsten Lutz, and Frank Wolter. First Order- Rewritability and Containment of Conjunctive Queries in Horn Description Logics. In IJCAI: International Joint Conference on Artificial Intelligence, 2016. 5. Meghyn Bienvenu, Carsten Lutz, and Frank Wolter. Deciding FO-Rewritability in EL. In Proceedings of the Twenty-Fifth International Workshop on Description Logics, 2012. 6. Meghyn Bienvenu, Carsten Lutz, and Frank Wolter. First-Order Rewritability of Atomic Queries in Horn Description Logics. In Proceeding of the Twenty-Third International Joint Conference on Artificial Intelligence, 2013. 7. Meghyn Bienvenu and Riccardo Rosati. New Inconsistency-Tolerant Semantics for Robust Ontology-Based Data Access. In Proceedings of the Twenty-Sixth Interna- tional Workshop on Description Logics, 2013. 8. Meghyn Bienvenu, Balder ten Cate, Carsten Lutz, and Frank Wolter. Ontology- Based Data Access: A Study through Disjunctive Datalog, CSP, and MMSNP. ACM Transactions on Database Systems, 39(4):33:1–33:44, 2014. 9. Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, and Riccardo Rosati. Tractable Reasoning and Efficient Query Answering in De- scription Logics: The DL-Lite Family. Journal of Automated Reasoning, 39(3):385– 429, 2007. 10. Peter Hansen and Carsten Lutz. Computing FO-Rewritings in EL in Practice: From Atomic to Conjunctive Queries. In The Semantic Web - ISWC 2017 - 16th International Semantic Web Conference, Vienna, Austria, October 21-25, 2017, Proceedings, Part I, pages 347–363, 2017. 11. Peter Hansen, Carsten Lutz, Inanç Seylan, and Frank Wolter. Efficient Query Rewriting in the Description Logic EL and Beyond. In Proceedings of the Twenty- Fourth International Joint Conference on Artificial Intelligence, pages 3034–3040, 2015. 12. Stanislav Kikot, Roman Kontchakov, and Michael Zakharyaschev. Conjunctive Query Answering with OWL 2 QL. In Proceedings of the Thirteenth International Conference on Principles of Knowledge Representation and Reasoning, 2012. 13. Atanas Kiryakov, Barry Bishoa, Damyan Ognyanoff, Ivan Peikov, Zdravko Tashev, and Ruslan Velkov. The features of bigowlim that enabled the bbcs world cup website. In Workshop on Semantic Data Management (SemData), pages 13–17, 2010. 14. Domenico Lembo, Maurizio Lenzerini, Riccardo Rosati, Marco Ruzzi, and Domenico Fabio Savo. Inconsistency-tolerant Semantics for Description Logics. In Proceedings of Fourth International Conference on Web Reasoning and Rule Systems, pages 103–117. Springer, 2010. 15. Domenico Lembo, Maurizio Lenzerini, Riccardo Rosati, Marco Ruzzi, and Domenico Fabio Savo. Query rewriting for inconsistent DL-Lite ontologies. In Proceedings of the Fifth International Conference on Web Reasoning and Rule Systems, pages 155–169. Springer, 2011. 16. Domenico Lembo, Maurizio Lenzerini, Riccardo Rosati, Marco Ruzzi, and Domenico Fabio Savo. Inconsistency-tolerant Query Answering in Ontology-Based Data Access. Journal of Web Semantics, 33:3–29, 2015. 17. Héctor Pérez-Urbina, Boris Motik, and Ian Horrocks. Tractable Query Answering and Rewriting under Description Logic Constraints. Journal of Applied Logic, 8(2):186–209, 2010. 18. Riccardo Rosati. On the Complexity of Dealing with Inconsistency in Descrip- tion Logic Ontologies. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, pages 1057–1062, 2011. 19. Giorgos Stoilos, Bernardo Cuenca Grau, Boris Motik, and Ian Horrocks. Repairing Ontologies for Incomplete Reasoners. In Proceedings of the 10th International Semantic Web Conference, Bonn, Germany, pages 681–696, 2011. 20. Despoina Trivela, Giorgos Stoilos, Alexandros Chortaras, and Giorgos Stamou. Optimising Resolution-Based Rewriting Algorithms for OWL Ontologies. Journal of Web Semantics, 33:30–49, 2015. 21. Despoina Trivela, Giorgos Stoilos, and Vasilis Vassalos. A Framework and Positive Results for IAR-answering. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, New Orleans, Louisiana, USA, February 2-7, 2018, 2018. 22. Eleni Tsalapati, Giorgos Stoilos, Giorgos B. Stamou, and George Koletsos. Efficient Query Answering over Expressive Inconsistent Description Logics. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, pages 1279–1285, 2016.