Brave and Cautious Reasoning in EL

Abstract

Developing and maintaining ontologies is an expensive and error-prone task. After an error is detected, users may have to wait for a long time before a corrected version of the ontology is available. In the meantime, one might still want to derive meaningful knowledge from the ontology, while avoiding the known errors. We introduce brave and cautious reasoning and show that it is hard for EL. We then propose methods for improving the reasoning times by precompiling information about the known errors and using proof-theoretic techniques for computing justi cations. A prototypical implementation shows that our approach is feasible for large ontologies used in practice.

Introduction

Description Logics (DLs) [ 3 ] have been successfully used to model many application domains, and they are the logical formalism underlying the standard ontology language for the semantic web OWL [ 30 ]. Consequently, more and larger ontologies are being built using these formalisms. Ontology engineering is expensive and error-prone; the combination of knowledge from multiple experts, and misunderstandings between them and the knowledge engineers may lead to errors that are hard to detect. For example, several iterations of SNOMED CT [ 13, 29 ] classi ed amputation of nger as a subclass of amputation of hand [ 7, 8 ].

Since domain knowledge is needed for correcting an unwanted consequence, and its causes might not be obvious, it can take long before a corrected version of an ontology is released. For example, new versions of SNOMED are released every six months; one should then expect to wait at least that amount of time before an error is resolved. During that time, users should still be able to derive meaningful consequences from the ontology, while avoiding known errors.

A related problem is inconsistency-tolerant reasoning, based on consistent query answering from databases [ 1, 9 ], where the goal is to obtain meaningful consequences from an inconsistent ontology O. Inconsistency is clearly an unwanted consequence from an ontology, but it is not the only one. We generalize the idea of inconsistency-tolerant reasoning to error-tolerant reasoning in which other unwanted consequences, beyond inconsistency, are considered.

