Repairing Incomplete Reasoners Giorgos Stoilos and Bernardo Cuenca Grau Oxford University Computing Laboratory Wolfson Building, Parks Road, OX1 3QD, Oxford Abstract. The pressing need for scalable query answering has moti- vated the development of many incomplete ontology-based reasoners. Improving the completeness of such systems without sacrificing their favourable performance would be beneficial to many applications. In this paper, we address the following problem: given a query q, a TBox T and an incomplete reasoner ans (i.e., one that accepts q and T as valid inputs but fails to return all query answers to q w.r.t. T and some dataset), we aim at computing a (hopefully small) TBox R (a repair ) which logically follows from T and such that ans is provably complete w.r.t. q and T ∪ R, regardless of the input data. We identify conditions on q, T and ans that are sufficient to ensure the existence of such repair and present a practi- cal repair generation algorithm. Our experiments suggest that repairs of small size can be computed for well-known ontologies and reasoners. 1 Introduction In Semantic Web applications, a description logic TBox is frequently used for describing the meaning of data stored in various sources. A query language (based on conjunctive queries) is then used for data access [13]. Unfortunately, when using an expressive ontology language, computing query answers can be costly, and in a Semantic Web setting, datasets may be extremely large. Motivated by the need for scalable query answering, there has been a growing interest in the development of incomplete ontology-based reasoning systems, which are not guaranteed to compute all query answers for some combinations of queries, TBoxes and datasets accepted as valid inputs. Many such systems (e.g., Jena, OWLim, and Oracle’s Semantic Store) are based on rule technologies; others are based on approximate reasoning techniques [7, 11, 1]. Incomplete query answers, however, may not be acceptable in some cases, and even if some incompleteness is acceptable, computing as many answers as possi- ble without affecting performance would be beneficial to many applications. Not surprisingly, many techniques for improving the completeness of (incomplete) reasoning systems have been proposed in recent years. A widely use approach relies on the materialisation of certain kinds of TBox consequences, prior to accessing the data. TBox materialisation is indeed a convenient and low-cost solution, as it does not rely on modifying the internals of the reasoning sys- tem at hand: it can either be included by reasoning systems’ implementors as a pre-processing step (e.g., DLEJena [3], PelletDB, TrOWL [11], Minerva [10] and DLDB [6]), or it can be performed by application designers, who have little knowledge of and/or control over the reasoner. This approach, however, exhibits several limitations: 1. TBox materialisation is done blindfold, without taking into account neither the capabilities of the incomplete reasoner under consideration, nor the pre- cise sources of its incompleteness for the application at hand. 2. In order to avoid a blowup in the size of the TBox, materialisation involves only simple atomic subsumption relations, and relevant entailments describ- ing more complex dependencies are typically ignored. 3. It is often difficult, or even infeasible, to estimate the extent to which mate- rialisation has improved the system’s completeness for the given application at hand, especially if the data is very large, unknown, or frequently changing. In this paper, we present a novel approach to TBox materialisation that attempts to address many of these limitations. Given a TBox T expressed in a language L, a conjunctive query (CQ) q, and a reasoning system ans satisfying certain properties known in advance (e.g., soundness), we aim at computing a (hopefully small) set of TBox axioms R, called a (q, T )-repair for ans, such that R logically follows from T and the system is guaranteed to compute all answers to q w.r.t. T ∪ R (and hence also w.r.t. T ), regardless of the input data. Our TBox materialisation techniques are “guided” by both the input query and TBox and the capabilities of the reasoner at hand, thus limiting the number of materialised consequences. Furthermore, our approach provides a provable completeness guarantee: after extending T with a (q, T )-repair, the incomplete reasoner at hand is indistinguishable from a complete one w.r.t. q and T , and regardless of the data (which is often unknown or frequently changing). Finally, if a (q, T )-repair does not exist for the given reasoner, we also provide means for quantifying the extent to which the reasoner’s completeness improved upon materialisation of a given set of TBox consequences. Our main contributions can be summarised as follows: – We formalise the notion of a repair for a given CQ, TBox and reasoner. – We identify sufficient conditions for the existence of a repair. Our conditions establish a bridge between the framework of completeness evaluation [16, 15] and the notion of interpolation in the context of DLs [8, 14, 9]. – We then present a practical algorithm that is guaranteed to compute a repair under certain assumptions. Our algorithm extends well-known query rewrit- ing techniques for DLs [12, 2] with means for computing suitable interpolants for each query in the rewriting. – Although the assumptions required by our algorithm may seem somewhat strict, we provide empirical evidence that repairs can be computed for well- known ontologies and incomplete reasoners. Furthermore, the size of such repairs is surprisingly small and preliminary evaluation has shown that their impact on performance is negligible. Finally, for reasoner which are complete only for a very weak description logic, we show that our techniques can provide “partial repairs”, whose impact can be quantified. 2 Although our main focus is on repairing rule-based reasoners, we feel that our techniques are also highly relevant to recent DL approximation frameworks [11, 1], and provide new insights into the process of approximation. Proofs for all lemmas and theorems can be found online.1 2 Preliminaries We use DLs that do not allow for nominals and we also assume that only atomic assertions are allowed in ABoxes. Let C, R, and I be countable, pairwise disjoint sets of atomic concepts, atomic roles, and individuals. An ELHI-role is either an atomic role P or its inverse P − . The set of ELHI-concepts is defined inductively by the following grammar, where A ∈ C, R is an ELHI-role, and C(i) are ELHI-concepts: C := ⊤ | ⊥ | A | C1 ⊓ C2 | ∃R.C An ELHI-TBox T is a finite set of GCIs C1 ⊑ C2 with Ci ELHI-concepts and RIAs R1 ⊑ R2 with Ri ELHI-roles. An ABox A is a finite set of assertions A(a) or P (a, b), for A ∈ C, P ∈ R, and a, b ∈ I. An ELHI-ontology O = T ∪ A consists of an ELHI-TBox T and an ABox A. Moreover, the DLP fragment of ELHI [5] (DLP-ELHI) is obtained from ELHI by disallowing concepts of the form ∃R.C on the right-hand side of GCIs. A conjunctive query (CQ) q is an expression of the form q(x1 , . . . , xn ) ← α1 , . . . , αm where each αi is a concept or role atom of the form A(t) or R(t, t0 ) (for t, t0 function-free terms and A, R atomic) and each xj is a distinguished variable occurring in some αi . The remaining variables are called undistinguished. We use the standard notion of a certain answer to q w.r.t. O = T ∪ A, and we denote with cert(q, O) the set of all certain answers to q w.r.t. O. Given q1 , q2 with the same distinguished variables ~x we say that q1 subsumes q2 w.r.t. T , written q2 ⊑T q1 , if the FO-entailment T |= ∀~x.(Bq2 → Bq1 ) holds, with Bqi the formula obtained from the conjunction of all body atoms in qi by existentially quantifying over all undistinguished variables. Finally, a UCQ rewriting u for a CQ q and TBox T is a union of conjunctive queries (a set of CQs with the same distinguished variables) that satisfies the following properties for each ABox A such that O = T∪∪ A is consistent [2]: cert(q 0 , A) ⊆ cert(q, O) for each q 0 ∈ u, and cert(q, O) ⊆ q0 ∈u cert(q 0 , A). 3 Completeness Repairs We start by recalling from [16, 15] the notions of a CQ answering algorithm, and of completeness for a query q and TBox T . 1 https://rapidshare.com/files/460900188/main.pdf 3 Definition 1. A CQ answering algorithm ans for a DL L is a procedure that, for each L-ontology O and CQ q computes in a finite number of steps a set ans(q, O) of tuples of constants. It is sound if ans(q, O) ⊆ cert(q, O) for each O and q. It is complete if cert(q, O) ⊆ ans(q, O) for each O and q. It is monotonic if ans(q, O) ⊆ ans(q, O0 ) for each O, O0 and q with O ⊆ O0 . It is invariant under renamings if, for each q, O = T ∪ A, O0 = T ∪ A0 and isomorphism ν between A and A0 we have ~a ∈ ans(q, O) if and only if ν(~a) ∈ ans(q, O0 ). It is well-behaved if it is sound, monotonic and invariant under renamings. We denote with C L the class of all well-behaved CQ answering algorithms for L. Finally, we say that ans is (q, T )-complete for a query q and TBox T if for each ABox A s.t. O = T ∪ A is consistent, we have that cert(q, O) ⊆ ans(q, O). This general definition allow us to abstract from the specifics of implemented systems. All incomplete reasoning algorithms known to us are well-behaved: they are sound, query answers can only grow if we add axioms to the ontology, and they do not depend on trivial renamings of ABox individuals. Furthermore, a (q, T )-complete algorithm, even if incomplete in general, behaves exactly like a complete one w.r.t. the given query q and TBox T , regardless of the data. Consider, as a running example, the following ELHI-TBox T0 and query q0 : T0 = {∃takes.Course ⊑ Student, GradCo ⊑ Course, GradSt ⊑ ∃takes.GradCo, PhDSt ⊑ GradSt, Student ⊓ Course ⊑ ⊥} q0 (x) ← Student(x) Consider an algorithm ans0 that first translates DLP-ELHI GCIs in T0 into a datalog program using standard transformations (and discarding the remaining GCIs), then saturates the input ABox w.r.t. the program, and finally answers q0 w.r.t. the saturated ABox. Clearly, ans0 is not (q0 , T0 )-complete: it returns the empty set for A = {GradSt(a)}, whereas cert(q0 , T0 ∪ A) = {a}. Computing the missing answer requires axiom GradSt ⊑ ∃takes.GradCo, which is discarded. Note, however, that one could dispense with the discarded axiom and still recover the missing answer by extending T0 with the following DLP-ELHI TBox R0 : R0 = {GradSt ⊑ Student} (1) Since T0 |= R0 , extending T0 with R0 does not change the meaning of T0 . The behaviour of ans0 w.r.t. T0 ∪R0 , however, is now different because ans0 translates R0 into a datalog clause and hence ans0 (q0 , T0 ∪ R0 ∪ A) = {a}. Note also that adding R0 allows us to recover missing answers w.r.t. many other ABoxes different from A. For example, given A0 = {PhDSt(b)} and T0 ∪A0 , we have that b is a certain answer to q0 that is computed by ans0 only after extending T0 with R0 . Our example suggests that given q, T and an algorithm ans that is incomplete for q and T , it may be possible to recover all missing answers to q (w.r.t. all possible ABoxes) by “repairing” T for ans—that is, by materialising a (hopefully small) number of T -consequences that ans can process. 4 Definition 2. Let L be a DL, q a CQ, T an L-TBox, A an ABox, and ans a CQ answering algorithm for L. A (q, T , A)-repair R for ans is an L-TBox such that 1. T |= R; and 2. cert(q, T ∪ A) ⊆ ans(q, T ∪ R ∪ A). Given a set A of ABoxes, we say that R is a (q, T , A)-repair for ans if it is a (q, T , A)-repair for ans for each A ∈ A. Finally, we say that R is a (q, T )-repair for ans if it is a (q, T , A)-repair for ans for every ABox A s.t. T ∪A is consistent. Unfortunately, deciding, on the one hand, whether ans is (q, T )-complete and, on the other hand, whether R is a (q, T )-repair for ans may involve computing query answers w.r.t. an unlimited number of ABoxes. In [16, 15], however, it was shown that under certain conditions on q and T it is possible to decide (q, T )- completeness by computing query answers only w.r.t. a finite (and hopefully small) number of ABoxes. Such finite set of ABoxes is called a testing base. Definition 3. Let L be a description logic, let C be a class of CQ answering algorithms for L, let T be an L-TBox, and let q be a CQ. A (q, T )-testing base B for C is a finite set of ABoxes A such that the following property holds for each algorithm ans in C: if cert(q, T ∪ A) ⊆ ans(q, T ∪ A) for each A ∈ B, then cert(q, T ∪ A0 ) ⊆ ans(q, T ∪ A0 ) for each ABox A0 consistent with T . In our previous work [16, 15] we have shown how to compute a (q, T )-testing base (if one exists) for the class C L of well-behaved algorithms. Consider our running example. The set of ABoxes B0 = {A1 , . . . , A5 } defined as follows is a (q0 , T0 )-testing base for the class of all well-behaved algorithms: A1 = {Student(a)}, A2 = {takes(a, b), Course(b)}, A3 = {GradSt(a)}, A4 = {takes(a, b), GradCo(b)}, A5 = {PhDSt(a)} Intuitively, in order to compute a (q, T )-repair, we only need to consider the (finitely many) ABoxes in a (q, T )-testing base instead of all (infinitely many) possible ABoxes. Theorem 1. Let L be a DL, q a CQ, T an L-TBox, and B a (q, T )-testing base for C L . The following property holds for each ans ∈ C L : If R is a (q, T , B)-repair for ans, then R is also a (q, T )-repair for ans. In our running example, clearly, ans0 only fails to compute certain answers w.r.t. A3 and A5 . Furthermore, R0 is a (q0 , T0 , B0 )-repair for ans0 . But then, Theorem 1 ensures that R0 is also a (q0 , T0 )-repair. Thus, by simply adding R0 to T0 , we can guarantee that ans0 will compute all certain answers, regardless of the data. 4 Computing Repairs Theorem 1 provides a sufficient condition for the existence of a (q, T )-repair for a well-behaved algorithm ans. To apply the theorem, however, we first need to compute a (q, T )-testing base B and then a (q, T , B)-repair R for ans. 5 As shown in [15, 16], a (q, T )-testing base B for C L can always be computed from a UCQ rewriting u for q and T . UCQ rewritings are guaranteed to exist if T is expressed in the DL underpinning the OWL 2 QL profile and they may also exist even if T is expressed in the DLs underpinning the OWL 2 EL profile; this is often the case in many real-world ontologies. Hence, in this paper we will restrict ourselves to TBoxes and queries for which a UCQ rewriting exists.2 Given a (q, T )-testing base B, however, the existence of a (q, T , B)-repair may also depend on the capabilities of the algorithm under consideration. For instance, in the case of our running example, no (q0 , T0 , B0 )-repair exists for an algorithm that ignores the TBox and simply matches the query to the data (even though such algorithm is well-behaved). Our techniques for computing repairs rely on a particular form of interpo- lation [8, 14]. We next make the connection between repairs and interpolation precise, and describe an algorithm for computing interpolants. 4.1 Completeness Repairs and Interpolation As already discussed, algorithm ans0 from our running example misses answers w.r.t. A3 , A5 ∈ B0 , and R0 from (1) is a (q0 , T0 , B0 )-repair for ans0 . Furthermore, B0 can be obtained by “instantiating” queries from the following UCQ rewriting u = {q1 , . . . , q5 } for q0 and T0 : q1 (x) ← Student(x), q2 (x) ← takes(x, y), Course(y), q3 (x) ← GradSt(x), q4 (x) ← takes(x, y), GradCo(y), q5 (x) ← PhDSt(x) In particular, A3 = {GradSt(a)} is obtained by instantiating q3 . We then say that q3 is “relevant” to ans0 . Formal definitions of instantiation and relevance are given next. Definition 4. Let q be a CQ, Bq the body atoms in q, and π a mapping from all variables of q to individuals. The following ABox is an instantiation of q: Aqπ := {A(π(x)) | A(x) ∈ Bq } ∪ {R(π(x), π(y)) | R(x, y) ∈ Bq } Definition 5. Let u be a UCQ rewriting for q and an L-TBox T , let ans be well- behaved and let B be a (q, T )-testing base. We say that qi ∈ u is relevant to ans if an instantiation Ai of qi exists s.t. Ai ∈ B and cert(q, T ∪ Ai ) 6⊆ ans(q, T ∪ Ai ). Note also that q3 is subsumed by q0 w.r.t. T0 . We can then identify R0 as an interpolant for the subsumption q3 ⊑T0 q0 since T0 |= R0 , q3 ⊑R0 q0 and R0 only mentions symbols occurring in either q0 or q3 . Definition 6. Let T be an L-TBox and let q, q 0 be CQs such that q 0 ⊑T q. A TBox = expressed in fragment L0 of L and using only symbols occurring in q or q 0 is an L0 -interpolant for q 0 ⊑T q if T |= = and q 0 ⊑= q. 2 The notion of a testing base can be extended, and such (extended) testing bases can be computed from Datalog rewritings. The study of such extensions is ongoing work. 6 The following theorem establishes which are the relevant interpolants for com- puting a repair. Furthermore, if each such interpolants can be expressed in a weak enough language, for which ans is provably complete, we can easily obtain a repair from the union of such interpolants. Theorem 2. Let u be a UCQ rewriting for q and an L-TBox T . Let ans ∈ C L be an algorithm that is complete for a fragment L0 of L. Let q1 , . . . , qn be those 0 ∪ for each 1 ≤ i ≤ n let =i be an L - queries in u relevant to ans. Finally, interpolant for qi ⊑T q. Then, = = 1≤i≤n =i is a (q, T )-repair for ans. 4.2 Computing Interpolants Assumptions First, we restrict ourselves to TBoxes expressed in ELHI. Sys- tems such as REQUIEM can compute a UCQ rewriting w.r.t. an ELHI-TBox, provided that one exists [12]. Second, we observe that most state-of-the-art incomplete systems are based on deductive database and rule technologies. Given O = T ∪ A and q as input, the ABox A is deterministically saturated with new assertions using axioms in T , and then q is answered directly w.r.t. the saturated ABox. Furthermore existing systems rarely extend the input ABox with “fresh” individuals and hence cannot handle existential quantification on the right-hand-side of TBox axioms. In fact, many such systems are complete for DLs of the DLP family. Thus, we will consider DLP-ELHI as our target language for computing interpolants. In this setting, we also need to restrict the kinds of queries we are considering to guarantee the existence of the relevant interpolants. It is rather straightfor- ward to find ELHI-TBoxes and queries q for which a UCQ rewriting does exist, but the DLP-ELHI interpolants required by Theorem 2 do not. For example, let T = {A ⊑ ∃R.C} and consider the following queries q(x) ← R(x, y), C(y) q 0 (x) ← A(x) Clearly, {q, q 0 } is a UCQ rewriting for q and T . There is, however, no DLP-ELHI interpolant for q 0 ⊑T q since such interpolant would need to contain existential quantification on the right-hand-side of GCIs. Consequently, from now onwards we focus on queries with only distinguished variables. This restriction is not unreasonable in practice since the standard language for querying ontologies on the Web (SPARQL) treats undistinguished variables as if they were distinguished [4]. The Algorithm Algorithm 1 computes a UCQ rewriting u (if one exists) for an ELHI-TBox T and a query q with no undistinguished variables. Furthermore, for each q 0 ∈ u, it computes a DLP-ELHI interpolant for q 0 ⊑T q. Our algorithm extends the rewriting algorithm implemented in the RE- QUIEM system [12], which first transforms T and q into a set of clauses (Lines 1, 2 in Algorithm 1) and then uses a resolution calculus to compute u. 7 Algorithm 1 Extended Resolution-based algorithm Algorithm: extendedUCQRewriting(q, T ) Input: T ∈ ELHI and q with no undistinguished vars. 1: T := clausify(T ) 2: q := clausify(q) 3: σ(q) := ∅ 4: for all α ∈ T do σ(α) := {α} 5: u := T ∪ {q} 6: repeat 7: Pick clauses C1 , C2 from u with C1 6= C2 8: C := resolve(C1 , C2 ) 9: u := u ∪ {C} 10: RC := σ(C1 ) ∪ σ(C2 ) 11: repeat 12: Pick clauses D1 , D2 from RC with D1 6= D2 13: RC := RC ∪ {resolve(D1 , D2 )} 14: until RC is saturated 15: σ(C) := prune(RC ) 16: until u is saturated 17: (u, σ) := ff(u, σ) 18: (u, σ) := unfold(u, σ) 19: if u is not a UCQ, return failure 20: return (u, σ) Interpolants are tracked down during resolution by means of a mapping σ from clauses to sets of clauses. Initially, σ maps q to the empty set (since q ⊑∅ q), and each clause from T to itself (Lines 3, 4). The rules in the resolution-based calculus from [12] are exhaustively applied in Lines 6–16, and new clauses are generated in Lines 7–9 exactly as in [12]. Then, for each new clause C produced as a resolvent of C1 and C2 our algorithm computes its corresponding interpolant σ(C). This is done by first saturating σ(C1 ) ∪ σ(C2 ) (Lines 11–14) and then removing all clauses mentioning a symbol that is neither in C nor in q (Line 15). After u is saturated, the algorithm removes all clauses that contain function symbols (Line 16). Then, at this point, both rewriting and interpolants are given as sets of function-free clauses, so the procedure unfold transforms each C ∈ u into a datalog rule and “rolls-up” σ(C) into a DLP-ELHI GCI. Finally, the algorithm rejects the input if u is not a UCQ (e.g., a datalog program) and returns both the UCQ rewriting and the interpolant for each query otherwise. Lemma 1. If u computed by Algorithm 1 is a UCQ, then u is a UCQ rewriting for q and T . Furthermore, for each q 0 ∈ u, σ(q 0 ) is a DLP-ELHI interpolant for q 0 ⊑T q. Algorithm 2 computes a repair by considering only those queries and ABoxes for which ans fails. Correctness follows from Theorem 2 and Lemma 1. Theorem 3. Algorithm 2 computes a (q, T )-repair for an algorithm ans that is complete for DLP-ELHI. 8 Algorithm 2 Computing a Repair Algorithm: computeRepair(ans, q, T ) Input: T , q as in Algorithm 1, ans well-behaved. 1: (u, σ) := extendedUCQRewriting(q, T ) 2: B := computeTestingBase(u) 3: Repair := ∅ 4: for all A ∈ B do 5: if cert(q, T ∪ A) 6⊆ ans(q, T ∪ A) then 6: q 0 := query in u that generated A 7: Repair := Repair ∪ σ(q 0 ) 8: end if 9: end for 10: return Repair If ans is not complete for DLP-ELHI (e.g., if it is an RDFS-reasoner), then the TBox R computed by Algorithm 2 may not be a repair; however, adding R may still have the desired effect of “mitigating” the reasoner’s incompleteness. 5 Evaluation We have developed a prototype tool based on Algorithms 1 and 2. Our imple- mentation uses REQUIEM [12] and the system described in [16, 15] for comput- ing (q, T )-testing bases and relevant queries. Additionally, our tool implements optimisations to eliminate redundancy in the computed repairs. We have evaluated our techniques first using LUBM’s TBox and its 14 test queries (all of which contain only distinguished variables) and then a version of the GALEN TBox together with 4 sample queries for which a UCQ rewrit- ing can be computed using REQUIEM. In each case, we have evaluated the following systems: Sesame 2.3-prl,3 OWLim,4 Jena v2.6.35 and DLEJena.6 Our experiments consisted of the following steps: 1. For each TBox T and test query q we computed a (q, T )-testing base and measured the proportion of certain answers that each system is able to com- pute w.r.t. the ABoxes in the (q, T )-testing base (δini ) [16]. 2. For each system and each q for which it was found incomplete (i.e., δini < 1), we computed a repair R (which might be only “partial” for some systems). 3. For each case in Step 2 we have extended T with the corresponding R, computed a (q, T ∪ R)-testing base and obtained a new completeness degree value δf in . 4. To evaluate the effects that adding TBox axioms had on systems’ perfor- mance in the LUBM scenario, we used the LUBM performance evaluation 3 http://www.openrdf.org/ 4 http://www.ontotext.com/owlim/ 5 http://jena.sourceforge.net/ 6 http://lpis.csd.auth.gr/systems/DLEJena/ 9 LUBM Sesame OWLim/Jena Q2 Q4 Q5 Q6 Q7 Q8 Q9 Q10 Q12 Q13 Q6 Q8 Q10 ♯urel 1 4 4 166 34 27 1 166 2 4 1 4 1 ♯R 0 0 4 1 1 1 0 1 0 4 1 1 1 δini .75 .68 0 .003 .04 .04 0 .001 .25 .2 .99 .98 .99 δf in .75 .68 .75 .004 .05 .05 0 .002 .25 .2 1 1 1 GALEN OWLim Jena DLEJena Q1 Q2 Q3 Q4 Q1 Q2 Q3 Q4 Q1 Q2 Q3 Q4 ♯urel 36 72 72 12 24 48 48 6 36 72 72 6 ♯R 2 2 2 2 2 2 2 1 2 2 2 1 δini .84 .83 .84 .77 .94 .94 .94 .92 .84 .83 .84 .84 δf in 1 1 1 1 1 1 1 1 1 1 1 1 Table 1. Experiments for LUBM & GALEN tool [6] and measured the loading and query answering times using the orig- inal and the repaired TBox. Our results for LUBM are summarised in the upper part of Table 1, where ♯urel represents the number of relevant queries in the UCQ rewriting (see Definition 5), and ♯R the number of axioms in the computed repair. The only system not included in the table is DLEJena, which was already complete for all queries (w.r.t. the original TBox). OWLim and Jena were found incomplete for three queries and Sesame for 10 of them. As shown in the table, we were able to repair both OWLim and Jena for all queries. This was a reasonable result, since these systems are considered to be complete for DLP-ELHI. Furthermore, all repairs consisted of the same, unique axiom. In contrast, no query could be fully repaired for Sesame. A slight increase in the completeness degree can be observed in 4 queries and a more significant one only in Q5. Again, this is unsurprising, since Sesame is essentially an RDFS reasoner. No measurable performance changes were observed for any system after repair, which suggests that completeness can be improved (at least in this scenario) without affecting scalability. Finally, repairs were computed in times ranging between a second and 3 minutes. Results for GALEN are given in the lower part of the table. As shown in the table, we were able to fully repair OWLim, Jena and DLEJena, and repairs contained at most two axioms in each case (a relatively small number compared to the number of queries in urel ). All repairs could be computed in less than a minute. Finally, Sesame hasn’t been included in the table because no improve- ment could be measured for any query. 6 Conclusions In this paper, we have studied the problem of repairing an incomplete reasoning systems given a query and a TBox. An important feature of our repairs is that 10 they provide data independent completeness guarantees: once an incomplete sys- tem has been repaired, we can ensure that its output answers will be the same as those of a complete one for the given q and T , regardless of how large and complex the dataset is. Furthermore, our preliminary experiments suggest that repairs can indeed be very small and their effect on systems’ performance may even be negligible in some applications. Our results will allow application de- signers to use highly scalable reasoning systems in their application with the guarantee that they will behave as if they were complete, thus bringing together “the best of both worlds”. The extension of our techniques to more expressive DLs and a more extensive evaluation are ongoing work. Acknowledgments Research supported by project SEALS (FP7-ICT-238975). B. Cuenca Grau is supported by a Royal Society University Research Fellowship. References 1. Botoeva, E., Calvanese, D., Rodriguez-Muro, M.: Expressive approximations in DL-Lite ontologies. In: AIMSA. pp. 21–31 (2010) 2. Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M., Rosati, R.: Tractable reasoning and efficient query answering in description logics: The DL-Lite family. Journal of Automated Reasoning 39(3), 385–429 (2007) 3. G. Meditskos and N. Bassiliades: Combining a DL reasoner and a rule engine for improving entailment-based OWL reasoning. In: Proc. ISWC. pp. 277–292 (2008) 4. Glimm, B., Krötzsch, M.: SPARQL beyond subgraph matching. In: Proc. of ISWC 2010. pp. 241–256 (2010) 5. Grosof, B.N., Horrocks, I., Volz, R., Decker, S.: Description logic programs: Com- bining logic programs with description logic. In: Proc. of WWW. pp. 48–57 (2003) 6. Guo, Y., Pan, Z., Heflin, J.: LUBM: A Benchmark for OWL Knowledge Base Systems. Journal of Web Semantics 3(2), 158–182 (2005) 7. Hitzler, P., Vrandecic, D.: Resolution-based approximate reasoning for OWL DL. In: Proc. of ISWC 2005). pp. 383–397 (2005) 8. Konev, B., Walther, D., Wolter, F.: Forgetting and uniform interpolation in large- scale description logic terminologies. In: Proc. of IJCAI 09. pp. 830–835 (2009) 9. Lutz, C., Wolter, F.: Deciding inseparability and conservative extensions in the description logic EL. Journal of Symbolic Computation 45, 194–228 (2010) 10. Ma, L., Yang, Y., Qiu, Z., Xie, G.T., Pan, Y., Liu, S.: Towards a complete OWL ontology benchmark. In: Proc. of ESWC 2006. pp. 125–139 (2006) 11. Pan, J.Z., Thomas, E.: Approximating OWL-DL Ontologies. In: Proc. of AAAI-07. pp. 1434–1439 (2007) 12. Pérez-Urbina, H., Motik, B., Horrocks, I.: Tractable query answering and rewriting under description logic constraints. Journal of Applied Logic 8(2), 186–209 (2010) 13. Poggi, A., Lembo, D., Calvanese, D., Giacomo, G.D., Lenzerini, M., Rosati, R.: Linking data to ontologies. Journal of Data Semantics X, 133–173 (2008) 14. Seylan, I., Franconi, E., de Bruijn, J.: Effective query rewriting with ontologies over dboxes. In: Proc. of IJCAI 09. pp. 923–925 (2009) 15. Stoilos, G., Cuenca Grau, B., Horrocks, I.: Completeness guarantees for incomplete reasoners. In: Proc. of ISWC 2010. LNCS, Springer (2010) 16. Stoilos, G., Cuenca Grau, B., Horrocks, I.: How incomplete is your semantic web reasoner? In: Proc. of AAAI-10. pp. 1431–1436 (2010) 11