Querying expressive DL Ontologies under the ICAR semantics

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 satis ed for a given input ontology and query.

Introduction

Query answering over ontologies expressed in Description Logics (DL) has recieved signi cant 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 rst remove the con icting 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 modi cations.

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 semantics [ 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 inconsistencytolerant semantics has been proved quite di cult for DLs more expressive than DL-Lite. More precisely, Rosati [ 18 ] showed that the problem of IAR and ICARanswering is at least coNP-hard w.r.t. data complexity for almost all well-known DLs from E L? to SHIQ. Moreover, in the E L?nr fragment of E L? 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 computes 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 ICARanswering 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 semiacyclic-E L? [ 5 ], as well as UCQ-rewritable queries over ontologies expressed in E L?nr. For DLs and queries for which the termination conditions are not generally satis ed, we exploit previous works [ 6, 8, 11 ] and provide an approach to check termination over a xed 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 nite set of assertions of the form A(a) or R(a; b) where a; b 2 I. A TBox T is a set of DL axioms. An E L? concept is inductively de ned by the syntax: C := > j ? j A j C1 u C2 j 9R:C, where A 2 C and R 2 R and C(i) are E L? concepts. An E L? TBox T is a nite set of inclusions of the form C1 v C2 with C1; C2 E L? 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 E L? by allowing concepts of the form A, and 9R:>; R in DLLite 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 E L? and DL-Lite axioms to rst order clauses (inverse roles have been omitted). In the following we assume that the TBox axioms are translated into FOL. Datalog and Conjunctive Queries A disjunctive datalog clause r (also called rule) is a function-free clause of the form 8~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 quanti ers 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 nite 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 i all minimal models of P contain D(~a); a negative ground atom :D(~a) is entailed by P i 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 nite 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 j= 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.

De nition 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 j= Q(~a) i R [ A j= Q(~a), or in case Q is boolean T [ A j= Q i R [ A j= 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 .

Note that we will refer to a clause of the form H(~s) Vi i ^ Vj :Bj , where i are positive atoms and Bj are conjunctions of positive atoms, as a datalog clause. Indeed such a clause is equisatis able to a datalog program that inlcudes H(~s) Vi i ^ Vj : j and j Bj , for all j, where j are positive atoms. Inconsistency-tolerant Semantics De nitions 2 and 3 recapitulate some of the notions used in the IAR and ICAR semantics [ 15 ]. De ntion 4 formalises the notion of the rewriting under the IAR and ICAR semantics.

De nition 2. Consider a TBox T and ABox A we de ne the consistent logical consequences of T ; A as the set clc(T ; A) = fa j some S A exists s.t. T [S j= a and S is consistent w.r.t. T g, where we use a to denote an assertion. De nition 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 IARanswer of Q over K if ~a 2 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 j=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 ICARanswer of Q over K if ~a 2 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 j=icar Q(~a).

De nition 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 j=ir Q(~a) i Rir [ A j= Q(~a). Similarly, for an ICAR-rewriting Ricr we have T [ A j=icr Q(~a) i Ricr [ A j= Q(~a). 3

Towards an ICAR-answering algorithm

The problem of answering queries under the ICAR semantics was rst investigated 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 = fC(x) A(x); ? A(x) ^ B(x)g, Q the query Q = Q(x) C(x) and A the ABox A = fA(a); B(a)g. A has two repairs, that is fA(a)g and fB(a)g, and hence Air = ;. It is not hard to verify that clc(T ; A) = fC(a); A(a); B(a)g. Moreover, clc(T ; A) has two repairs, that is fA(a); C(a)g and fB(a); C(a)g and hence Aicar = fC(a)g. Therefore, cert(Q; T [ Aicar) = fag and by de nition of the ICAR-answers it holds that certicar(Q; T [ A) = f g

a .

In the rst step, the algorithm in [ 15 ] computes the rewriting R of Q; T under the standard semantics, R = fQ(x) C(x); Q(x) A(x)g. Then, it extends the queries in R with the appropriate negative atoms, R0 = fQ(x) C(x); Q(x) A(x) ^ :B(x)g. 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 [ fQ(x) A(x)g that captures the assertions in clc(T ; A). When Q(x) A(x) of R00 is evaluated over A we obtain the ICAR-answer fag, 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) and the ABox A = fA(a); B(a)g.

C(x) T = f C(x)

K(x)

A(x) ^ K(x)

B(x) ?

A(x) ^ B(x)g It is not hard to verify that clc(T ; A) = fA(a); B(a); K(a)g and that Aicar = fK(a)g. Hence, certicar(Q; T [ A) = ;.

By applying the technique of [ 22 ] we rst compute the saturation of A, As = fC(a); A(a); B(a); K(a)g and the IAR-rewriting, Rir = fQ(x) C(x); Q(x) A(x) ^ K(x) ^ :B(x); Q(x) A(x) ^ B(x) ^ :B(x)g. When we evaluate Q(x) C(x) of Rir over As we yield fag 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 ICARanswering 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 rst step, we compute the IAR-rewriting of Q; T . For this purpose, we apply the IARrewriting algorithm presented in [ 21 ] that takes as input an arbitary DL TBox.

Rir = f Q(x)

C(x) Q(x) Q(x)

A(x) ^ K(x) ^ :(A(x) ^ B(x)) A(x) ^ B(x) ^ :(A(x) ^ B(x))g (1) (2) Finally, we construct the set R0 = Rir [ f(4); (5)g.

Notice that when Q(x) A(x) ^ B(x) of R0 is evaluated over A we obtain Q(a), but fag is not in certicar(Q; T ; A); hence R0 is not an ICAR-rewriting.

In order to x 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 j= ? A(x) ^ B(x), any set of the form fA(a); B(a)g 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 fA(a); B(a)g 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 6j= ? A(x)^K(x). By eliminating (5) from R0 we obtain the ICAR-rewriting Ricr = Rir [ f(4)g. } Example 4. Consider the following TBox T , query Q(x) A = fR(a; b); K(b); R(b; a)g.

A(x) and ABox 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)): (4) (5) (6) (7) (8) (9) (10) T = f A(x)

A(x)

R(x; y) ^ K(y)

R(x; y) ^ A(y) ?

K(x) ^ R(x; y)g We rst compute the IAR-rewriting of Q w.r.t. T by applying the calculus of [ 21 ]:

Rir = f Q(x)

A(x) A(x) A(x)

R(x; y) ^ A(y) ^ :(R(x; y) ^ K(x))g R(x; y) ^ K(y) ^ :(R(x; y) ^ K(x)) ^ :(R(y; z) ^ K(y))(11) (12) Next, we apply a rewriting procedure on the elements of Rir: In line with the Example 4 notice that for the clauses (7),(8) in R0 it holds that T 6j= ? R(x; y) ^ K(y), T 6j= ? R(x; y) ^ A(y). However, R0 = Rir [ f(7); (8)g 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 ICARanswer since A(b) 2= clc(T ; A). This is because to derive A(b) we have used fR(a; b); K(b); R(b; a)g 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 su cient to examine if T 6j= ? R(x; y) ^ A(y); since the concept A participates in a recursion, there is an in nite 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 ICARrewriting over a TBox expressed in an arbitary DL. De nition 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 nite 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.

De nition 5. A negative closure of a TBox T , denoted by Tcn, is a nite set of negative clauses such that T j= ? V i i some ? V i in Tcn exists with ? V i j= ? V 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 4: for H(~s) Vi i ^ Vj : j 2 Rir do 5: Compute a UCQ-rewriting R of Q(~s) 6: for each Q(~s) Vi i0 2 R do 7: if for every clause C 2 Tcn it holds C 6j= ? 8: Ricr = Ricr [ fH(~s) Vi 0i ^ Vj : jg 9: end if 10: end for 11: end for 12: return Ricr Vi i w.r.t. T

Vi 0i then

Algorithm 1 computes the IAR-rewriting Rir (line (2)) by applying the procedure 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 precisely, for the positive body atoms i of every element in Rir, it constructs the UCQ-rewriting of the query Q(~s) Vi 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) In the rst step, Algorithm 1 computes the IAR-rewriting of Q: Next, by considering the clauses (16), (17), (18) in Rir it computes the UCQrewriting of Q(x) A(x), Q(x) R(x; y) ^ B(y), Q(x) R(x; y) ^ C(y): (16) (17)

Q(x) Q(x) A(x)

R(x; y) ^ B(y) R(x; y) ^ C(y)

R(x; y) ^ C(y) ^ :(B(y) ^ K(y)) The negative closure of T is Tcn = f? B(x) ^ K(x); ? C(x) ^ K(x)g. 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 satis ed. Finally, Algorithm 1 outputs Ricr = Rir [ f(19); (20); (21)g 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 rst show that Ricr [ A j= Q(~a) i Rir [ clc(A) j= Q(~a). By de nition of Rir it holds that Rir [ clc(A) j= Q(~a) i R [ clc(A) j=ir Q(~a). Finally, by de nition of Aicar we conclude that Ricr [ A j= Q(~a) i R [ A j=icr Q(~a). (13) (14) (15) (16) (17) (18) (19) (20) (21) tu 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 exists a negative closure for a semi-acyclic-EL? TBox. Theorem 2 follows. Theorem 2. Let T be a semi-acyclic-E L? TBox and let Q be an instance query. Then, on input T and Q, Algorithm 1 terminates and computes an ICARrewriting of Q w.r.t. T .

In [ 18 ] the E L?nr fragment of E L? was studied and in [ 21 ] it was shown that there always exists a negative closure of an E L?nr TBox. Therefore, although the problem of ICAR-answering of CQs over E L?nr TBoxes is in general intractable, for a given UCQ-rewritable CQ we obtain the following result.

Theorem 3. Let T be a E L?nr TBox and let Q be a CQ that is UCQ-rewritable. Then, on input T and Q Algorithm 1 terminates and computes an ICARrewriting of Q w.r.t. T .

To check if a given query is UCQ-rewritable we can exploit results in UCQrewritability 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 HornDLs, like E L?, E LI? and Horn-SHIF . These results were used to design a practical algorithm for checking UCQ-rewritability of instance queries [ 11 ]. Subsequently, 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 = fAi(x) j ? A1(x) ^ : : : ^ Am(x) 2 T g. 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 UCQrewritability 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 satis ed, 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 evaluation of the proposed framework. Our system is based on the implementation of Algorithm 1. At rst step, the UCQ-rewritability of the input query Q is examined 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 in computing the ICAR-rewriting Ricr as described in lines 3-10. The whole system 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 di erent levels in the concepts hierarchy, so that these a ect 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 UCQrewritable. 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 j= A v B and T j= 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, jRirj 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 ICARrewriting was obtained within a few seconds. In contrast, in the case of NotGalen 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 = fA(x) A1(x); ? A(x) ^ B(x)g and query Q = Q(x) A(x) ^ C(x) the IAR-rewriting is of the form Rir = fQ(x) A(x) ^ C(x) ^ :(A(x) ^ B(x)) ^ :(A1(x) ^ B(x)); Q(x) A1(x) ^ C(x) ^ :(A1(x) ^ B(x))g and to obtain Rir the standard rewriting R = fQ(x) A(x) ^ C(x); Q(x) A1(x) ^ C(x)g 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 triplestore 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 e ciently 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 semiacyclic-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 Zakharyaschev . The DL-Lite Family and Relations . Journal of Arti cial Intelligence Research , 36 :1{ 69 , 2009 .

2. Franz Baader , Deborah L. McGuinness , Daniele Nardi , and Peter F. PatelSchneider. The Description Logic Handbook: Theory, implementation and applications . Cambridge University Press, 2002 .

3. Meghyn Bienvenu , Camille Bourgaux, and Francois Goasdoue . Querying Inconsistent 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 OrderRewritability and Containment of Conjunctive Queries in Horn Description Logics . In IJCAI: International Joint Conference on Arti cial 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 Arti cial Intelligence , 2013 .

7. Meghyn Bienvenu and Riccardo Rosati . New Inconsistency-Tolerant Semantics for Robust Ontology-Based Data Access . In Proceedings of the Twenty-Sixth International Workshop on Description Logics , 2013 .

8. Meghyn Bienvenu , Balder ten Cate, Carsten Lutz, and Frank Wolter. OntologyBased 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 E cient Query Answering in Description 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, Inanc Seylan, and Frank Wolter . E cient Query Rewriting in the Description Logic EL and Beyond . In Proceedings of the TwentyFourth International Joint Conference on Arti cial 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 Ognyano , 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. Hector Perez-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 Description Logic Ontologies . In Proceedings of the Twenty-Second International Joint Conference on Arti cial 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 Arti cial Intelligence , New Orleans, Louisiana, USA, February 2- 7 , 2018 , 2018 .

22. Eleni Tsalapati , Giorgos Stoilos, Giorgos B. Stamou , and George Koletsos . E cient Query Answering over Expressive Inconsistent Description Logics . In Proceedings of the Twenty-Fifth International Joint Conference on Arti cial Intelligence , pages 1279 { 1285 , 2016 .