Ontology repair remains one of the main bottlenecks for the development of ontologies for practical use. Many automated methods have been developed for suggesting potential repairs, but ultimately human intervention is required for selecting the adequate one, and the human expert might be overwhelmed by the amount of information delivered to her. We propose a decomposition of ontologies into smaller components that can be repaired in parallel. We show the utility of our approach for ontology repair, provide algorithms for computing this decomposition through standard reasoning, and study the complexity of several associated problems.
One of the main challenges in real-world Description Logic (DL) based applications is to maintain the ontologies consistent with the intended domain modeling, a task often involving interactions with domain experts. It is thus desirable to allow experts to work distributively and in parallel for verifying and correcting unexpected logical consequences. This task is of a particular importance in scenarios where information is precious, large, and complex, and where manual veri cation of a repair plan is a necessary but labour-consuming task.
Current research on ontology repair (see e.g. [
To repair the ontology, minimal hitting sets [18], represented with squared nodes in each sub gure from Figure 1, are the commonly used. The reason for ? This work is supported by the DFG Research Unit FOR 1513, project B1 and within the Cluster of Excellence `cfAED'. this choice is that a minimal hitting set of all MinAs corresponds to a minimal set of elements that need to be removed to avoid this consequence. That is, it provides a minimal repair plan, which can be computed automatically.
When multiple experts are available for authenticating a repair plan, it would be desirable to divide this task in a manner that allows experts to work in parallel. One way is to distribute one MinA to each expert. However, due to the overlaps between the MinAs, this may lead to unnecessary extra re-validations from di erent experts. Alternatively, we could distribute the minimal hitting sets; it is then unclear which hitting set should be sent from the many available. Consider the case where several hitting sets are precomputed and each one of them is sent to an expert. Besides the problem of possible overlaps among hitting sets in general, the large sizes of these sets (e.g. n + 1 in the example ontology O), means a high work load for each expert. Moreover, if a given hitting set is partitioned and distributed among di erent experts, there is a need of a communication mechanism for all experts to be informed of any decision made by the others, to avoid successive clashes and unnecessary e ort.
Based on these observations, we propose a novel methodology for
decomposing ontologies that allows experts to validate and apply a repair plan in parallel.
Generally speaking, we are interested in a decomposition that guarantees that:
{ no communication is required among experts and no axiom is submitted to
more than one expert; and
{ the union of the repairs returned is free of the unintended consequence.
For the example ontology O, a possible such decomposition is shown in Figure 2,
where each thickened ellipse is a component delivered to an expert for repair.
This decomposition allows n experts to work distributively, analysing two
axioms each. Stated in a general ontology language, our methodology is applicable
to all logic-based applications that have a necessity to have experts assisting
the repair process. Moreover, to keep the modeling convention of a domain, we
assume that subontologies should be delivered in their original format. All these
features distinguish the present work from the existing research e orts on
ontology decompositions, such as ontology modularization [
To remain as general as possible, we do not x any speci c knowledge representation formalism, but assume that we have an ontology language that describes two classes of well-formed formulas called axioms and consequences, respectively. An ontology O is a nite set of axioms, and a subset of O is called a subontology of O. For a xed ontology language L, a monotone consequence relation j= is a binary relation between ontologies O and consequences of L such that, if O j= and O O0, then O0 j= . If O j= , we say that O entails . For the rest of this paper, we denote as C the complexity of deciding entailments in L.
Two examples of ontological languages are HL and EL, among other DLs [
If an unwanted consequence follows from an ontology, we are interested in
repairing it, by nding an appropriate weaker ontology that does not entail
anymore. Formally, a repair for O w.r.t. is an ontology R such that (i) R 6j= ,
(ii) R is weaker than O; that is, for every consequence , if R j= , then O j= ,
and (iii) R is a minimal change of O. We simply say a repair for O when the
consequence is clear from context. If is an erroneous consequence, then a repair
describes a minimal change of O that removes it. The notion of minimal change
depends on the ontological knowledge and the desired application. For example,
one can de ne repairs to be maximal subontologies that avoid the consequence
(see e.g. [
M0 ( M, M0 6j= . a consequence with O j= . if M j= and for every An axiom is said to be consequence-free w.r.t. if it is not in any MinA for O w.r.t. . When the consequence is clear from context, we simply call it free axiom. Our goal is to divide the ontology into di erent components that can be repaired in parallel. Since free axioms are never responsible for the occurrence of the erroneous consequence , for the rest of the paper we assume that the ontology O does not contain any consequence free axiom w.r.t. . 3 MinAs receive several names. They are e.g. called MUS in propositional logic, and
MUPS [19] or justi cations [
We now formalize the notion of parallel ontology repair via decompositions. We start with the ideal case where an ontology can be fully decomposed into di erent components and repaired in parallel. However, the existence of this case can not be guaranteed. Hence, we subsequently propose a series of ontology decompositions that do not necessarily partition the whole ontology, but still allow repairs to be performed independently on each component. De nition 2 (Perfect Partition). Given an ontology O and a consequence if,Rai piesrafecrteppaairrtiotfioKn ioffoOr iw;1.r.t. i isna, tphaerntitSioinn=1fRKi1;is::a: ;rKepnagirofofOOsuwc.hr.tth.at,. In this case, the perfect partition has size n.
A perfect partition provides a way to break down an ontology into multiple disjoint subontologies that can be resolved independently, and the union of their repairs will lead to a repair of the whole ontology.4 This characterizes the intuition of repairing an ontoloy in parallel.
Example 3. Let O = fA v Bi; Bi v C j 1 i ng [ fA v Di; Di v C j 1 i mg. The sets Ki = fA v Bi; Bi v Cg and Li = fA v Di; Di v Cg, produce a perfect partition of O w.r.t. A v C. Repairing each Ki and Li w.r.t. A v C leads to a repair of O w.r.t. the same consequence.
In this example, the set of mutually disjoint MinAs produces a perfect partition of O. However, this is not true in general, as illustrated by the following example. Example 4. Consider the ontology
O = fA v B1; B1 v C; A v B1 u B2; B2 v Cg: M1 = fA v B1; B1 v Cg and M2 = fA v B1 u B2; B2 v Cg are two disjoint MinAs for A v C, and fM1; M2g is a partition of O. However, they do not form a perfect partition: fB1 v Cg and fA v B1 u B2g are repairs of M1 and M2, respectively, but their union fB1 v C; A v B1 u B2g is not a repair of O. The ontology O from this example does not have any perfect partition of size 2. Clearly, a perfect partition of size 1 always exists: the whole ontology itself is such one. Since only decompositions of size larger than 1 are meaningful for parallel repair, in the rest of the paper, by a perfect partition we mean its size is equal or greater than 2 unless explicitly stated otherwise. The following theorem provides a simple su cient condition for an ontology to have a perfect partition. Proposition 5. Let M1; : : : ; Mn be all the MinAs of O w.r.t. a consequence . If these MinAs are all pairwise disjoint, O has a perfect partition of size n. In general the condition of partitioning the ontology is too strong. In some cases, a decomposition of larger size can be obtained if some axioms are not included in any of the components. We formalize this idea next. 4 A subontology is the repair of itself if it does not contain a MinA.
De nition 6 (Perfect Partial-Partition). A set of mutually disjoint subontologies fK1; : : : ; Kng is a perfect partial partition of O w.r.t. a consequence if it satis es the following condition: given repairs Ri of Ki for each i; 1 i n, Sin=1 Ri is a repair for Sin=1 Ki w.r.t. .
To characterize these partial partitions, we introduce the notion of
decomposition. This is inspired by the work [
The decomposition D has size n, or is an n-decomposition; each Ki is a component of D; and Dn(O; ) denotes the set of n-decompositions of O w.r.t. the consequence .
Intuitively, the condition (i) characterizes the inner-connection such that each expert is assigned with a subontology containing some causes of the consequence. And the condition (ii) guarantees the outer-isolation as illustrated by the following example.
Example 8. Consider again the ontology O and the MinAs M1 and M2 from Example 4. fM1; M2g is not a decomposition because there fA v B1uB2; B1 v Cg is also a MinA contained in M1 [ M2, violating the condition (ii) of De nition 7. Suppose that M1 and M2 were distributed to two experts, which return the repairs B1 v C 2 M1 and A v B1 u B2 2 M2, respectively. Then, these repairs together would still entail the unwanted consequence.
Theorem 9. If D is an n-decomposition, then D is a perfect partial-partition of size n.
Theorem 9 tells that the inconsistencies in each component of a decomposition can be resolved distributively and the merged repair becomes consistent.
Notice that the union of the components needs not to be the whole ontology, so a decomposition de ned De ntion 7 is not necessarily a perfect partition. Let U = O n Sin=1 Ki. If U 6= ;, we cannot guarantee that Sin=1 Ri [ U does not entail the consequence. Consider again the example from the introduction with n = 2. For the decomposition fK1; K2g with Ki = fA v Bi; Bi v Cg for i = 1; 2, the axiom B2 v B1 2 U . The subontologies R1 = fB1 v Cg and R2 = fA v B2g are repairs for K1 and K2, respectively. However, Sin=1 Ri [ U j= A v C. To solve this issue, one can either drop the uncon rmed axiom B2 v B1 because the other axioms that can form a MinA with it have been veri ed by experts; or, repeat the same process by constructing a new decomposition to resolve the remaining inconsistencies. To parallelize the e ort of repairing the ontology, we are interested in decompositions of maximal size. The corresponding decision problem is the following.
Input: an ontology O, a consequence , an integer m Question: is there an m-decomposition of O w.r.t. ? As we show next, this problem can be solved using a special kind of decomposition made of MinAs only.
De nition 10 (MinA Decomposition). A decomposition D = fK1,...,Kng of O w.r.t. is a MinA decomposition if for every i; 1 i n, Ki is a MinA for O w.r.t. .
Lemma 11. O has an m-decomposition if and only if O has a MinA decomposition of size m.
Based on this lemma, we can decide max-decom by guessing m disjoint subsets K1; : : : ; Km of O in polynomial time, and verifying that they form a MinA decomposition; that is, solving the following problem.
Input: ontology O, consequence , D = fK1; : : : ; Kmg Question: is D a (MinA) decomposition of O w.r.t. ? To decide this problem, we can guess a MinA M that violates the second condition of De nition 7. To verify that M is indeed a MinA, polynomially many entailment tests are required. Thus we get the following bound.
This lemma provides only an upper bound for the problem; in particular, it
also shows that is-mina-decom is in coNPC. In general, these upper bounds do
not need to be tight. For example, in HL it is possible to decide in polynomial
time whether the set D = fM1; : : : ; Mmg is exactly the set of all MinAs for
an ontology O [
Algorithm 1 uses all these ideas to decide max-decom. The procedure notmina receives as input an ontology O and a consequence , and answers \yes" if O is not a MinA w.r.t. . This is the case if either O 6j= (line 18), or there is a strict subset of O that still entails (line 17). The other two procedures perform a non-deterministic guess; max-decom guesses the components, while is-decom guesses a MinA that violates the second condition of De nition 7. Theorem 13. max-decom is in ( 2P )C.
In particular, this theorem shows that max-decom is in 2P for both HL and EL. As before, the bound needs not be tight; indeed, using the arguments described above, it is easy to see that this problem is in NP for HL.
Algorithm 1 Deciding max-decom 1: procedure max-decom(O, , m) 2: for 1 i m do 3: guess Ki O 4: if not-mina(Ki, ) then return no 5: if Ki \ Kj = ; for all i; 1 i < j m then 6: return is-decom(fK1; : : : ; Kmg, ) 7: else return no 8: end procedure 9: procedure is-decom(D, ) 10: guess M SK2D K 11: if M * K for all K 2 D then 12: return not-mina(M, ) 13: else return yes 14: end procedure 15: procedure not-mina(O, ) 16: for all t 2 O do 17: if O n ftg j= then return yes 18: return O 6j= 19: end procedure Algorithm 2 Deciding perfect-part 1: procedure full-decom(O, , m) 2: for 1 i m do 3: guess Ki O 4: if fK1; : : : ; Kmg is a partition of O then 5: return is-decom(fK1; : : : ; Kmg, ) 6: else return no 7: end procedure
We are mainly interested in decompositions of maximal size since they allow for a more e cient parallelization of the repairing procedure: each component can be repaired independently, and the properties of the decomposition guarantee that the union of these repairs does not entail the consequence. However, we are interested in nding a repair for the whole input ontology O, not just for those axioms appearing in the decomposition. As described before, ideally we would nd a perfect partition of size n, for a given natural number n. Accordingly, we want to decide whether such a decomposition exists.
Input: an ontology O, a consequence , an integer m Question: is there a perfect partition of O w.r.t. of size m? Algorithm 2 describes a method for deciding perfect-part. In a nutshell, it guesses a partition D of O of size m, and then veri es, through a call to the procedure is-decom from Algorithm 1, that D is a decomposition. This yields the same complexity upper bound as for max-decom.
Theorem 14. perfect-part is in ( 2P )C.
We can in general visualize the set of MinAs for a consequence as a hypergraph GO; . Every axiom in O is represented through a node, and every MinA is a hyperedge in this hypergraph. Consider the sub-hypergraph HO; of GO; that contains only nodes belonging to some hyperedge; i.e., where all free axioms have been removed. It is easy to see that there is a perfect partition of size m i there are at least m maximally connected subgraphs of HO; . This is usually not a desired behavior for parallelization, since the number of components will be usually small. For example, the ontology depicted in Figure 3 allows for a decomposition of size 5, but its only perfect partition has size 1. On the other hand, if D is an n-decomposition of O w.r.t. , then D is a perfect partition of SK2D K w.r.t. of size n.
To maximize the number of components, and hence the degree of parallelization, we are willing to ignore some axioms, as described by the notion of decomposition. However, we should try to submit to the experts as much information from the original ontology as possible, to ensure an e ective repair process. This will be the focus of the next section. 4
While MinA decompositions are useful for deciding the existence of a decomposition of a given size, they, by construction, ignore a large amount of axioms from the ontology. Consider again the example in Figure 3. The maximal size of a decomposition of this ontology is 5, as shown on the left-hand-side graph through a MinA decomposition. In total, the components contain only 10 out of the 16 axioms from the ontology. Moreover, there is a whole MinA for the consequence that is left out of the decomposition; even if all the components are corrected, the obtained ontology would still entail the error. On the right-hand-side, we can observe a decomposition of the same size 5, whose components extend those of the MinA decomposition, and uses 14 out of the 16 axioms.
Algorithm 3 Finding a minimal remain decomposition 1: procedure find-min-rem-dec(O, , m) 2: D find-decom(O, , m) 3: R SK2D K 4: for all t 2 O n R do
6: R R [ ftg
8: end procedure
When we send a subontology for repair, it should be as informative as possible, to ensure that no simple errors are ignored. Clearly, the less axioms that are removed to build the decomposition, the more information that is gathered and used during the parallel repair. Thus, we are interested in nding, among all decompositions of maximal size, those that include the most axioms possible. De nition 15 (Minimal Remain Decomposition). Let n be a natural number and O j= . The remain of a decomposition D is O n (SK2D K). A decomposition D 2 Dn(O; ) is a minimal remain decomposition if there is no D0 2 Dn(O; ) with SK2D K ( SK2D0 K.
In other words, a decomposition D has minimal remain if it is not possible to decompose a proper superset of SK2D K in the same number of components. Consider again the example in Figure 3. The decomposition on the right-handside has a remain with two axioms. It is a minimal remain decomposition, since adding any of these two axioms would destroy the properties of decompositions.
To nd a minimal remain decomposition, we can recursively try to add axioms from the remainder of a previously known n-decomposition, until none can be added, as described in Algorithm 3. More precisely, let D be an n-decomposition, for instance, a MinA decomposition of size n that was constructed through Algorithm 1, and let R = SK2D K; i.e., R is the complement of the remain of D. For each axiom t in the remain of D, we decide whether R [ ftg has a full n-decomposition. If so, then t is added to R. At the end of this iteration, R has a maximal subontology that allows for a perfect partition of size n. Any perfect partition of this subontology is hence guaranteed to have minimal remain.
The internal subprocedure in lines 3 to 6 of Algorithm 3 can be easily adapted to verify that the decomposition D has minimal remain.
Input: ontology O, consequence , D = fK1; : : : ; Kmg Question: is D a minimal remain decomposition of O w.r.t. ? In the variant algorithm, one only has to check that R [ ftg has no perfect partition, for every t 2 O n R. If that is the case, then D has minimal remain. Theorem 16. is-min-rem-decom is in ( 2P )C. Notice that the decomposition obtained through Algorithm 3 may have no resemblance with the rst decomposition found at line 2. Indeed, the only requirement is that there is a perfect partition of all the axioms used, which could di er greatly from the original one. In some cases, e.g. when the rst decomposition was constructed from some speci c MinAs that should remain connected, it is desirable to only add axioms to the existing components.
De nition 17 (Pareto Decomposition). Given n 2 N, O j= , and decompositions D; D0 2 Dn(O; ), D is contained in D0, denoted by D D0 if, for every K 2 D there is a K0 2 D0 such that K K0. D is a Pareto decomposition if there is no D0 6= D with D D0.
Clearly, every minimal remain decomposition is also Pareto. The converse, however, does not hold. Consider the situation depicted in Figure 4, where the ellipses represent the di erent MinAs for a given consequence. This ontology can be decomposed into a perfect partition of size two, simply by considering its connected subgraphs. It is easy to see that the 2-decomposition D, where one component is formed by the diamond-shaped axioms, and the other by the triangle-shaped axioms is a Pareto decomposition. However, the dot-shaped axiom is in the remain of D. This implies that D is not a minimal-remain decomposition.
To nd a Pareto decomposition, we can use the same ideas of Algorithm 3. We rst nd a decomposition, and then try to add each of the remaining axioms to one of the components, as long as this addition still yields a decomposition. It can also be restricted to decide whether an input decomposition is already Pareto or not. Notice, however, that in line 5 the algorithm for deciding Pareto decomposition does not need to verify whether a set of axioms accepts a full decomposition, but rather whether a set of subontologies forms a decomposition, which, as seen before, is a simpler problem. Thus, we have the following.
Input: ontology O, consequence , D = fK1; : : : ; Kmg Question: is D a Pareto decomposition of O w.r.t. ?
We have considered decompositions that maximize the information stored in the components in two di erent ways: either by minimizing the elements that remain out of the decomposition, or by maximizing the components in a Pareto optimal manner. Notice, however, that some of the axioms included in a component might be irrelevant for the repair of that speci c component. For that reason, we might also be interested in justi ed decompositions. De nition 19 (Justi ed Decomposition). Let O j= . A decomposition D is called justi ed if for every K 2 D and every t 2 K there exists a MinA M of O w.r.t. such that t 2 M K.
Clearly, we can combine this notion with the previous ones and obtain, e.g.,
Pareto justi ed decompositions. All the algorithms presented so far can be
easily adapted to handle justi ed decompositions. One only needs to perform an
additional check to verify that there is a full MinA for every axiom contained
in a component. This test adds a new non-deterministic test, and hence the
upper bounds increase to the next level of the polynomial hierarchy. Moreover,
this jump in the hierarchy cannot be avoided since deciding whether an axiom is
justi ed in a component is already NP-hard for very simple sublogics of HL [
We have introduced several notions of ontology decomposition targeted towards an e cient repair mechanism. Our motivating idea is that human experts, which are usually in demand for a correct repair of an ontology, can be easily overwhelmed by the amount of axioms provided to them. We thus suggest to divide the ontology into disjoint components that can be repaired in parallel, possibly by several di erent experts. Our de nition of decomposition guarantees that the combination of the individual repairs for the components does not yield any new errors, hence providing an e cient parallelization of the repair process.
We have mainly focused on studying the di erent decision problems associated with decomposing ontologies, and their complexity. Our approach is general, considering an arbitrary monotonic consequence relation over some ontology language. Hence, our complexity analysis can only provide upper bounds; whether these bounds are tight or not is a matter of the speci c language used. However, our results can be instantiated to well-known ontology languages. In Table 1 we summarize the complexity of these problems for DLs. The cells show the known upper bound for deciding the problems at each column; cells with a darker background represent tight bounds.
We plan to study the precise complexity of these problems for speci c languages, in particular for light-weight DLs. We will also further consider the applicability of our decompositions for practical ontology repair. To this goal, we will implement optimized versions of our algorithms and study the viability of developing a repair plan, in which components are sent to experts in a manner that minimizes the expected total e ort and time required to remove the error. 12th Int. Conf. on the Principles of Knowledge Representation and Reasoning (KR-10). AAAI Press (2010) 17. Pen~aloza, R.: Axiom Pinpointing in Description Logics and Beyond. Ph.D. thesis, Institute for Theoretical Computer Science, Faculty of Computer Science, TU Dresden, Germany (2009) 18. Reiter, R.: A theory of diagnosis from rst principles. Artif. Intell. 32(1), 57{95 (Apr 1987), http://dx.doi.org/10.1016/0004-3702(87)90062-2 19. Schlobach, S., Cornet, R.: Non-standard reasoning services for the debugging of description logic terminologies. In: Proceedings of the 18th International Joint Conference on Arti cial Intelligence. pp. 355{360. Morgan Kaufmann Publishers Inc. (2003), http://dl.acm.org/citation.cfm?id=1630659.1630712 20. Suntisrivaraporn, B.: Polynomial-Time Reasoning Support for Design and Maintenance of Large-Scale Biomedical Ontologies. Ph.D. thesis, Institute for Theoretical Computer Science, Faculty of Computer Science, TU Dresden, Germany (2009)