We study brave and cautious semantics. Intuitively, cautious semantics refer to consequences that follow from all the possible repairs of O; this guarantees ? Partially supported by DFG within the Cluster of Excellence `cfAED'. that, however the ontology is repaired, the consequence will still follow. For some consequences, one might only be interested in guaranteeing that it follows from at least one repair; this de nes the brave semantics. As usual in inconsistencytolerant reasoning, the repairs are maximal subontologies of O that do not entail the unwanted consequence. We also consider the IAR semantics, proposed in [ 21 ] as a means to e ciently approximate cautious reasoning; see also [ 11, 28 ].

In this paper, we focus on subsumption between concepts w.r.t. a TBox in EL, which is known to be polynomial [ 12 ]. As every EL TBox is consistent, considering inconsistency-tolerant semantics makes no sense in this setting. On the other hand, SNOMED CT and other large-scale ontologies are written in tractable extensions of this logic, and being able to handle errors written in them is a relevant problem for knowledge representation and ontology development.

We show that error-tolerant reasoning in EL is hard. More precisely, brave semantics is NP-complete, and cautious and IAR semantics are coNP-complete. These results are similar to the complexity of inconsistency-tolerant semantics in inexpressive logics [ 10, 28 ]. We also show that hardness does not depend only on the number of repairs: there exist errors with polynomially many repairs, for which error-tolerant reasoning requires super-polynomial time (unless P = NP).

To improve the time needed for error-tolerant reasoning, we propose to precompute the information on the causes of the error. We rst annotate every axiom with the repairs to which it belongs. We then use a proof-theoretic approach, coupled with this annotated ontology, to derive error-tolerant consequences. We demonstrate the practical applicability of our approach for brave and cautious reasoning by applying a prototype-implementation on large ontologies used in practice. 2

Error-Tolerant Reasoning in EL We rst brie y recall the DL EL. Given two disjoint sets NC and NR of concept-, and role-names, respectively, concepts are constructed by C ::= A j C uC j 9r:C, where A 2 NC and r 2 NR. A TBox is a nite set of GCIs of the form C v D, where C; D are concepts. The TBox is in normal form if all its GCIs are of the form A v 9r:B, 9r:A v B, or A1 u : : : u An v B with n 1 and A; A1; : : : ; An; B 2 NC [ f>g. The semantics of EL is de ned through interpretations I = ( I ; I ), where I is a non-empty domain and I maps each A 2 NC to a set AI I and every r 2 NR to a binary relation rI over I . This mapping is extended to arbitrary concepts as shown in Table 1. The interpretation I is a model of the TBox T if CI DI for every C v D 2 T . The main reasoning problem is to decide subsumption [ 2, 12 ]: C is subsumed by D w.r.t. T (denoted C vT D) if CI DI holds for every model I of T . HL is the sublogic of EL that does not allow existential restrictions; it is a syntactic variant of Horn logic: every Horn clause with at least one positive literal can be seen as an HL GCI. An HL TBox is a core TBox if all its axioms are of the form A v B with A; B 2 NC.

Error-tolerant reasoning refers to the task of deriving meaningful consequences from a TBox that is known to contain errors. In the case of EL, an erroneous consequence refers to an error in a subsumption relation. If a TBox T entails an unwanted subsumption C vT D, then we are interested nding the ways in which this consequence can be avoided.

De nition 1 (repair). Let T be an EL TBox and C vT D. A repair of T w.r.t. C v D is a maximal (w.r.t. set inclusion) subset R T such that C 6vR D. The set of all repairs of T w.r.t. C v D is denoted by RepT (C v D). We will usually consider a xed TBox T , and hence say that R is a repair w.r.t. C v D, or even simply a repair, if the consequence is clear from the context. Example 2. The repairs of T = fA v 9r:X; 9r:X v B; A v Y , Y v B; A v B0g w.r.t. the consequence A v B are the sets Ri := T n Si; 1 i 4, where S1 = fA v 9r:X; A v Y g, S2 = fA v 9r:X; Y v Bg, S3 = f9r:X v B; A v Y g, and S4 = f9r:X v B; Y v Bg.

The number of repairs w.r.t. a consequence may be exponential, even for core TBoxes [ 26 ]. Each of these repairs is a potential way of avoiding the unwanted consequence; however, there is no way of knowing a priori which is the best one to use for further reasoning tasks. One common approach is to be cautious and consider only those consequences that follow from all repairs. Alternatively, one can consider brave consequences: those that follow from at least one repair. De nition 3 (cautious, brave). Let T be a TBox, C vT D, and C0; D0 be two concepts. C0 is bravely subsumed by D0 w.r.t. T and C v D if there is a repair R 2 RepT (C v D) such that C0 vR D0; C0 is cautiously subsumed by D0 w.r.t. T and C v D if for every repair R 2 RepT (C v D) it holds that C0 vR D0. If T or C v D are clear from the context, we usually omit them. Example 4. Let T , R1; : : : R4 be as in Example 2. A is bravely but not cautiously subsumed by Y u B0 w.r.t. T and A v B since A vR2 Y u B0 but A 6vR1 Y u B0. In the context of inconsistency-tolerant reasoning, other kinds of semantics which have better computational properties have been proposed [ 11, 21, 28 ]. Among these are the so-called IAR semantics, which consider the consequences that follow from the intersection of all repairs. Formally, C0 is IAR subsumed by D0 w.r.t. T and C v D if C0 vQ D0, where Q := TR2RepT (CvD) R: Example 5. Let T and R1; : : : ; R4 be as in Example 2. Then A is IAR subsumed by B0 w.r.t. T and A v B as A v B0 2 Ti4=1 Ri.

A notion dual to repairs is that of MinAs, or justi cations [ 7, 17 ]. A MinA for C vT D is a minimal (w.r.t. set inclusion) subset M of T such that C vM D. We denote as MinAT (C v D) the set of all MinAs for C vT D. There is a close connection between repairs and MinAs for error-tolerant reasoning. Theorem 6. Let T be a TBox, C; C0; D; D0 concepts with C vT D. Then We show that deciding cautious and IAR subsumptions is intractable already for core TBoxes. Deciding brave subsumptions is intractable for EL, but tractable for HL. We rst prove the latter claim using directed hypergraphs, which generalize graphs by connecting sets of nodes, rather than just nodes.

A directed hypergraph is a pair G = (V; E ), where V is a non-empty set of nodes, and E is a set of directed hyperedges e = (S; S0), with S; S0 V. Given S; T V, a path from S to T in G is a set of hyperedges f(Si; TiS) n2 E j 1 i ng such that for every 1 i n, Si S [ Sjn=11 Tj , and T i=1 Ti hold. The reachability problem in hypergraphs consists in deciding the existence of a path from S to T in G. This problem is decidable in polynomial time on jVj [ 15 ].

Recall that HL concepts are conjunctions of concept names; we can represent C = A1 u u Am as its set of conjuncts SC = fA1; : : : ; Amg. Each GCI C v D yields a directed hyperedge (SC ; SD) and every HL-TBox T forms a directed hypergraph GT . Then C vT D i there is a path from SC to SD in GT . Theorem 7. Brave subsumption in HL can be decided in polynomial time on the size of the TBox.

Proof. Let T be an HL TBox, and C; C0; D; D0 be HL concepts. C0 is bravely subsumed by D0 w.r.t. T and C v D i there is a path from SC0 to SD0 in GT that does not contain any path from SC to SD. If no such path exists, then (i) every path from SC0 to SD0 passes through SD, and (ii) every path from SC0 to SD passes through SC . We need to verify whether any of these two statements is violated. The existence of a path that does not pass through a given set is decidable in polynomial time. tu However, for EL this problem is NP-complete. To prove this we adapt an idea from [ 25 ] for reducing the NP-hard more minimal valuations (mmv) problem [ 7, 14 ]: deciding, for a monotone Boolean formula ' and a set V of minimal valuations satisfying ', if there are other minimal valuations V 2=V satisfying '. Theorem 8. Brave subsumption in EL is NP-complete.

We now show that the cautious and IAR semantics are intractable already for core TBoxes. This is a consequence of the intractability of the following problem. De nition 9 (axiom relevance). The axiom relevance problem consists in deciding, given a core TBox T , A v B 2 T , and A0 vT B0, whether there is a repair R of T w.r.t. A0 v B0 such that A v B 2= R.

Lemma 10. Axiom relevance is NP-hard.

Proof. We reduce the NP-hard path-via-node problem [ 20 ]: given a directed graph G = (V; E ) and nodes s; t; m 2 V, decide if there is a simple path from s to t in G that goes through m. Given an instance of the path-via-node problem, we introduce a concept name Av for every v 2 (V n fmg) [ fm1; m2g, and build the core TBox

T := fAv v Aw j (v; w) 2 E ; v; w 6= mg [ fAv v Am1 j (v; m) 2 E ; v 6= mg [ fAm2 v Av j (m; v) 2 E ; v 6= mg [ fAm1 v Am2 g: There is a simple path from s to t in G through m i there is a repair R of T w.r.t. As v At with Am1 v Am2 2= R. tu Theorem 11. Cautious subsumption and IAR subsumption w.r.t. core, HL or EL TBoxes are coNP-complete.

Proof. If C is not cautiously subsumed by D, we can guess a set R and verify in polynomial time that R is a repair and C 6vR D. If C is not IAR subsumed by D, we can guess a set Q T , and for every GCI Ci v Di 2= Q a set Ri such that Ci v Di 2= Ri. Verifying that each Ri is a repair and C 6vQ D is polynomial. Thus both problems are in coNP. To show hardness, for a GCI C v D 2 T , there is a repair R such that C v D 2= R i C 6vR D i C is neither cautiously nor IAR subsumed by D. By Lemma 10 both problems are coNP-hard. tu The hardness of error-tolerant reasoning is usually attributed to the fact that there can exist exponentially many repairs for a given consequence. However, this argument is incomplete. For instance, brave reasoning is polynomial in HL, although consequences may have exponentially many repairs already in this logic. We show now that cautious and brave subsumption are also hard on the number of repairs ; i.e., they are not what we call repair-polynomial.

De nition 12 (repair-polynomial). An error-tolerant problem w.r.t. a TBox T and a consequence C v D is repair-polynomial if it can be solved by an algorithm that runs in polynomial time on the size of both T and RepT (C v D).1 Theorem 13. Unless P = NP, cautious and brave subsumption of C0 by D0 w.r.t. T and C v D in EL are not repair-polynomial.

The proof adapts the construction from Theorem 8 to reduce the problem of enumerating maximal valuations that falsify a formula to deciding cautious subsumption. The number of repairs obtained from the reduction is polynomial on the number of maximal valuations that falsify the formula. Since this enumeration cannot be solved in time polynomial on the number of maximal falsi ers, cautious reasoning can also not be performed in time polynomial on the 1 Notice that the repairs are not part of the input. This is closely related to output complexity measures [ 16 ]. Input: Unwanted consequence C vT D, concepts C0; D0 Output: R RepT (C v D): repairs entailing C0 v D0

R RepT (C v D) for each R 2 RepT (C v D) do if C0 6vR D0 then

R R n fRg return R number of repairs. An analogous argument is used for brave reasoning. Thus, error-tolerant reasoning is hard even if only polynomially many repairs exist; i.e., there are cases where jRepT (C v D)j is polynomial on jT j, but brave and cautious reasoning require super-polynomial time. The culprit for hardness is therefore the computation of the repairs and not their number per se.

We now propose a method for improving the reasoning times, by precomputing a data structure based on the set of all repairs. 4

Precompiling Repairs

A nave solution for deciding brave or cautious subsumptions would be to enumerate all the repairs and check which of them entail the consequence that should be checked (Algorithm 1). C0 is then bravely or cautiously subsumed by D0 i R 6= ; or R = RepT (C v D), respectively. Each test C0 vR D0 requires polynomial time on jRj jT j [ 12 ], and exactly jRepT (C v D)j such tests are performed. The for loop in the algorithm thus needs polynomial time on the sizes of T and RepT (C v D). From Theorem 13 it follows that the rst step, namely the computation of all the repairs, must be expensive. In particular, these repairs cannot be enumerated in output-polynomial time; i.e., in time polynomial on the input and the output [ 16 ].

Corollary 14. The set of repairs for an EL TBox T w.r.t. C v D cannot be enumerated in output polynomial time, unless P = NP.

For any given error, one would usually try to decide whether several brave or cautious consequences hold. It thus makes sense to improve the execution time of these reasoning tasks by avoiding a repetition of the rst, expensive, step.

The set of repairs can be computed in exponential time on the size of T ; this bound cannot be improved in general since (i) there might exist exponentially many such repairs, and (ii) they cannot be enumerated in output polynomial time. However, this set only needs to be computed once, when the error is found, and can then be used to improve the reasoning time for all subsequent subsumption relations. Once RepT (C v D) is known, Algorithm 1 computes R, and hence decides brave and cautious reasoning, in time polynomial on jT j jRepT (C v D)j.

Clearly, Algorithm 1 does more than merely deciding cautious and brave consequences. Indeed, it computes the set of all repairs that entail C0 v D0. This information can be used to decide more complex reasoning tasks. For instance, Algorithm 2 Decide cautious and brave subsumption Input: Labelled TBox T , concepts C0; D0 procedure is-brave(T ; C0; D0) for each M 2 MinAT (C0 v D0) do if lab(M) 6= ; then

return true return false procedure is-cautious(T ; C0; D0)

; for each M 2 MinAT (C0 v D0) do

[ lab(M) if = f1; : : : ; ng then

return true return false one may be interested in knowing whether the consequence follows from most, or at least k repairs, to mention just two possible inferences. IAR semantics can also be decided in polynomial time on T and RepT (C v D): simply compute Q = TR2RepT (CvD) R, and test whether C0 vQ D0 holds. The rst step needs polynomial time on RepT (C v D) while the second is polynomial on Q T .

As we have seen, precompiling the set of repairs already yields an improvement on the time required for deciding error-tolerant subsumption relations. However, there are some obvious drawbacks to this idea. In particular, storing and maintaining a possibly exponential set of TBoxes can be a challenge in itself. Moreover, this method does not scale well for handling multiple errors that are found at di erent time points. When a new error is detected, the repairs of all the TBoxes need to be computed, potentially causing the introduction of redundant TBoxes that must later be removed. We improve on this solution by structuring all the repairs into a single labelled TBox.

Let RepT (C v D) = fR1; : : : ; Rng. We label every GCI E v F 2 T with lab(E v F ) = fi j E v F 2 Rig: Conversely, for every subset I f1; : : : ; ng we de ne the TBox TI = fE v F 2 T j lab(E v F ) = Ig. A set I is a component if TI 6= ;. Every axiom belongs to exactly one component and hence the number of components is bounded by jT j. One can represent these components using only polynomial space and all repairs can be read from them and a directed acyclic graph expressing dependencies between components. For simplicity we keep the representation as subsets of f1; : : : ; ng.

The labelled TBox has full information on the repairs, and on their relationship with each other. For S T , lab(S) := TEvF 2S lab(E v F ) yields all repairs containing S. If M is a MinA for C0 v D0, lab(M) is a set of repairs entailing this subsumption. Moreover, (C0 v D0) := SM2MinAT (C0vD0) lab(M) is the set of all repairs entailing C0 v D0. Thus, C0 is bravely subsumed by D0 i (C0 v D0) 6= ; and is cautiously subsumed i (C0 v D0) = f1; : : : ; ng. The set (C0 v D0) is the boundary for the subsumption C0 v D0 w.r.t. the labelled TBox T [ 4 ]. Several methods for computing the boundary exist. Since we are only interested in deciding whether this boundary is empty or equal to f1; : : : ; ng, we can optimize the algorithm to stop once this decision is made. This optimized method is described in Algorithm 2. The algorithm rst computes all MinAs for C0 vT D0, and their labels iteratively. If one of this labels is not empty, then the subsumption is a brave consequence; the procedure is-brave then returns true. Alternatively, is-cautious accumulates the union of all these labels in a set until this set contains all repairs, at which point it returns true.

IAR semantics can be solved through one subsumption test, and hence in polynomial time on the size of T , regardless of the number of repairs. Theorem 15. Let n = jRepT (C v D)j. Then C0 is IAR-subsumed by D0 i C0 vTJ D0, where J = f1; : : : ; ng.

This shows that precompiling all repairs into a labelled ontology can help reducing the overall complexity and execution time of reasoning. In the next section, we exploit the fact that number of MinAs for consequences in ontologies used in practice is relatively small and compute them using a saturation-based approach.

5 Implementation and Experiments

We ran two separate series of experiments. The goal of the rst series was to investigate the feasibility of error-tolerant reasoning in practice. We implemented a prototype tool in Java that checks whether a concept subsumption C v D is brave or cautious w.r.t. a given TBox T and a consequence C0 v D0. The tool uses Theorem 6 and the duality between MinAs and repairs, i.e. the repairs for C0 v D0 w.r.t T are obtained from the MinAs for C0 v D0 by consecutively removing the minimal hitting sets [ 27 ] of the MinAs from T . The tool rst computes all the MinAs for both inclusions C v D and C0 v D0 w.r.t. T , and then veri es whether some inclusions between MinAs for C v D and C0 v D0 hold to check for brave or cautious subsumptions. For the computation of the MinAs we used a saturation-based approach based on a consequence-based calculus [ 18 ]. More details regarding the computation of MinAs can be found in [ 23 ].

We selected three ontologies that are expressed mainly in EL and are typically considered to pose di erent challenges to DL reasoners. These are the January 2009 international release of SNOMED, version 13.11d of the NCI thesaurus,2 and the GALEN-OWL ontology.3 All non-EL axioms (including axioms involving roles only, e.g. role inclusion axioms) were rst removed from the ontologies. The number of axioms, concept names, and role names in the resulting ontologies is shown in Table 2.

For every ontology T we selected a number of inclusion chains of the form A1 vT A2 vT A3 vT A4; which were then grouped into Type I inclusions, where A2 vT A4 was set as the unwanted consequence, and Type II inclusions, where A2 vT A3 was de ned as the unwanted consequence. 2 http://evs.nci.nih.gov/ftp1/NCI_Thesaurus 3 http://owl.cs.manchester.ac.uk/research/co-ode/ For the NCI and SNOMED ontologies we chose inclusions A2 v A4 (for Type I) and A2 v A3 (for Type II) that were not entailed by the consecutive version of the considered ontology, i.e. those that can be considered to be \mistakes" xed in the consecutive release (the July 2009 international release of SNOMED and version 13.12e of the NCI Thesaurus). 500 inclusions of each type were found for SNOMED, but only 26 Type-I inclusions and 36 Type-II inclusions were detected in the case of NCI. For the GALEN-OWL ontology 500 inclusions chains of each type were chosen at random. For every Type-I chain, we then used our tool to check whether the inclusion A1 v A3 is a brave or cautious consequence w.r.t. A2 v A4. Similarly, for every Type-II inclusion we checked whether A1 v A4 is a brave or cautious consequence w.r.t. A2 v A3.

All experiments were conducted on a PC with an Intel Xeon E5-2640 CPU running at 2.50GHz. An execution timeout of 30 CPU minutes was imposed on each problem in this experiment series. The results obtained are shown in Table 3. The rst two columns indicate the ontology that was used and the inclusion type. The next three columns show the number of successful computations within the time limit, and the number of brave and cautious subsumptions, respectively. The average and the maximal number of MinAs over the considered set of inclusions are shown in the next two columns. The left-hand side of each of these columns refers to the MinAs obtained for the consequence for which its brave or cautious entailment status should be checked, and the right-hand side refers to the unwanted consequence. The last column shows the average CPU time needed for the computations over each considered set of inclusions.

The number of successful computations was the lowest for the experiments involving SNOMED, whereas no timeouts were incurred for NCI. Moreover, the highest average number of MinAs was found for Type-II inclusions for SNOMED with a maximal number of 54. GALEN-OWL required the longest computation times, which could be a consequence of the fact that the (full) GALEN ontology is generally seen as being di cult to classify by DL reasoners. The shortest computation times were reported for experiments involving NCI. All the successful computations required at most 11 GiB of main memory. ontology type #succ. comp. #brave #cautious avg. #MinAs max #MinAs avg. time (s)

In a second series of experiments we evaluated the advantages of performing precompilation when checking the brave and cautious entailment status of several inclusions w.r.t. an unwanted consequence. We implemented a slightly improved version of Algorithm 1 which iterates over all the repairs for the unwanted consequence and determines whether a consequence that should be checked is brave or cautious by using the conditions from De nition 3. The implemented algorithm stops as quickly as possible, e.g. when a non-entailing repair has been found, we conclude immediately that the consequence is not cautious. The computation of the repairs is implemented using the duality between MinAs and repairs as described above. The minimal hitting sets were computed using the Boolean algebraic algorithm from [ 22 ]. We used ELK [ 19 ] to check whether a given inclusion follows from a repair. In the following we refer to this improved algorithm as the nave approach.

For comparing the performance of Algorithms 1 and 2 in practice, we selected 226 inclusions between concept names from SNOMED having more than 10 MinAs, with a maximum number of 223. For each inclusion A v B we randomly chose ve inclusions A0i v Bi0 entailed by SNOMED, and tested whether A0i v B0 i is a brave or cautious subsumption w.r.t. A v B for every i 2 f1; : : : ; 5g using the nave approach and Algorithm 2. In this series of experiments we allowed each problem instance to run for at most 3600 CPU seconds, and 4 GiB of heap memory, and 16 GiB of main memory in total, were allocated to the Java VM.

The results obtained are depicted in Figure 1. The problem instances A v B are sorted ascendingly along the x-axis according to the number of repairs for A v B. The required computation times for each problem instance (checking whether the ve subsumptions are brave or cautious entailments w.r.t. the unwanted consequence) are shown along the y-axis on the left-hand side of the graph. If no corresponding y-value is shown for a given problem instance, the computation either timed out or ran out of memory. The number of repairs for the unwanted consequences is depicted with a solid line, and the corresponding values can be read o the y-axis on the right-hand side in logarithmic scale.

One can see that a relatively small number of MinAs can lead to several thousands (up to over 14 millions) of repairs. Also, if the number of repairs remains small, i.e. below 400, the nave approach performs fairly well, even outperforming the precompilation approach on a few problem instances. For larger number of repairs, however, none of the computations for the nave approach succeeded. The time required to perform reasoning with ELK outweighs the computation times of all the MinAs for the precompilation approach. In total 115 instances could be solved by the precompilation approach, whereas only 39 computations nished when the nave approach was used. In our experiments the computation of the MinAs was typically the most time consuming part; the computation of the repairs once all the MinAs were available could be done fairly quickly. 6

Conclusions

We introduced error-tolerant reasoning inspired by inconsistency-tolerant semantics from DLs and consistent query answering over inconsistent databases. The main di erence is that we allow for a general notion of error beyond inconsistency. We studied brave, cautious, and IAR reasoning, which depend on the class of repairs from which a consequence can be derived. Although we focused on subsumption w.r.t. EL TBoxes, these notions can be easily extended to any kind of monotonic consequences from a logical language.

Our results show that error-tolerant reasoning is hard in general for EL, although brave reasoning remains polynomial for some of its sublogics. Interestingly, IAR semantics, introduced to regain tractability of inconsistency-tolerant query answering in light-weight DLs, is coNP-hard, even for the basic logic HL with core axioms. Moreover, the number of repairs is not the only culprit for the hardness of these tasks: for both brave and cautious reasoning there is no polynomial-time algorithm on the size of T and the number of repairs that can solve these problems unless P = NP.

To overcome the complexity issues, we propose to compile the repairs into a labeled ontology. While the compilation step may require exponential time, after its execution IAR semantics can be decided in polynomial time, and brave and cautious semantics become repair-polynomial. Surprisingly, the idea of precomputing the set of all repairs to improve the e ciency of reasoning seems to have been overlooked in inconsistency-tolerant reasoning.

To investigate the feasibility of error-tolerant reasoning in practice, we developed a prototype based on computing all MinAs, and annotating axioms with the repairs they belong to. Our experiments show that despite their theoretical complexity, brave and cautious reasoning can be performed successfully in many practical cases, even for large ontologies. Our saturation-based procedure can detect a large number of MinAs for some consequences in a fairly short amount of time. There is a close connection between error-tolerant reasoning and axiompinpointing [ 6, 7 ]; our labelled ontology method also relates to context-based reasoning [ 4 ]. Techniques developed for those areas, like e.g. automata-based pinpointing methods [ 5 ], could be useful in this setting.

It is known that for some inexpressive DLs, all MinAs can be enumerated in output-polynomial time [ 24, 25 ]; the complexity of enumerating their repairs has not, to the best of our knowledge, been studied. We will investigate if enumerating repairs is also output-polynomial in those logics, and hence error-tolerant reasoning is repair-polynomial.

References

1. Arenas , M. , Bertossi , L. , Chomicki , J.: Consistent query answers in inconsistent databases . In: Proceedings of the 18th ACM SIGMOD-SIGACT-SIGART symposium on Principles of Database Systems (PODS 1999 ). pp. 68 { 79 . ACM ( 1999 )

2. Baader , F. : Terminological cycles in a description logic with existential restrictions . In: Gottlob, G. , Walsh , T. (eds.) Proceedings of the 18th International Joint Conference on Arti cial Intelligence (IJCAI'03) . pp. 325 { 330 . Morgan Kaufmann ( 2003 )

3. Baader , F. , Calvanese , D. , McGuinness , D.L. , Nardi , D. , Patel-Schneider , P.F . (eds.): The Description Logic Handbook: Theory, Implementation, and Applications . Cambridge University Press, 2nd edn. ( 2007 )

4. Baader , F. , Knechtel , M. , Pen~aloza, R.: Context-dependent views to axioms and consequences of semantic web ontologies . Journal of Web Semantics 12 { 13 , 22 { 40 ( 2012 ), available at http://dx.doi.org/10.1016/j.websem. 2011 . 11 .006

5. Baader , F. , Pen~aloza, R.: Automata-based axiom pinpointing . Journal of Automated Reasoning 45 ( 2 ), 91 { 129 ( August 2010 )

6. Baader , F. , Pen~aloza, R.: Axiom pinpointing in general tableaux . Journal of Logic and Computation 20 ( 1 ), 5 { 34 ( 2010 )

7. Baader , F. , Pen~aloza, R., Suntisrivaraporn , B. : Pinpointing in the description logic EL+ . In: Proceedings of the 30th German Conference on Arti cial Intelligence (KI2007) . LNAI , vol. 4667 , pp. 52 { 67 . Springer, Osnabruck, Germany ( 2007 )

8. Baader , F. , Suntisrivaraporn , B. : Debugging SNOMED CT using axiom pinpointing in the description logic EL+ . In: Proceedings of the 3rd Knowledge Representation in Medicine (KR-MED '08): Representing and Sharing Knowledge Using SNOMED. CEUR-WS , vol. 410 ( 2008 )

9. Bertossi , L. : Database repairing and consistent query answering . Synthesis Lectures on Data Management 3 ( 5 ), 1 { 121 ( 2011 )

10. Bienvenu , M. : On the complexity of consistent query answering in the presence of simple ontologies . In: Proceedings of the 26st Natonal Conference on Arti cial Intelligence (AAAI 2012 ) ( 2012 )

11. Bienvenu , M. , Rosati , R. : Tractable approximations of consistent query answering for robust ontology-based data access . In: Rossi, F . (ed.) Proceedings of the 23rd International Joint Conference on Arti cial Intelligence (IJCAI'13) . AAAI Press ( 2013 )

12. Brandt , S. : Polynomial time reasoning in a description logic with existential restrictions, GCI axioms , and - what else ? In: de Mantaras, R.L. , Saitta , L . (eds.) Proceedings of the 16th European Conference on Arti cial Intelligence , (ECAI 2004 ). pp. 298 { 302 . IOS Press ( 2004 )

13. Cote , R. , Rothwell , D. , Palotay , J. , Beckett , R. , Brochu , L. : The systematized nomenclature of human and veterinary medicine . Tech. rep. , SNOMED International, North eld, IL: College of American Pathologists ( 1993 )

14. Eiter , T. , Gottlob , G.: Identifying the minimal transversals of a hypergraph and related problems . Tech. Rep. CD-TR 91/16 , Christian Doppler Laboratory for Expert Systems , TU Vienna ( 1991 )

15. Gallo , G. , Longo , G. , Pallottino , S. : Directed hypergraphs and applications . Discrete Applied Mathematics 42 ( 2 ), 177 { 201 ( 1993 )

16. Johnson , D.S. , Yannakakis , M. , Papadimitriou , C.H. : On generating all maximal independent sets . Information Processing Letters 27 ( 3 ), 119 { 123 ( 1988 )

17. Kalyanpur , A. , Parsia , B. , Horridge , M. , Sirin , E.: Finding all justi cations of OWL DL entailments . In: Proceedings of the 6th International Semantic Web Conference and 2nd Asian Semantic Web Conference, ISWC 2007 , ASWC 2007 . LNCS , vol. 4825 , pp. 267 { 280 . Springer ( 2007 )

18. Kazakov , Y. : Consequence-driven reasoning for Horn SHIQ ontologies . In: Boutilier, C . (ed.) Proceedings of the 21st International Joint Conference on Articial Intelligence (IJCAI'09) . pp. 2040 { 2045 ( 2009 )

19. Kazakov , Y. , Krotzsch, M. , Simanc k , F.: The incredible ELK: From polynomial procedures to e cient reasoning with EL ontologies . Journal of Automated Reasoning ( 2013 ), to appear

20. Lapaugh , A.S. , Papadimitriou , C.H. : The even-path problem for graphs and digraphs . Networks 14 ( 4 ), 507 { 513 ( 1984 ), http://dx.doi.org/10.1002/net. 3230140403

21. Lembo , D. , Lenzerini , M. , Rosati , R. , Ruzzi , M. , Savo , D.F. : Inconsistency-tolerant semantics for description logics . In: Hitzler, P. , Lukasiewicz , T. (eds.) Proceedings of the 4th International Conference on Web Reasoning and Rule Systems (RR'10) . LNCS, vol. 6333 , pp. 103 { 117 . Springer ( 2010 )

22. Lin , L. , Jiang , Y. : The computation of hitting sets: Review and new algorithms . Information Processing Letters 86 ( 4 ), 177 { 184 ( 2003 )

23. Ludwig , M. : Just: a tool for computing justi cations w .r.t. EL ontologies. In: Proceedings of the 3rd International Workshop on OWL Reasoner Evaluation (ORE 2014 ) ( 2014 )

24. Pen~aloza, R., Sertkaya , B. : Complexity of axiom pinpointing in the DL-Lite family of description logics . In: Coelho, H. , Studer , R. , Wooldridge , M. (eds.) Proceedings of the 19th European Conference on Arti cial Intelligence , (ECAI 2010 ). Frontiers in Arti cial Intelligence and Applications , vol. 215 , pp. 29 { 34 . IOS Press ( 2010 )

25. Pen~aloza, R., Sertkaya , B. : On the complexity of axiom pinpointing in the EL family of description logics . In: Lin, F. , Sattler , U. , Truszczynski , M. (eds.) Proceedings of the Twelfth International Conference on Principles of Knowledge Representation and Reasoning (KR 2010 ). AAAI Press ( 2010 )

26. Pen~aloza, R.: Axiom-Pinpointing in Description Logics and Beyond . Ph.D. thesis , Dresden University of Technology, Germany ( 2009 )

27. Reiter , R.: A theory of diagnosis from rst principles . Arti cial Intelligence 32 ( 1 ), 57 { 95 ( 1987 )

28. Rosati , R.: On the complexity of dealing with inconsistency in description logic ontologies . In: Walsh, T . (ed.) Proceedings of the 22nd International Joint Conference on Arti cial Intelligence (IJCAI'11) . pp. 1057 { 1062 . AAAI Press ( 2011 )

29. Spackman , K. : Managing clinical terminology hierarchies using algorithmic calculation of subsumption: Experience with SNOMED-RT . Journal of the American Medical Informatics Association ( 2000 ), fall Symposium Special Issue.

30. W3C OWL Working Group: OWL 2 web ontology language document overview . W3C Recommendation ( 2009 ), http://www.w3.org/TR/owl2-overview/