Motivation. Most artificial intelligence applications rely on knowledge that is encoded in a knowledge base (KB) by means of some logical knowledge representation language such as propositional logic (PL) [CL73], Datalog [CGT89], first-order logic (FOL) [CL73], The Web Ontology Language (OWL [PSHH04], OWL 2 [GHM08, MPSP09]) or Description Logic (DL) [BCM07]. Experts in a variety of application domains keep developing KBs of constantly growing size. A concrete example of a repository containing biomedical KBs is the Bioportal2, which comprises vast ontologies with tens or even hundreds of thousands of terms each (e.g. the SNOMED-CT ontology with currently over 395.000 terms). Such KBs however pose a significant challenge for people as well as tools involved in their evolution, maintenance and application.

All these activities are based on the most essential benefit of logical KBs, namely the opportunity to perform automatic reasoning to derive implicit knowledge or to answer complex queries about the modeled domain. The feasibility of meaningful reasoning requires a KB to meet the minimum quality criterion consistency, i.e. there must not be any contradictions in the KB. Because any logical formula can be derived from an inconsistent KB. Further on, one might postulate further requirements to be met by a KB. For instance, one might consider faulty a FOL KB entailing for some predicate symbol p occurring in the KB. Such a KB would be incoherent, i.e. it would violate the requirement coherency (which was originally defined for DL KBs [SHCH07, PSK05]). Additionally, test cases can be specified giving information about desired (positive test cases) and non-desired (negative test cases) entailments a correct KB should feature. This characterization of a KB’s intended semantics is a direct analogon to the field of software debugging, where test cases are exploited as a means to verify the correct semantics of the program code.

As KBs are growing in size and complexity, their likeliness of violating one of these criteria increases. Faults in KBs may, for instance, arise because human reasoning is simply overstrained [HBP11, HPS09]. That is, generally a person will not be capable of completely grasping or mentally processing the entire knowledge contained in a (large or complex) KB at once. In fact, a person might fully comprehend some isolated part of a the KB, but might not be able to determine or understand all implications or nonimplications of this isolated part combined with other parts of a KB, i.e. when new logical formulas are added.

Another reason for the non-compliance with the mentioned quality criteria imposed on KBs might be that multiple (independently working) editors contribute to the development of the KB [NCLM06] which may lead to contradictory formulas. The OBO Project3 and the NCI Thesaurus4 are examples of collaborative KB development projects. Employing automatic tools, e.g. [JRG11, NB12, JMSK09], to generate (parts of) KBs can further exacerbate the task of KB quality assurance [Mei11, EFvH11].

Moreover, as studies in cognitive psychology [CP71, JL99] attest, humans make systematic errors while formulating or interpreting logical formulas. These observations are confirmed by [RDH04, RCVB09] which present common faults people make when developing a KB (ontology). Hence, it is essential to devise methods that can efficiently identify and correct faults in a KB.

Non-Interactive KB Debugging. Given a set of requirements to the KB and sets of test cases, KB debugging methods [SHCH07, KPHS07, FS05, HPS08] can localize a (potential) fault by computing a subset D of the formulas in the KB K called a diagnosis. At least all formulas in a diagnosis must be (adequately) modified or deleted in order to obtain a KB that satisfies all postulated requirements and test cases. Such a KB constitutes the solution to the KB debugging problem. Figure 1.15 outlines such a KB debugging system. The input to the system is a diagnosis problem instance (DPI) defined by

• some KB K formulated using some (monotonic) logical language L (every formula in K might be correct or faulty),

• (optionally) some KB B (over L) formalizing some background knowledge relevant for the domain modeled by K (such that B and K do not share any formulas; all formulas in B are considered correct)

• a set of requirements R to the correct KB,

• sets of positive (P) and negative (N ) test cases (over L) asserting desired semantic properties of the correct KB and

• (optionally) some fault information FP, e.g. in terms of fault probabilities of logical formulas in K.

Moreover, the system requires a sound and complete logical reasoner for deciding consistency (coherency) and calculating logical entailments of a KB formulated over the language L. Some approaches (including the ones presented in this work) use the reasoner as a black-box (e.g. [SFFR12, Hor11]) within the debugging system. That is, the reasoner is called as is and serves as an oracle independent from other computations during the debugging process; that is, the internals of the reasoner are irrelevant for the debugging task. On the other hand, glass-box approaches (e.g. [SHCH07, Hor11, KPSH05]) attempt to exploit internal modifications of the reasoner for debugging purposes; in other words, the sources of problems (e.g. contradictory formulas) in the KB are computed as a direct consequence of reasoning [Hor11]. The advantages of a black-box approach over a glass-box approach are the lower memory consumption and better performance [KPSH05] of the reasoner and the reasoner independence of the debugging method. The latter benefit is essential for the generality of our approaches and their applicability to various knowledge representation formalisms.

Given these inputs, the debugging system focuses on (a subset of) all possible fault candidates (usually the set of minimal, i.e. irreducible, diagnoses) and usually outputs the most probable one amongst these if some fault information is provided or the minimum cardinality one, otherwise. Alternatively, a debugging system might also be employed to calculate a predefined number of (most probable or minimum cardinality) minimal diagnoses or to determine all minimal diagnoses computable within a predefined time limit.

Figure 1.1: The principle of non-interactive KB debugging.

Issues with Non-Interactive KB Debugging Systems. In real-world scenarios, debugging tools often have to cope with large numbers of minimal diagnoses where the trivial application, i.e. deletion, of any minimal diagnosis leads to a (repaired) KB with different semantics in terms of entailed and non-entailed formulas. For example, in [SF10] a sample study of real-world KBs revealed that the number of different minimal diagnoses might exceed thousand by far (1782 minimal diagnoses for a KB with only 1300 formulas). In such situations simple visualization of all these alternative modifications of the ontology is clearly ineffective. Selecting a wrong diagnosis (in terms of its semantics, not in terms of fulfillment of test cases and requirements) can lead to unexpected entailments or non-entailments, lost desired entailments and surprising future faults when the KB is further developed. Manual inspection of a large set of (minimal) diagnoses is time-consuming (if not practically infeasible), error-prone and often computationally infeasible due to the complexity of diagnosis computation.

Moreover, [Stu08] has put several (non-interactive) debugging systems to the test using a test set of faulty (incoherent OWL) real-world KBs which were partly designed by humans and partly by the application of automatic systems. The result was that most of the investigated systems had serious performance problems, ran out of memory, were not able to locate all the existing faults in the KB (incompleteness), reported parts of a KB as faulty which actually were not faulty (unsoundness), produced only trivial solutions or suggested non-minimal faults (non-minimality). Often, performance problems and incompleteness of non-interactive debugging methods can be traced back to an explosion of the search tree for minimal diagnoses.

The Solution: Interactive KB Debugging. In this work we present algorithms for interactive KB debugging. These aim at the gradual reduction of compliant minimal diagnoses by means of user interaction, thereby seeking to prevent the search tree for minimal diagnoses from exploding in size by performing regular pruning operations. “User” in this case might refer to a single person or multiple persons, usually experts of the particular domain the faulty KB is dealing with such as biology, medicine or chemistry. Throughout an interactive debugging session, the user is asked a set of automatically chosen queries about the domain that should be modeled by a given faulty KB. A query can be created by the system after a set D of a minimum of two minimal diagnoses has been precomputed (we call D the leading diagnoses). Each query is a conjunction (i.e. a set) of logical formulas that are entailed by some correct subset of the formulas in the KB. With regard to one particular query Q, any set of minimal diagnoses for the KB, in particular the set D which has been utilized to generate Q, can be partitioned into three sets, the first one () including all diagnoses in D compliant only with a positive answer to Q, the second () including all diagnoses in D compliant only with a negative answer to Q, and the third () including all diagnoses in D compliant with both answers. A positive answer to Q signalizes that the conjunction of formulas in Q must be entailed by the correct KB wherefore Q is added to the set of positive test cases. Likewise, if the user negates Q, this is an indication that at least one formula in Q must not be entailed by the correct KB. As a consequence, Q is added to the set of negative test cases.

Assignment of a query Q to either set of test cases results in a new debugging scenario. In this new scenario, all elements of are no longer minimal diagnoses given that Q has been classified as a positive test case. Otherwise, all diagnoses in are invalidated. In this vein, the successive reply to queries generated by the system will lead the user to the single minimal solution diagnosis that perfectly reflects their intended semantics. In other words, after deletion of all formulas in the solution diagnosis from the KB and the addition of the conjunction of all formulas in the specified positive test cases to the KB, the resulting KB meets all requirements and positive as well as negative test cases. In that, the added formulas contained in the positive test cases serve to replace the desired entailments that are broken due to the deletion of the solution diagnosis from the KB.

Thence, in the interactive KB debugging scenario the user is not required to cope with the understanding of which faults (e.g. sources of inconsistency or implications of negative test cases) occur in the faulty initial KB, why they are faults (i.e. why particular entailments are given and others not) and how to repair them. All these tasks are undertaken by the interactive debugging system.

The proposed approaches to interactive KB debugging in this work follow the standard model-based diagnosis (MBD) technique [Rei87, dKW87]. MBD has been successfully applied to a great variety of problems in various fields such as robotics [SW05], planning [SW09], debugging of software programs [WSM02], configuration problems [FFJS04], hardware designs [FSW99], constraint satisfaction problems and spreadsheets [ARW12]. Given a description (model) of a system, together with an observation of the system’s behavior which conflicts with the intended behavior of the system, the task of MBD is to find those components of the system (a diagnosis) which, when assumed to be functioning abnormally, provide an explanation of the discrepancy between the intended and the observed system behavior. Translated to the setting of KB debugging, the set of “system components” comprises the formulas in the given faulty KB K. The “system description” refers to the statement that the KB K along with the background KB B and the positive test cases must meet all predefined requirements (e.g. consistency, coherency) and must not logically entail any of the negative test cases , i.e.

The “observation which conflicts with the intended behavior of the system” corresponds to the finding that (i) or (ii) or both are violated. That is, the “system description” along with the “observation” and the assumption that all components are sound yields an inconsistency. An “explanation for the discrepancy between observed and intended system behavior” (i.e. a diagnosis) is the assumption D that all formulas in a subset D of K are faulty (“behave abnormally”) and all formulas in K\D are correct (“do not behave abnormally”) such that the “system description” along with the “observation” and the assumption D is consistent. Computation of (minimal) diagnoses is accomplished with the aid of minimal conflict sets, i.e. irreducible sets of formulas in the KB K that preserve the violation of (i) or (ii) or both.

An MBD problem can be modeled as an abduction problem [BATJ91], i.e. finding an explanation for a set of data. It was proven in [BATJ91] that the computation of the first explanation (minimal diagnosis) is in P. However, given a set of explanations (minimal diagnoses) it is NP-complete to decide whether there is an additional explanation (minimal diagnosis). Stated differently, the detection of the first explanation can be efficiently accomplished whereas the finding of any further one is intractable (unless P = NP). When seeing the (interactive) KB debugging problem as an abduction problem, one must additionally take into account the costs for reasoning. Because, a call to a logical reasoner is required in order to decide whether or not a set of hypotheses (a subset of the KB) is an explanation (minimal diagnosis). Incorporating the necessary reasoning costs and assuming consistency a minimal requirement to the correct KB, the finding of the first explanation (minimal diagnosis) is already NPhard even for propositional KBs [SL89] (since propositional satisfiability checking is NP-complete). The worst case complexity for the debugging of KBs formulated over more expressive logics such as OWL 2 (reasoning is 2-NEXPTIME-complete [GHM08, Kaz08]) will be of course even worse. This seems quite discouraging. However, we have shown in our previous works [RSFF13, SFFR12, SFRF14c] that for many real-world KBs interactive KB debugging is feasible in reasonable time, despite high (or intractable) worst case reasoning costs and the intractable complexity of the abduction (i.e. minimal diagnosis finding) problem as such. Hence, the goal of this work is amongst others to present algorithms that work well in many practical scenarios.

Assumptions about the Interacting User. About a user u consulting an (interactive) debugging system, we make the following plausible assumptions:

U1 u is not able to explicitly enumerate a set of logical formulas that express the intended domain that should be modeled in a satisfactory way, i.e. without unwanted entailments or non-fulfilled requirements,

U2 u is able to answer concrete queries about the intended domain that should be modeled, i.e. u can classify a given logical formula (or a conjunction of logical formulas) as a wanted or unwanted proposition in the intended domain (i.e. an entailment or non-entailment of the correct domain model).

The first assumption is obviously justified since otherwise u could have never obtained a faulty KB, i.e. a KB that violates at least one requirement or test case, and there would be no need for u to employ a debugging system.

Regarding the second assumption, the first thing to be noted is that any KB (i.e. any model of the intended domain) either does entail a certain logical formula ax or it does not entail ax. Second, if u is assumed to bring along enough expertise in that domain, u should be able to gauge the truth of (at least) some formulas about that domain, especially if these formulas constitute logical entailments of parts of the specified knowledge in KB so far. We want to emphasize that u is not required to be capable of answering all possible queries (or formulas) about the respective domain since u might always skip a particular query in our system without any noticeable disadvantages. In such a case, the system keeps generating further queries, one at a time (usually the next-best one according to some quality measure for queries), until u is ready to answer it. As the number of possible queries is usually exponential in the number of minimal diagnoses exploited to compute it, there will be plenty of different “surrogate queries” in most scenarios.

A Motivating Example. To get a more concrete idea of these assumptions, the reader is invited to think about whether the following first-order KB K is consistent (a similar example is discussed in [HPS09]):

If we assume that the predicate symbols res, secr and gen stand for ’researcher’, ’secretary’ and ’general employee’, respectively, and the constant pam stands for the person Pam, the KB says the following:

• Formula 1.1: “Somebody is a researcher if and only if everything they write is a paper.”

• Formula 1.2: “Everybody who writes something is a researcher.”

• Formula 1.3: “Each secretary is a general employee.”

• Formula 1.4: “No general employee is a researcher.”

• Formula 1.5: “Pam is a secretary.”

This KB is indeed inconsistent. The reader might agree that it is not very easy to understand why this is the case. The observations made in [HPS09] concerning a slight modification of the KB K extracted from a real-world KB confirm this assumption. Compared to K, the KB included only Formulas 1.1- 1.3 of K, was formulated in DL (cf. Section 2.2), and used the terms A, C, . . . instead of res, paper, . . . . Amongst others, this KB was used as a sample KB in a study where participants had to find out whether a concrete given formula is or is not entailed by a concrete given KB. In the case of the KB , the assignment (translated to the terminology in our KB K) was to find out whether is an entailment of formulas 1.1-1.3. Although contains only three formulas, the result was that even participants with many years of experience in DL, among them also DL reasoner developers, did not realize that this is in fact the case (the reason for this entailment to hold is that formulas 1.1-1.3 imply that holds).

Since is also necessary for the inconsistency of K, this suggests that people might also have severe difficulties in comprehending why K is inconsistent. Once the validity of this entailment is clear, it is relatively straightforward to see that K cannot have any models. For, res(pam) (due to ) and (due to formulas 1.3-1.5) are implications of K.

Consequently, we might also assume that even experienced knowledge engineers (not to mention pure domain experts) could end up with a contradictory KB like K, which substantiates our first assumption (U1) about u. Probably, the intention of those people who specified formulas 1.1-1.3 was not that should be entailed. That is, it might be already a too complex task for many people to (mentally) reason even with such a small KB like this and manually derive implicit knowledge from it.

However, on the other hand, we might well assume u to be able to answer a concrete query about the intended domain they tried to model by K. For instance, one such query could be whether is a desired entailment of their model (i.e. “should everybody be a researcher in your intended model of the domain?”). If we assume the (seemingly obvious) case that u negates this query, i.e. asserts that this is an unwanted entailment, then an interactive debugging system (employing a logical reasoner) can derive that at least one of the formulas 1.1 and 1.2 must be faulty. This holds because the only set-minimal explanation in terms of formulas in K for the entailment is given by these two formulas. In other words, the set of formulas {1.1, 1.2} is the only minimal conflict set in K given that is a negative test case. Hence, the deletion (or suitable modification) of any of these formulas will break this unwanted entailment.

Before it is known that must not be entailed by the correct KB, given consistency is the only requirement to the KB postulated by u, the complete KB K is a minimal conflict set. That is, after the assignment of a (strategically well-chosen) query to the set of positive or, in this case, negative test cases can already shift the focus of potential modifications or deletions to a subset of only two candidate formulas. We would call these two formulas the remaining minimal diagnoses after an answer to the query has been submitted.

Initially, there are five minimal diagnoses, each formula in K is one. The meaning of a diagnosis is that its deletion from K leads to the fulfillment of all requirements and (so-far-)specified positive and negative test cases. As the reader should be easily able to see, the deletion of any formula from K yields a consistent KB; e.g. removing formula 1.5 prohibits the entailment whereas discarding formula 1.2 prohibits the entailment res(pam). The reader should notice that, as soon as the negative test case is known, removing (only) formula 1.5 does not yield a correct KB since {1.1, 1.2, 1.3, 1.4} still entails which must not be entailed.

A second query to u could be, for example, (i.e. “is there somebody who writes something, but is no researcher?”). Again, it is reasonable to suppose that u might know whether or not this should hold in their intended domain model. The (seemingly obvious) answer in this case would be positive, e.g. because u intends to model students who write homework, exams, etc., but are no researchers. This positive answer leads to the new positive test case . Adding this positive test case, like a set of new formulas, to the KB K would result in . The debugging system would then figure out that formula 1.2 is the only minimal conflict set in the KB . The reason for this is that the elimination of formula 1.2 breaks the entailment (negative test case) and enables the addition of a new desired entailment (positive test case) without involving the violation of any requirements (consistency). Therefore, formula 1.2 is the only minimal diagnosis that is still compliant with the new knowledge in terms of and obtained.

It is important to notice that the solution KB that is returned to the user as a result of the interactive debugging session includes a new logical formula that can be seen as a repair of the deleted formula 1.2. Since the knowledge after the debugging session is that must be true, this new knowledge is incorporated into the KB . This indicates that the fault in KB was simply that the in front of formula 1.2 had been forgotten.

Notice however that the positive test case is not added to K as a usual KB formula, but rather as an extension of K that has already been approved by the user. Should the user at some later point in time commit the same fault again (and explicitly specify some formula x equivalent to formula 1.2), then the interactive debugging system, owing to the positive test case , would immediately detect a singleton conflict comprising only formula x. As a consequence, each diagnosis considered during this later debugging session would suggest to delete or modify (at least) x.

This scenario should illustrate that, in spite of not being able to specify their domain knowledge in a logically consistent way, the user u might still be able to answer questions about the intended domain, which supports our second assumption made about the user u (the reader might agree that answering and is much easier than recognizing the entailment of the KB). In other words, the availability of an (efficient) debugging system could help u debug their KB, without needing to analyze which entailments hold or do not hold, why certain entailments hold or do not hold or why exactly the KB does not meet certain imposed requirements or test cases, by simply answering queries whether a certain entailment should or should not hold. These queries are automatically generated by the system in a way that they focus on the problematic parts of the KB, i.e. the minimal conflict sets, and discriminate between the possible solution candidates, i.e. the minimal diagnoses.

Benefits of the Usage of Conflict Sets. We want to remark that the usage of minimal conflict sets “naturally” forces the system to take into consideration only the smallest relevant (faulty) parts of the problematic KB. This is owed to the property of minimal conflict sets to abstract from what all the reasons for a certain entailment or requirements violation are. Instead, only the “root” (subset-minimal) causes for such violations are examined and no computation time is wasted to extract “purely derived” causes (those which are resolved as a byproduct of fixing all root causes from which it is derived, cf. [Hor11, Kal06]). For example, assuming the debugging scenario involving our example KB consisting only of formulas 1.1-1.4 which is incoherent and a requirements set including coherency. Then, there are two entailments reflecting the incoherency of this KB, first and second (these entailments hold due to which follows from formulas 1.1 and 1.2). Of these two, only the second one is a “root” problem; the first one is a “purely derived” problem. That means, the entailment only holds due to the presence of the entailment . So, the cause for is given by the set of formulas {1.1, 1.2, 1.4} whereas the proper superset {1.1, 1.2, 1.3, 1.4} of this set accounts for the entailment . The exploitation of minimal conflict sets (the only minimal conflict set for this KB is {1.1, 1.2, 1.4}) ascertains that such “purely derived” causes of requirements or test case violations will not be considered at all.

Figure 1.2: The principle of interactive KB debugging.

The Ability to Incorporate Background Knowledge. Another feature of the approaches described in this work is their ability to incorporate relevant additional information in terms of a background knowledge KB B (which is regarded to be correct). B is a (consistent) KB which is usually semantically related with the faulty KB, e.g. B represents knowledge about the domain modeled by K that has already been sufficiently endorsed by domain experts. For instance, a doctor who wants to express their knowledge of dermatology in terms of a KB might resort to an approved background KB that specifies the human anatomy. Taking this background information into account puts the problematic KB into some context with existing knowledge and can thereby help a great deal to restrict the search space for solutions of the (interactive) KB debugging problem. This has also been found in [Stu08]. This useful strategy of prior search space restriction is also exploited in the field of ontology matching6 where automatic systems are employed to generate an alignment, i.e. a set of correspondences between semantically related entities of two different ontologies (KBs). Here, both ontologies are considered correct and diagnoses are only allowed to include elements of the alignment [MST07].

Applying a strategy like that to our example KB given above, supposing that we know that Pam is not a researcher in the world the KB should model, we might specify the background KB prior to starting the interactive debugging session. This would immediately reduce the initial set of possible minimal diagnoses from five (i.e. the entire KB) to two (i.e. the first two formulas 1.1 and 1.2). Reason for this is that the entailment of formulas 1.1 and 1.2 already conflicts with the background knowledge .

Outline of an Interactive KB Debugging System. The schema of an interactive debugging system is pictured by Figure 1.2.7 As in the case of a non-interactive debugging system (see above), the system receives as input a diagnosis problem instance (DPI). Further on, a range of additional parameters might be provided to the system. These serve as a means to fine-tune the system’s behavior in various aspects. Hence, we call these inputs tuning parameters. These are (roughly) explained next.

First, some parameters might be specified that take influence on the number of leading diagnoses used for query generation and the necessary computation time invested for leading diagnoses computation. Moreover, some parameter determining the quantity of (pre-)generated queries (of which one is selected to be asked to the user) versus the reaction time (the time it takes the system to compute the next query after the current one has been answered) of the system can be chosen. A further input argument is a query selection measure constituting a notion of query “goodness” that is employed to filter out the “best” query among the set of generated queries. To give the system a criterion specifying when a solution of the interactive KB debugging problem is “good enough”, the user is allowed to define a fault tolerance parameter . The lower this parameter is chosen, the better the (possibly “approximate”) solution that is guaranteed to be found. In case of specifying this parameter to zero, the system will (if feasible) return the “exact” solution of the interactive KB debugging problem. Roughly, the exact solution is given in terms of a solution KB obtained by means of a single solution candidate (minimal diagnosis) that is left after a sufficient number of queries have been answered (and added to the test cases). On the contrary, an approximate solution is represented by a solution KB obtained by means of a solution candidate with sufficiently high probability (where “sufficiently high” is determined by ) at some point where there are still multiple solution candidates available.

Finally, the user may choose between two different modes (static or dynamic) of determining the leading diagnoses. The static diagnosis computation strategy guarantees a constant “convergence” towards the exact solution by “freezing” the set of solution candidates at the very beginning and exploiting answered queries only for the deletion of minimal diagnoses. A possible disadvantage of this approach is the lack of efficient pruning of the used search tree. On the other hand, the dynamic method of calculating leading diagnoses has a primary focus on the preservation of a search tree of small size, thereby aiming at being able to solve diagnosis problem instances which are not solvable by the static approach due to high time and (more critically) space complexity. To this end, more powerful pruning rules are applied in this case which do not permit the algorithm to consider only a fixed set of solution candidates. Rather, the set of minimal diagnoses and minimal conflict sets are generally variable in this case which means that they are subject to change after assignment of an answered query to the test cases.

Like in the case of a non-interactive debugger, an interactive debugging system requires a sound and complete logical reasoner for deciding consistency (coherency) and calculating logical entailments of a KB formulated over the language L.

The workflow in interactive KB debugging illustrated by Figure 1.2 is the following:

1. A set of leading diagnoses is computed by the diagnosis engine (by means of the fault information, if available) using the logical reasoner and passes it to the query generation module.

2. The query generation module computes a pool of queries exploiting the set of leading diagnoses and delivers it to the query selection module.

3. The query selection module filters out the “best query” (often by means of the fault information, if available) and shows it to the interacting user.

4. The user submits an answer to the query.

5. The query along with the given answer is used to formulate a new test case.

6. This new test case is transferred back to the diagnosis engine and taken into account in prospective iterations. If the stop criterion (as per , see above) is not met, another iteration starts at step 1. Otherwise, the solution KB constructed from the currently most probable minimal diagnosis is output.

Contributions of this Work. The contributions of this work are the following:

• This work provides a thorough account of the subject and evolves the theory of interactive KB debugging (for monotonic KBs) by presupposing a reader to have only some basic knowledge of logic. Hence, this work addresses newbies as well as people already familiar with related topics. Whereas the comprehensive theoretical considerations might appeal to the more theoretically

oriented readers such as researchers, the precise and exhaustive description of all discussed algorithms might be interesting from the implementation point of view and might serve more practically oriented people such as programmers or engineers as an algorithmic cookbook. Further on, the extensive illustration of the way algorithms work by examples might also serve a merely superficially interested reader to just receive a rough impression of how KBs might be interactively debugged.

• Except for basics in FOL and PL, this work is self-contained and provides all necessary definitions and proofs to make the topic of interactive KB debugging accessible to the reader.

• To the best of our knowledge, this work provides the most comprehensive and detailed introduction to the field of interactive debugging of (monotonic) KBs. Our previous works on the topic [SFFR12, SF10, RSFF13, FS05, SFRF14c] are more application-oriented and thus abstract from some details and omit some of the proofs in favor of comprehensive evaluations of the presented strategies.

• This is the first work that gives formal and precise definitions of problems dealt with in interactive KB debugging and introduces methods that provably solve these problems. We believe that precise problem statements are the very basis for all further scientific investigations in a field. Hence, we hope that this work can “open” the important subject of interactive KB debugging to a broader audience of interested researchers. This can lead to further progress and improvements in debugging techniques which we deem essential in the light of the growing number of intelligent applications incorporating KBs of growing size and complexity (keyword: The Semantic Web [BLHL01]).

• An in-depth discussion of query computation including computational complexity considerations together with an accentuation of potential ways of improving these methods is given. The investigated methods for query computation have been used also in [SFFR12, RSFF13, SF10, SFRF14c], but have not been addressed in depth in these works.

• We are concerned with the discussion of different ways of exploiting diverse sources of meta information in the KB debugging process from which diagnosis probabilities can be extracted. Our previous works on this topic [SFFR12, RSFF13, SF10, SFRF14c] do not address this matter in a comparable depth.

• We give a formal proof of the soundness of an algorithm QX (based on [Jun04]) for the detection of a minimal conflict set in a KB and we show the correctness (completeness, soundness, optimality) of a hitting set tree algorithm HS (based on [Rei87]) for finding minimal diagnoses in a KB in best-first order (i.e. most probable diagnoses first) which uses QX for conflict set computation only on-demand. We are not aware of any other work that comprises such proofs.

• We establish the theoretical relationship between the widely-used notions of a conflict set and a justification. The former is i.a. used in [dKW87, Rei87, SFFR12, RSFF13] and the latter i.a. in [HPS08, HPS09, HPS10, Hor11, HBP11, HPS12b, SQJH08, Kal06, MS09, SSZ09, NRG12]. As a consequence, empirical results concerning the one might be translated to the other. For instance, since each minimal conflict set is an subset of a justification and there is an efficient (polynomial) method for computing a minimal conflict set given a superset of a minimal conflict set, a result manifesting the efficiency of justification computation for a set of KBs (e.g. [HPS12a]) implies the efficiency of conflict set computation for the same set of KBs. Moreover, we argue that minimal conflict sets are the better choice for our system since these put the focus of the debugger only on the smallest faulty subsets of the KB whereas justifications are better suited in scenarios where exact explanations for the presence of certain entailments are sought.

• Two new algorithms for iterative (leading) diagnosis computation in interactive KB debugging are proposed. One that is guaranteed to reduce the number of remaining solutions after a query is

answered and one that features more powerful pruning techniques than our previously published algorithms [SFFR12, RSFF13] (an evaluation that compares the overall efficiency of our previous algorithms with the ones proposed in this work must still be conducted and is part of our future research).

• We suggest and extensively analyze different methods for the selection of an “optimal” query to ask the user out of a pool of possible queries. We compare a greedy “split-in-half” strategy that proposes queries which eliminate half of the leading diagnoses with a strategy relying on information entropy [Sha48] that chooses the query with highest information gain based on some statistic or (a user’s) beliefs about faults in the KB. Comprehensive experiments manifest that only an average guess of the fault information suffices to reduce the query answering effort for the interacting user, often to a significant extent, by means of the latter strategy compared to the former. Moreover, we demonstrate that both methods clearly outperform a random query selection strategy. The latter result witnesses that incorporation of meta (fault) information into the debugging process is in fact reasonable and might relieve the interacting user of a significant proportion of the effort required without taking into account any meta information.

• Addressing the issue of choosing the suitable query selection method for some given fault information, we present a reinforcement learning query selection strategy. For, reliance upon a strategy (e.g. information entropy) that fully exploits and gains from the given fault information can speed up the debugging procedure in the normal case, but can also have a negative impact on the performance in the bad case where the actual solution diagnosis is rated as highly improbable. As an alternative, one might prefer to rely on a tool (e.g. “split-in-half”) which does not consider any fault information at all. In this case, however, possibly well-chosen information cannot be exploited, resulting again in inefficient debugging actions.

Minimal effort for the interacting user can be achieved if both the query selection method is chosen carefully and the provided fault information satisfies some minimum quality requirements. In particular, for deficient fault information and unfavorable strategy for query selection, we observe cases where the overhead in terms of user effort exceeds 2000% (!) in comparison to employing a more favorable query selection strategy. Since, unfortunately, assessment of the fault information is only possible a-poteriori (after the debugging session is finished and the correct solution is known), we devise a learning strategy (RIO) that continuously adapts its behavior depending on the performance achieved and in this vein minimizes the risk of using low-quality fault information.

This approach makes interactive debugging practical even in scenarios where reliable fault estimates are difficult to obtain. Evaluations provide evidence that for 100% of the cases in the hardest (from the debugging point of view) class of faulty test KBs, RIO performed at least as good as the best other strategy and in more than 70% of these cases it even manifested superior behavior to the best other strategy. Choosing RIO over other approaches can involve an improvement by the factor of up to 23, meaning that more than 95% of user time and effort might be saved per debugging session.

• We come up with mechanisms for efficiently dealing with KB debugging problems involving high cardinality (minimal) diagnoses. In the standard interactive debugging approach described in the first parts of this work, the computation of queries is based on the generation of the set of most probable (or minimum cardinality) leading diagnoses. By this postulation, certain quality guarantees about the output solution can be given. However, we learn that dropping this requirement can bring about substantial savings in terms of time and especially space complexity of interactive debugging, in particular in debugging scenarios where faulty KBs are (partly) generated as a result of the application of automatic systems, e.g. KB (ontology) learning or matching systems [HSNM11, NB12, JMSK09, RP10, JRGZH12, Mei11].

Figure 1.3: Precedence constraints among the parts of this work.

To cope with such situations, we propose to base query computation on any set of leading diagnoses using a “direct” method for diagnosis generation. Contrary to the standard method that exploits minimal conflict sets, this approach takes advantage of the duality between minimal diagnoses and minimal conflict sets and employs “inverse” algorithms to those used in the standard approach in order to determine minimal diagnoses directly from the DPI without the indirection via conflict sets.

We study the application of this direct method to high cardinality faults in KBs and find out that the number of required queries per debugging session is hardly affected for cases when the standard approach is also applicable. However, the direct method proves applicable and able to locate the correct solution diagnosis in situations when the standard approach (albeit one that not yet incorporates the powerful search tree pruning techniques introduced in this work) is not due to time or memory issues.

Organization of this Work. This work is subdivided into seven parts. Figure 1.3 illustrates the precedence constraints among the parts. We want to point out that Parts IV-VI correspond to works that have already been published and are thus self-contained, both from the notation and the content point of view. Parts I-III, on the contrary, are constructive and should thence be read in order.

(Rest of) Part I. In Chapter 2, besides introducing the notation used in this work, we describe the requirements imposed on logical knowledge representation languages L that might be used with our approaches. It should be noted that the postulated properties do not restrict the applications of our approaches very much. For instance, these might be employed to resolve over-constrained constraint satisfaction problems (CSPs) or repair faulty KBs in PL, FOL, DL, Datalog or OWL. Since DL provides the logical underpinning of OWL which has recently received increasing attention due to the extensive research in the field of The Semantic Web [BLHL01], we will also give a short introduction to DL. For, to underline the flexibility of the presented debugging systems in this work, we will illustrate how they work by means of examples involving PL, FOL as well as DL KBs.

In Chapter 3, we first give a formal definition of the KB debugging problem and define a diagnosis problem instance (DPI), the input of a KB debugger, and a solution KB, the output of a KB debugger. Further on, we formally characterize a diagnosis and give the notion of KB validity and what it means for a KB to be faulty. We discuss and prove relationships between these notions and specify properties a DPI must satisfy in order to be solvable by a KB debugger.

We motivate why it makes sense to focus on set-minimal diagnoses instead of all diagnoses, i.e. to stick to “The Principle of Parsimony” [Rei87, BATJ91]. This results in the definition of the problem of parsimonious KB debugging. Then, we prove that solving this problem is equivalent to the computation of a minimal diagnosis. Finally, we explain the benefits of using some background KB in (parsimonious) KB debugging.

In Chapter 4 we describe methods for diagnosis computation. To this end, we first introduce the notion of a (minimal) conflict set, discuss some properties of conflict sets related to the notion of KB validity and give sufficient and necessary criteria for the existence of non-trivial conflict sets w.r.t. a DPI. Subsequently, we derive the relationship between a conflict set and the notion of a justification (a minimal set of formulas necessary for a particular entailment to hold) which is well-known and frequently used, especially in the fields of DL, OWL and The Semantic Web [HPS08, HPS09, HPS10, Hor11, HBP11, HPS12a]. Concretely, we will demonstrate that a minimal conflict set is a subset of a justifica-tion for some negative test case or for some inconsistency (entailment false) or incoherency (entailment for some predicate symbol p of arity k) of the given KB. Moreover, we will learn that, for the debugging tasks we consider, conflict sets are better suited than justifications.

Having deduced all relevant characteristics of (minimal) conflict sets, we proceed to give a description of a method (QX, Algorithm 1) due to [Jun04] which was originally presented as a method for finding preferred explanations (conflicts) in over-constrained CSPs, but can also be employed for an efficient computation of a minimal conflict set w.r.t. a DPI in KB debugging. We discuss and exemplify this algorithm in detail, prove its correctness as a routine for minimal conflict set computation and give complexity results.

Having at our disposal a proven sound method for generation of a minimal conflict set, we continue with the delineation of a hitting set tree algorithm similar to the one originally presented in [Rei87] which enables the computation of different minimal conflict sets by means of successive calls to QX, each time given an (adequately) modified DPI. In this manner, a hitting set tree can be constructed (breadth-first) which facilitates the computation of minimal diagnoses (minimum cardinality diagnoses first). We prove the correctness (termination, soundness, completeness, minimum-cardinality-first property) of this hitting set tree algorithm coupled with the QX method which serves to solve the problem of parsimonious KB debugging.

In order to be able to incorporate fault information into the diagnoses finding process, we deal with the induction of a probability space over diagnoses in Section 4.6. We discuss several ways of constructing a probability space including different sources of fault information. Hereinafter, we detail how diagnosis probabilities can be determined on the basis of some available fault information and how these can be appropriately updated after new observations (in terms of answered queries) have been made. Furthermore, we outline how fault probabilities can be appropriately incorporated into the hitting set search tree in order to guarantee the discovery of minimal diagnoses in best-first order, i.e. most probable ones first. Then, we prove the correctness (termination, soundness, completeness, best-first property) of this best-first diagnosis finding algorithm for parsimonious KB debugging.

Finally, we describe a non-interactive KB debugging procedure (Algorithm 3) that relies on this best-first diagnosis finding algorithm. Some illustrating examples are provided which at the same time reveal significant shortcomings present in non-interactive KB debugging. This motivates the development of interactive KB debugging algorithms.

Readers not theoretically inclined or non-interested in the technical details might well skip Sections 4.2, 4.4.2, 4.5.2 and 4.6 in Part I.

Part II. In Chapter 6, we first discuss how disadvantages of non-interactive KB debugging procedures can be overcome by allowing a user to take part in the debugging process. Then, we define the problem of interactive static KB debugging as well as the problem of interactive dynamic KB debugging which “naturally” arise from the fact that the DPI in interactive KB debugging is always renewed after a new test case has been specified (a new query has been answered). The former problem searches for a solution KB w.r.t. the DPI given as input such that this solution KB satisfies all test cases added during the debugging session and there is no other such solution KB. The latter problem searches for a solution KB w.r.t. the current DPI (i.e. the input DPI including all new test cases added throughout the debugging session so far) such that there is no other solution KB w.r.t. the current DPI.

Next, in Chapter 7, the central term of a query is specified which constitutes the medium for user interaction. Queries are generated from a set of leading diagnoses which is characterized thereafter. The set of leading diagnoses is uniquely partitioned into three subsets by each query. The tuple including these subsets is called q-partition. Subsequently, the reader is given some explanations how the q-partition can be interpreted, and how it relates to a query. In fact, we will prove that the notion of a q-partition can serve as a criterion for checking whether a set of logical formulas is a query or not. After that, we will learn that a query exists for any set of (at least two) leading diagnoses which grants that the presented algorithms will definitely be able to come up with a query without the need to impose any restrictions on which (minimal) diagnoses are computed by the diagnosis engine in each iteration.

Chapter 8 shows a method for the generation of (a pool of) set-minimal queries (Algorithm 4) aiming at stressing the interacting user as sparsely as possible, features in-depth discussions of this method’s properties, proves its correctness, provides complexity results and gives some illustrating examples. Further on, drawbacks of this method are pointed out and possible solutions are discussed.

Subsequently, Chapter 9 deals with the presentation of the central algorithm of this work which implements an interactive KB debugging system (Algorithm 5). First, an overview of the workflow of interactive KB debugging is given, followed by a more comprehensive detailed specification of the algorithm. Some query selection measures are discussed [RSFF13, SFFR12] and optimization versions of the problems of interactive dynamic and static KB debugging are defined where the goal is to obtain the solution to these problems by asking the user a minimal number of queries. Finally, we prove the correctness of the interactive KB debugging algorithm and provide a discussion of its complexity.

Non-theoretically-oriented readers might well skip Sections 8.2, 8.4, 8.5, 8.7 and 9.4 in Part II. Moreover, for the superficially interested reader, it may suffice to concentrate only on Chapter 6 and Sections 7.1, 7.2 and 9.1 in Part II.

Part III. Here, we go into detail w.r.t. the two strategies for iterative diagnoses computation introduced in Part II that might be plugged into Algorithm 5 to solve either the interactive static or dynamic KB debugging problem.

Chapter 11 describes the static method and proves its soundness and completeness w.r.t. the computation of minimal diagnoses w.r.t. the DPI given as an input to the interactive KB debugging algorithm and its optimality w.r.t. the discovery of minimal diagnoses in best-first order (most-probable or minimum cardinality diagnoses first). Incorporation of the static method as a routine for leading diagnosis computation into Algorithm 5 provably solves the problem of interactive static KB debugging.

Chapter 12 details the dynamic method and proves its soundness and completeness w.r.t. the computation of minimal diagnoses w.r.t. the current DPI and its optimality w.r.t. the discovery of minimal diagnoses in best-first order (most-probable or minimum cardinality diagnoses first). Employing the dynamic method as a routine for leading diagnosis computation in Algorithm 5 provably solves the problem of interactive dynamic KB debugging.

The practically oriented reader or the one that is willing to believe that the presented iterative diagnosis computation techniques in fact work as claimed might skip Sections 11.4 as well as 12.4 in Part III.

Part IV. In this part, we suggest and extensively analyze different methods for the selection of an “optimal” query (see above). The material dealt with in Part IV is based on the publications [SFFR12, SF10] where the former was published in the journal Web Semantics: Science, Services and Agents on the World Wide Web and the latter in the Proceedings of the 9th International Semantic Web Conference (ISWC 2010).

Part V. The reinforcement learning query selection strategy (RIO) that makes the presented debugging system robust against the usage of low-quality fault information is presented and thoroughly analyzed in this part which is based on the works [RSFF13, RSFF12, RSFF11, SRF11] published in Web Reasoning and Rule Systems (RR-2013), in the Proceedings of the 7th International Workshop on Ontology Matching (OM-2012), in the Proceedings of the Joint Workshop on Knowledge Evolution and Ontology Dynamics 2011 (EvoDyn2011) and in DX 2011 - 22nd International Workshop on Principles of Diagnosis, respectively.

Part VI. This part covers the topic of efficiently dealing with KB debugging problems involving high cardinality faults (see above) and relies on material presented in [SFRF14c, SFRF14a, SFRF14b] and published in the Proceedings of the 21st European Conference on Artificial Intelligence (ECAI 2014), in DX 2014 - 25th International Workshop on Principles of Diagnosis and in the Proceedings of the Third International Workshop on Debugging Ontologies and Ontology Mappings (WoDOOM14), respectively.8

Part VII. To round this work off, we provide a discussion of related work in Chapter 32,9 summarize the contributions of this work in Chapter 33 and deal with our future work topics in Chapter 34.

2.1 Assumptions

The techniques described in this work are applicable for any logical knowledge representation formalism L for which the entailment relation is

1. monotonic: is given when adding a new logical formula to a KB cannot invalidate any entailments of the KB, i.e. implies that ,

2. idempotent: is given when adding implicit knowledge explicitly to a KB does not yield new entailments of the KB, i.e. and implies and

3. extensive: is given when each logical formula entails itself, i.e. for all ,

and for which

4. reasoning procedures for deciding consistency and calculating logical entailments of a KB are available,

where are logical formulas and is a setof logical formulas formulated

over the language is to be understood as the conjunction . Notice that the elements of a KB are called quite differently in literature. Possible denotations are logical formula (e.g. [KK06]), well-formed formula (e.g. [CL73]), (logical) sentence or axiom (e.g. [RN10]) and axiom (in most of the description logic literature, e.g. [BCM07]). We will mainly stick to the term formula (sometimes axiom) to refer to the elements of a KB. As the logic will be clear from the context in the sequel, we will omit the index L when referring to formulas or KBs over L throughout the rest of this work.

2.2 Considered Logics

To underline the general character of this work, we will illustrate our approaches using example diagnosis problem instances expressed in different logical languages. In this section we give notational remarks concerning these different logics used, namely propositional logic (PL), first-order logic (FOL) as well as description logic (DL). Whereas we assume the reader to be familiar with FOL and PL (a good introduction to PL and FOL can be found in [CL73]), we will give a short introduction to DL.

Remark 2.1 It is important to notice that the usage of DL as well as FOL examples throughout this work should not suggest that the Properties 1 – 4 stated above are satisfied for any DL or FOL language L. In fact, it is well-known by the theorems of Church and Turing (cf. [Men09]; the original works are [Chu36, Tur37]) that FOL is not decidable in general, i.e. Property 4 above is not met. Also in the case of DL, which subsumes a range of different logical languages featuring different expressivity and thus different computational complexity of reasoning procedures, there are languages which are undecidable. For instance, a DL language allowing the formalism of equality role-value-maps which facilitates the expression of concepts like “persons whose co-workers coincide with their relatives” can be proven undecidable [BCM07, SS89].

Property 4 is satisfied, for example, for the DL language SROIQ which is the logical underpinning of OWL 2 [GHM08]. However, the complexity (2-NEXPTIME-complete [Kaz08]) of logical reasoning is intractable in the worst case for this language which implies the intractability of our methods in the worst case. Nevertheless, other DL languages applied with similar systems as those described in this paper have been showing reasonable performance [SFRF14c, RSFF13, SFFR12]. Also from the theoretical point of view, there are DL languages that allow for efficient reasoning. One example is the OWL 2 EL profile which enables polynomial time reasoning [BBL05]. For this language, the efficient reasoning service ELK has been presented by [KKS14]. For FOL, datalog is an example of a decidable sublanguage where reasoning is efficient [RN10]. Further, restricted sublanguages of FOL can often be translated to some DL language wherefore DL positive results concerning the decidability of reasoning as well as complexity results can be adopted for these restricted FOL languages [BCM07, chapter 4] [Bor96].

Moreover, we want to point out that the practical efficiency of our systems depends strongly on the practical performance (which might be by far better than suggested by the worst case reasoning complexities) of the reasoning services called by our algorithms since the reasoning services are used as a black-box (as mentioned in Chapter 1). Possible strategies for improving the reasoning efficiency in the black-box setting are briefly discussed in Chapter 34.

Ontologies and The Semantic Web

Ontologies are KBs that formally and explicitly represent common knowledge about a domain in the form of individuals, concepts (set of individuals) and roles (binary relationships between individuals). As, in the last decade, extensive research has been done in the area of The Semantic Web [BLHL01] making (automatic) ontology development tools and reasoning services more efficient, ontology engineering for the Semantic Web is on the upswing. The Semantic Web aims at the enrichment of unstructured information on the web by semantic meta data which should facilitate the usage of the web as structured database of knowledge of all kinds where computers are able to “understand” this structured data, establish relationships between different data sources, combine information from different data sources and (most essentially) derive new (implicit) knowledge from the structured data. At this, ontologies are the key to a common vocabulary used for the semantic meta data. Ontologies are employed to precisely define the meaning of different terms, state relationships between different terms and to introduce new terms by means of already specified ones.

The constantly increasing number of people creating ontologies of increasing size (examples were given in Chapter 1) results in more and more (faulty) ontologies which constitute useful application scenarios and test cases for our approaches. For that reason, we also want to use ontology engineering for The Semantic Web as a concrete use case for the presented work. The standard knowledge representation formalism for ontologies is OWL 2 [MPSP09, GHM08] which relies on DL. A short introduction to DL is given next.

Description Logic

Description Logic (DL) [BCM07] is a family of knowledge representation languages with a formal logic-based semantics that are designed to represent knowledge about a domain in form of concept descriptions. The syntax of a description language L is defined by its signature and a set of constructors. The signature of L corresponds to the union of possibly disjoint sets and , where contains all concept names (unary predicates), comprises all role names (binary predicates) and is the set of all individuals (constants) in L. Each concept and role description can be either atomic or complex. The latter ones are composed using constructors defined in the particular language L. A typical set of DL constructors for complex concepts includes conjunction , disjunction , negation , existential and value restrictions, where A, B are concept descriptions and .

Axioms are statements of knowledge that must be true in a domain. An ontology K is defined as a tuple (T , A), where T (TBox) is a set of terminological axioms and A (ABox) a set of assertional axioms. Each TBox axiom is expressed by a general concept inclusion , a form of logical implication, or by a definition , a kind of logical equivalence, where A and B are concept descriptions or role descriptions. ABox axioms are used to assert properties of individuals in terms of the vocabulary defined in the TBox, e.g. concept A(x) or role r(x, y) assertions, where A is a concept description, r a role description, and .

The semantics of a description language is given in terms of interpretations consisting of a non-empty domain and a function that assigns to every atomic concept a set , to every atomic role a set and to every individual some value . The interpretation function is extended to complex concept descriptions by the following inductive definitions:

where and are predefined concepts; the former is the universal concept and the latter the bottom concept.

The semantics of axioms is defined as follows for (1) TBox and (2) ABox axioms: (1) Interpretation I satisfies iff and it satisfies iff . (2) A(x) is satisfied by I iff and r(x, y) is satisfied iff . An interpretation I is a model of K = (T , A) iff it satisfies all TBox axioms in T and all ABox axioms in A. An ontology K is consistent iff it has a model. A concept A (role r) is satisfiable w.r.t K iff there is a model I of K with ). An ontology K is coherent iff all concepts and roles occurring in K are satisfiable. An axiom is entailed by K iff is true in all models I of K. For a set of axioms X we write K |= X as a shorthand for for all .

Usually description logic systems provide sound and complete reasoning services to their users. Besides verification of coherency and consistency of K and satisfiability checking of concepts, reasoner tasks include classification and realization. Classification determines, for each concept name A occurring in K, most specific (general) concepts that subsume (are subsumed by) A. A concept A subsumes (is subsumed by) a concept B iff ). Classification is employed to build a taxonomy of concepts in K. Realization, given an individual name x occurring in K and a given set of concepts in K (usually all concepts in K), computes the most specific concepts from the set such that for all i = 1, . . . , n. The most specific concepts are those that are minimal w.r.t. the

subsumption ordering .

Example 2.1 The example KB given in the Introduction (Chapter 1) can be equivalently represented in DL (cf. Remark 2.1) as follows:

where Res is the concept symbol with equivalent meaning as the predicate symbol res, the role symbol writes corresponds to the equally named binary predicate, Paper to paper, and so on. Notice that axiom 2.2 states that the domain of writes is Res.

2.3 Notational Remarks10

General Notational Conventions. Throughout this work, the nomenclature given by Table 2.1 is used (many of the designators in the table will be explained later in this work). We will mainly refer to an ontology by the term KB.

In order to make a clear distinction between scalars and functions, we denote all scalars g by g and all functions g by g(). If an ordered list occurs in a set operation, then this list is interpreted as a (non-ordered) set. For example, let L := [1, 3, 4, 2] be an ordered list; then yields the set {1, 2, 3}.

Notational Convention for PL (cf. [RN10]). We use uppercase letters A, B, . . . to denote atoms and the standard logical connectives to build PL formulas from atoms. The operator precedence we use is , , from highest to lowest. Given a PL KB K and a PL formula ax, we call and the signature of K and the signature of ax, respectively. The former comprises all atoms occurring in K and the latter all atoms occurring in ax.

Notational Convention for FOL (cf. [CGT89]). Variables are denoted by uppercase letters; constants and predicate symbols are denoted by strings beginning with a lowercase letter11. Recalling the example KB given in Chapter 1, X, Y are variables, pam is a constant and res, writes, paper, secr and gen are predicate symbols. FOL formulas are built from the standard logical connectives described for PL above. The operator precedence we use for FOL formulas is the same as stated above12. The precedence of quantifiers is such that a quantifier outside of any parenthesized expression holds over everything to the right of it; if occurring in a parenthesized expression, a quantifier holds over everything to the right of it within this expression. For example, is equivalent to (i.e. “for each professor there is at least one secretary”) and not to (i.e. “if everybody is a professor, then there is at least one secretary”).

Given a FOL KB K and a FOL formula ax, we call and the signature of K and the signature of ax, respectively. The former comprises all predicate, function and constant symbols occurring in K and the latter all predicate, function and constant symbols occurring in ax. The signature of the example KB given in Chapter 1 is {res, writes, paper, secr, gen, pam} and the signature of formula 1.2 of this KB is {writes, res}.

Remark 2.2 By analogy with the definition of coherency in DL (see Section 2.2), we call a FOL KB K incoherent iff for some k-place predicate symbol p in the signature of K where .

Remark 2.3 We want to point out that whenever we will speak of entailment computation we address the invocation of a sound reasoning service that is guaranteed to terminate after finite execution time and returns a finite number of entailments for any KB given as input (cf. Remark 2.1). Similarly, when we say that all entailments of a KB are computed, we always refer to a finite set of entailments of certain types output by such a reasoning service. Examples of such entailment types regarding DL are the (a) classifi-cation and (b) realization entailments, by which we mean (a) all the subsumption relationships between concept names appearing in the KB, i.e. entailments of the form for concept names and (b) all the concept names instantiated by a given individual for all individuals appearing in the KB, i.e. entailments of the form C(a) for concepts names and individual names .

Table 2.1: Symbols and abbreviations used throughout this work (cf. footnote 10).

KB debugging can be seen as a test-driven procedure comparable to test-driven software development and debugging, where test cases are specified to restrict the possible faults until the user detects the actual fault manually or there is only one (highly probable) fault remaining which is in line with the specified test cases. In this chapter, we want to study the theory of (non-interactive) KB debugging, present and discuss mechanisms that can be employed for the debugging of KBs and reveal drawbacks of such systems. In (non-interactive) KB debugging we assume test cases fixed during the debugging procedure. That is, a user might specify a set of test cases offline, run a debugging system and investigate the output solution(s). In case no satisfactory solution has been returned, some additional test cases might be defined offline before the debugger might be invoked again.

The inputs to a KB debugging problem can be characterized as follows: Given is a KB K and a KB B (background knowledge), both formulated over some logic L complying with the conditions 1 – 4 given in Chapter 2. All formulas in B are considered to be correct and all formulas in K are considered potentially faulty. does not meet postulated requirements R where {consistency{coherency, consistency} or does not feature desired semantic properties, called test cases.13 Positive test cases (aggregated in the set P) correspond to desired entailments and negative test cases (N ) represent undesired entailments of the correct (repaired) KB (along with the background KB B). Each test case and is a set of logical formulas over L. The meaning of a positive test case is that the correct KB integrated with B must entail each formula (or the conjunction of formulas) in p, whereas a negative test case signalizes that some formula (or the conjunction of formulas) in n must not be entailed by the correct KB integrated with B.

Remark 3.1 In the sequel, we will write K |= X for some set of formulas X to denote that K |= ax for all and to state that for some .

The described inputs to the KB debugging problem are captured by the notion of a diagnosis problem instance:

Definition 3.1 (Diagnosis Problem Instance). Let

be a KB over L,

• P, N sets including sets of formulas over L,

consistencycoherency, consistency},

be a KB over L such that and B satisfies all requirements ,

• the cardinality of all sets K, B, P, N be finite.

Then we call the tuple a diagnosis problem instance (DPI) over L.14

Note that, for now, we do not make any assumptions about the contents of the sets K, B, P and N that go beyond Definition 3.1. So, it might be well the case, for example, to specify a DPI according to Definition 3.1 for which there are no solutions or for which only trivial solutions exist. Later on, we will discuss properties a DPI must fulfill to guarantee existence of solutions for it.

We define a solution KB for a DPI as follows:

Definition 3.2 (Solution KB). Let be a DPI. Then a KB is called solution KB w.r.t. , written as , iff all the following conditions hold:

A solution KB w.r.t. a DPI is called maximal, written as , iff there is no solution KB such that .

Now, the problem of KB debugging can be formalized:

Problem Definition 3.1 (KB Debugging). Given a DPI , find a solution KB w.r.t. .

Note that basically any KB that meets conditions (3.1) - (3.3) is a solution KB in the sense of Definition 3.2. Hence, does not even need to have a non-empty intersection with K. Only the postulation of maximality of a solution KB (as detailed later in Section 3.1) establishes a relationship to the given KB K.

Remark 3.2 Let . Then, conditions (3.1) - (3.3) can be reduced to conditions (3.2) and (3.3) if

• given R = {consistency} or

• is k-place predicate symbol in in case R = {consistency, coherency}.

This holds because a KB K is inconsistent iff K |= {false} and K is incoherent iff some predicate symbol in must be false for any instantiation. Notice that the latter must hold for all predicate symbols in and not only in K (see Example 3.1). For PL and DL, the definitions of N are analogous (cf. Chapter 2), but for PL coherency is not defined wherefore only the first bullet is relevant for PL. In what follows we will stick to the more explicit characterization of a solution KB given by Definition 3.2.

Example 3.1 Let a DL DPI be defined as

Then, , but there is some concept , but , which is unsatisfiable w.r.t. . Since we want a solution KB integrated with B to meet the conditions (3.1) - (3.3), K is not a solution KB w.r.t. despite the fact that it is perfectly consistent and coherent as an isolated KB.

Whereas the definition of a solution KB refers to the desired properties of the output of a KB debugging system, the following definition can be seen as a characterization of KBs provided as an input to a KB debugger. If a KB is valid w.r.t. the background knowledge, the requirements and the test cases, then finding a solution KB w.r.t. the DPI is trivial. Otherwise, obtaining a solution KB from it involves modification of the input KB and subsequent addition of suitable formulas. Usually, the KB K part of the DPI given as an input to a debugger is assumed to be invalid w.r.t. this DPI.

Definition 3.3 (Valid KB). Let be a DPI. Then, we say that a KB is valid w.r.t. iff does not violate any and does not entail any . A KB is said to be invalid (or faulty) w.r.t. iff it is not valid w.r.t. .15

Intuitively, if a KB K is faulty w.r.t. , then there is at least one incorrect formula in K that needs to be corrected or deleted; if a KB K is valid w.r.t. , a solution KB can be directly obtained by simply extending K by the set of all sentences comprised in positive test cases. Note, however, that K being valid w.r.t. does not necessarily mean that entails any .

Proposition 3.1. Let be a DPI. Then, iff is valid w.r.t. .

Proof. “”: If is a solution KB, then meets all as per condition (3.1) and does not entail any as per condition (3.3). Hence, is valid w.r.t. .

“”: If is valid w.r.t. , then meets all , i.e. meets condition (3.1). Moreover, for all , i.e. meets condition (3.3). By extensiveness of the used language for all , i.e. condition (3.2) is fulfilled by . Thus, is a solution KB.

Definition 3.4 (Extension). Let be a DPI over L and . A set of formulas E over L is called an extension w.r.t. and , written as , iff is a solution KB w.r.t. .

Definition 3.5 (Diagnosis). Let be a DPI. A set of formulas is called a diagnosis w.r.t. , written as , iff there exists some , i.e. is a solution KB w.r.t. .

A diagnosis D w.r.t. is minimal, written as , iff there is no such that is a diagnosis w.r.t. . A diagnosis D w.r.t. is a minimum cardinality diagnosis w.r.t. iff there is no diagnosis w.r.t. such that . Proposition 3.2. Let be a DPI. Then, iff K \ D is valid w.r.t. .

Proof. “”: If D is a diagnosis w.r.t. , there is some extension E w.r.t. D and , which implies that is a solution KB w.r.t. . Now, assume that K \ D is not valid w.r.t. . By Proposition 3.1, this means that is not a solution KB. Hence, violates some or entails some . As is a solution KB, we have that for all . So, by idempotency of which violates some or entails some . By monotonicity of also violates some or entails some whereby is not a solution KB which is a contradiction.

“”: If K\D is valid w.r.t. , then does not violate any and does not entail any . Since also entails each positive test case by extensiveness of L, we can conclude that is a solution KB. By Definition 3.4, and thus D is a diagnosis w.r.t. .

In other words, D is a diagnosis w.r.t. iff meets all requirements, i.e. consistency and/or coherency, as per condition (3.1), does not entail any negative test cases as per condition (3.3), and the positive test cases can be added to without violating any of the conditions (3.1) or (3.3).

From a given DPI , a solution KB can be obtained by a deletion and an expansion step. The deletion step involves the elimination of a diagnosis from K. Note that, due to monotonicity of L, only deletion (and not expansion) of the KB can effectuate a repair of inconsistencies, incoherencies and unwanted entailments. Note, if K is already valid w.r.t. , then D can be set to and the deletion step can be omitted. The expansion step aims at the fulfillment of positive test cases P, i.e. condition (3.2), which is not necessarily the case after the deletion step. In fact, some new logical sentences may need to be added to to grant entailment of all positive test cases.

Corollary 3.1. Let D be a diagnosis w.r.t. . Then there is a set of logical sentences over L such that:

Proof. The proposition of the corollary is a direct consequence of Definition 3.2 and Definition 3.5.

From the point of view of a solution KB w.r.t. is a diagnosis w.r.t. and is one possible extension w.r.t. D and .

Proposition 3.3. For each solution KB w.r.t. there is a diagnosis w.r.t. and an extension E w.r.t. D and such that and .

Proof. Let be a solution KB w.r.t. . Then can be written as . Let and , then . Further on, holds and E is a set of logical sentences such that . Therefore, and .

Corollary 3.2. The (non-)existence of a diagnosis w.r.t. is equivalent to the (non-)existence of a solution KB w.r.t. .

Proof. Proposition 3.3 shows that there is a diagnosis for each solution KB. By Definition 3.5, there is also a solution KB for each diagnosis.

The next Proposition gives sufficient and necessary criteria for the existence of a solution, i.e. a diagnosis or a solution KB, respectively, for a given DPI.

Proposition 3.4. Let be a DPI. Then, a diagnosis D w.r.t. exists iff

fulfills r and

• ∀ B ∪ ̸|= n.

Proof. “”: Let us define D := K. Then . Consequently, X satisfies each as per condition (3.1), for each as per condition (3.3), and finally X |= p for each by extensiveness of L and thus meets condition (3.2). So, X is a solution KB w.r.t. wherefore D must be a diagnosis.

“”: Let be some diagnosis w.r.t. . Then, by definition of a diagnosis, there is some solution KB w.r.t. . Then for all by condition (3.2), which implies that does not feature any new entailments compared to by idempotency of L. So, holds. Now, for arbitrary , since we have that , and, by monotonicity of L, that . Analogously, for any , because satisfies r, it must be true that satisfies r and, by monotonicity of L, that satisfies r.

Definition 3.6 (Admissible DPI). We call a DPI admissible iff there is at least one diagnosis .

A non-admissible DPI may arise in a situation where a user specifies test cases manually. For this procedure a similar error-proneness as for the user’s formulation of KB formulas can be assumed. And there are lots of pitfalls to escape, as Proposition 3.4 shows. In particular, the specified test cases in P and N must be “compatible” with each other, i.e. positive test cases must not contradict negative ones. For example, adding and to P and to N leads to a contradiction between P and N and consequently to the non-admissibility of a DPI comprising P and N . Furthermore, the background KB B which is considered as correct, must indeed be correct, at least in terms of R; and negative test cases must be specified in a way not to postulate non-entailment of knowledge specified in B. A counterexample is and N := {{C(x)}}. And third, the union of positive test cases together with B must be in compliance with R, particularly the formulas in P must not be inconsistent or incoherent. Because the union of positive test cases can be viewed as an own KB since all logical sentences occurring in some must be true in the solution KB. So, in a setting where test cases are specified manually, faults occur as likely in as they do in K.

The debugging system presented in this work, however, guarantees by automatic test case generation that admissibility of a DPI is satisfied at any time, provided that an admissible DPI is given as an initial input to the debugging system.

Remark 3.3 In case of a present DPI which is non-admissible, the DPI must be properly modified before it can be used with our debugging system. More concretely, the sets B, P as well as N must be prepared in a way that the two conditions in Proposition 3.4 are satisfied. When supposing that B is an already approved and correct KB (which is a reasonable assumption for a KB used as background knowledge during a debugging session), then there are (at least) the following ways to obtain an admissible DPI from a given non-admissible DPI without modifying B.

(a) One straightforward way to achieve that is the deletion of all manually specified test cases from P and N . After that, both sets are either the empty set (if no automatic test cases, e.g. from former debugging sessions were included in these sets) or comprise only automatically generated test cases. The former case yields an admissible DPI independently of K by the property of B to not violate any requirements in R (see Definition 3.1). That the latter case implies the admissibility of the DPI is a property of the debugging system described in this work (as we will show later by Corollary 7.3).

(b) Another way to resolve the non-admissibility of a DPI is to first check whether is admissible (verification of Proposition 3.4 by means of a reasoning service). If so, it is clear that B does not conflict with N . Then, a debugger (like the one presented in this work) can be exploited to find an as small as possible subset of the set of all formulas occurring in the positive test cases, the removal of which causes the DPI to become admissible. This would be accomplished by the computation of a minimal diagnosis w.r.t. and the usage of the modified admissible DPI instead of the original one. In this case, only a set-minimal set of formulas that were desired entailments of the user are lost. This modification is possible in polynomial time apart from the reasoning costs, i.e. by means of a polynomial number of calls to a reasoner (cf. Chapter 1).

(c) Otherwise, i.e. if B already conflicts with the negative test cases N , then an algorithm similar to Algorithm 1 (that will be presented in Section 4.4.1) can be employed to determine a maximal subset of N w.r.t. set inclusion such that B will not be in conflict with . This approach also requires only a polynomial number of calls to a reasoner (cf. Proposition 4.8). If the resulting modified DPI is not yet admissible, i.e. after adding the positive test cases to B there are again conflicts with , method (b) must be executed in order to finally obtain an admissible DPI.

That is, given a non-admissible DPI, there is a transformation achievable in polynomial time which enables the establishment of admissibility involving a set-minimal number of modifications to the given test cases. Thence, in the rest of this work, we will assume that a DPI given as an input to our algorithms is admissible.

In general, there are multiple (minimal) diagnoses for a DPI, i.e. > 1, and there are multiple, in fact infinitely many, extensions for a fixed diagnosis . The task addressed in this work is finding an optimal diagnosis for a given DPI, whereas the identification of an optimal extension w.r.t. that diagnosis and the DPI is not the aim. What we understand by “optimality” of a diagnosis will be addressed in more detail in Part II. Instead, we will content ourselves with finding any extension that enables to formulate a solution KB given a DPI and a diagnosis for that DPI. In fact, the problem of finding a solution KB for a DPI can be reduced to finding a diagnosis for that DPI since a suitable extension can be easily formulated for any diagnosis, as the next proposition shows:

Proposition 3.5. Let be a DPI and . Then is an extension w.r.t. D and .

Proof. Let us assume that there is some and is not an extension w.r.t. D and . By the definition of a diagnosis, this is equivalent to stating that is not a solution KB which in turn means that at least one condition (3.1), (3.2) or (3.3) of Definition 3.2 is violated by . However, the fact that D is a diagnosis implies the existence of some extension that can be added to (K \ D) to obtain a solution KB. This means that conditions (3.1) and (3.3) must be already valid for (K \ D), since, by monotonicity of L, addition of logical sentences E can neither solve inconsistencies or incoherencies necessary for fulfillment of condition (3.1) nor invalidate non-desired entailments as per condition (3.3). As a consequence, condition (3.2) must be violated by . By extensiveness of L it holds that for all whereby we obtain that condition (3.2) is fulfilled which yields a contradiction.

Proposition 3.5 claims that the expansion operation, i.e. identifying a concrete extension for a diagnosis, is trivial, at least for our purposes, namely formulating an extension reflecting only evident entailments given by the set of positive test cases P. Consequently, in order to find a solution KB for some DPI, it is sufficient to concentrate on the deletion step, i.e. on the search for diagnoses.

Note that using as a canonical extension when computing diagnoses does not affect the set of identified diagnoses. In other words, exchanging for in Definition 3.5 yields an equivalent definition. The following corollary proves this statement and summarizes the relationship between the notions diagnosis, solution KB and valid KB.

Corollary 3.3. The following statements are equivalent:

1. D is a diagnosis w.r.t.

2. is a solution KB w.r.t.

3. (K \ D) is valid w.r.t. .

Proof. That (1) is equivalent to (2) follows from Definition 3.5 which states that D is a diagnosis w.r.t. iff there is some set of sentences such that is a solution KB, and from Proposition 3.5 which proves that is an extension w.r.t. any diagnosis D and .

That (1) is equivalent to (3) follows directly from Proposition 3.2 and the equivalence of (2) and (3) has been shown in Proposition 3.1.

3.1 Parsimonious Knowledge Base Debugging

Why are minimal diagnoses interesting? First, the set of minimal diagnoses w.r.t. a DPI captures all the information that explains the unwanted properties, i.e. violation of requirements or test cases, of the DPI. In other words, the minimal diagnoses represent all subset-minimal possibilities to modify a KB in a way it becomes a valid KB w.r.t. the given DPI (e.g. by simply deleting a minimal diagnosis from the KB in the trivial case). By monotonicity of the logic L, each superset of a minimal diagnosis w.r.t. a DPI is a diagnosis w.r.t. this DPI. That is, can be easily reconstructed given . There is however no evidence (in terms of specified requirements and test cases) in a DPI that would justify the selection of a non-minimal diagnosis. That is, if K is a KB and a minimal diagnosis w.r.t. a DPI including K, K \ D does not violate any of the postulated properties that must hold for a KB to be valid w.r.t. this DPI. For that reason, there is no evident need to delete or modify any other sentences in K except for the ones in some minimal diagnosis D.

Second, usually a setting can be assumed where the author of a KB specifies formulas to the best of their knowledge. Hence, the assumption that a formula is rather correct than faulty, or in other words, that the KB author wants to keep as many formulated sentences as possible in a solution KB obtained from a debugger, is practical.

This also motivates the importance of a certain subset of minimal diagnoses, namely minimum cardinality diagnoses, which are the solutions of choice in scenarios where no probabilistic information about the KB authors’ faults is available, e.g. in terms of statistics retrieved from log data of the used IDE (see Section 4.6 for details). In an application where such information is given, minimum cardinality diagnoses might not always be the appropriate choice (for details see Part II). In this case the aim is to find a minimal diagnosis with a maximal probability of including only sentences that are actually faulty (which might not necessarily be a minimum cardinality diagnosis).

Third, minimality of diagnoses will be a necessary condition to guarantee the possibility of discrimination between different (candidate) diagnoses to formulate a solution KB, as will be seen later in Chapter 7.

Fourth, focusing only on minimal diagnoses rather than all diagnoses can greatly reduce the search space for diagnoses and therefore greatly speed up the debugging procedure (cf. [dKW87]).

Projected to the task of KB debugging, namely finding a solution KB w.r.t. a given DPI, this means we are interested in minimal invasiveness, that is making as few formula-deletion-modifications to the input KB K as possible in the course of the performed debugging actions. That is, the actual goal is to find some maximal solution KB for a DPI. Compare with “The Principle of Parsimony” in [Rei87, p. 7] [BATJ91].

Problem Definition 3.2 (Parsimonious KB Debugging). Given a DPI , the task is to find a maximal solution KB w.r.t. .

The next proposition shows that this problem can be reduced to finding a minimal diagnosis.

Proposition 3.6. (i) is a minimal diagnosis w.r.t. for each maximal solution KB w.r.t. .

(ii) If D is a minimal diagnosis w.r.t. , then is a maximal solution KB w.r.t. for all extensions .

Proof. Ad (i): Let be an arbitrary maximal solution KB w.r.t. . The first observation is that is a diagnosis w.r.t. since by the fact that is a solution KB by assumption. Let us assume that there is a diagnosis such that . Since is a diagnosis, it holds per Definition 3.5 that there is an extension such that is a solution KB. Further on, . Since can be written as which is a strict subset of which in turn is a subset of . Consequently, holds, which is by Definition 3.2 a contradiction to the maximality of the solution KB . Thus, is a minimal diagnosis w.r.t. .

Ad (ii): Let D be a minimal diagnosis w.r.t. . Then, by Definition 3.5, there is an extension such that is a solution KB. Let us assume that . We can rewrite as . Since , we have that . Thus, there is a and an extension such that such that . As is a solution KB, this is a contradiction to the minimality of D. Therefore, (*) for all must hold.

Let E be any extension w.r.t. D and . Then we can write and by (*) also . Consequently, (**) . Now, assume that there is a solution KB with the property . By (**), this implies that which means that there is a such that . Now is a solution KB w.r.t. and can be written as . By and since there is a set of formulas such that we have that must hold wherefore is a diagnosis by Definition 3.5. This, however, is a contradiction to the minimality of D. Therefore, must be a maximal solution KB for any .

By claim (i), Proposition 3.6 assures that each maximal solution KB can be found by investigating all minimal diagnoses w.r.t. a DPI. Claim (ii) shows that any solution KB built from a minimal diagnosis is indeed maximal. Thus, finding a suitable minimal diagnosis solves the problem of parsimonious KB debugging completely.

3.2 Background Knowledge

The general debugging setting considered in this work envisions the opportunity for the user to specify some background knowledge B, i.e. a set of formulas that are known (or strongly assumed) to be correct in advance. Note that, in order for the debugging procedure to work soundly, before some background knowledge is incorporated into the DPI, it is necessary to verify its conformance with the postulated requirements R (cf. Definition 3.1).We can distinguish between two basic scenarios how background knowledge can be leveraged: (1) We have an initial KB and we know or want to assume that a subset of formulas in is correct, i.e. , and (2) we have an initial KB and some background knowledge disjoint from , i.e. .

Example use cases for scenario (1) are situations where a user knows that a subset of formulas B in K is definitely sound or wants to restrict the scope of debugging to a particular part of the KB. Concretely, this may occur, for instance, when B is the result, i.e. the finally output solution KB , of a former successful debugging session and K is a further development of , or in a collaborative setting where many users are involved in the development of K and one of them may want to debug only formulas authored by herself and not touch foreign formulas, which are thus assumed as correct and assigned to B. In (1), and partition the original KB into a set of correct and a set of possibly incorrect formulas, respectively. The corresponding DPI would thus be for some sets of test cases P and N . Note that this DPI does meet the necessary condition (cf. Definition 3.1) as . So, in the debugging session, only is used to search for diagnoses, which can reduce the search space substantially. Though, B is incorporated in the calculations throughout the KB debugging procedure, but no formula in B may take part in a diagnosis. The advantage of this over simply not considering the formulas in B at all is, that the semantics of formulas in B is not lost and can be exploited, e.g., to grant the desired semantic properties also in the context of existing approved knowledge or to facilitate a greater choice of queries to interact with a user, which can be exploited to ask queries with lower cardinality or involving less complex formulas (see Chapter 7 for details on queries).

In scenario (2), the corresponding DPI looks like for some sets of test cases P and N . An application of this scenario could be the reuse of an existing KB to support an increase of the fault detection rate and thus more sustainable debugging. For example, when formulating a KB about a domain, a reference KB B in that domain that is thoroughly curated by experts could be leveraged. The use of such a KB B is possible both if is correct as a standalone KB, i.e. is already a solution KB for , or not. In the first case, might still contain formulations conflicting with B. In this vein, in both cases, faults may be detected that would have been missed otherwise.

In this chapter we describe methods for computing minimal diagnoses w.r.t. a given admissible DPI, provide an in-depth theoretical analysis of these methods including correctness proofs and illustrate the presented algorithms by various examples.

4.1 Conflict Sets

The search space for minimal diagnoses w.r.t. the size of which is in general (if all subsets of the KB K are investigated) can be reduced to a great extent by exploiting the notion of a conflict set [Rei87, dKW87, SFFR12].

Definition 4.1 (Conflict Set). Let be a DPI. A set of formulas is called a conflict set w.r.t. , written as , iff is not a solution KB w.r.t. . A conflict set C is minimal, written as , iff there is no such that is a conflict set.

Simply put, a (minimal) conflict set is a (minimal) faulty KB that is a subset of K. That is, a conflict set is one source causing the faultiness of K in the context of . In other words, a valid KB may not include all the formulas of any conflict set.

Corollary 4.1. is a conflict set w.r.t. iff C is invalid w.r.t. .

Proof. If C is a conflict set w.r.t. , then is not a solution KB, i.e. violates some , some or some . By extensiveness of for all , so must violate some or entail some . Thus, by Definition 3.3, C is invalid w.r.t. .

If is not valid w.r.t. , then violates some or entails some , wherefore . Hence, by Definition 4.1, C is a conflict set w.r.t. .

Consequently, a conflict set C along with the background knowledge B either violates some , entails some , or yields to a violation of some or entailment of some if all formulas comprised by the positive test cases are added to C. Any KB K that is not valid w.r.t. is itself a conflict set and includes at least one minimal conflict set.

Proposition 4.1. Let be a DPI. Then, K is not valid w.r.t. iff K includes at least one minimal conflict set w.r.t. .

“”: Let K include at least one minimal conflict set w.r.t. . Then, by Definition 4.1, there is some such that is not a solution KB. Hence, by the monotonicity of cannot be a solution KB either. So, by Proposition 3.1, K is not valid w.r.t. .

As a consequence, a complete and sound method for computing minimal conflict sets w.r.t. a DPI can be used to decide validity of K w.r.t. . Moreover, such a method can be used to decide whether a given DPI is admissible, i.e. has solutions. For, if a DPI is admissible and the given KB is invalid w.r.t. this DPI, then there cannot be an empty conflict set. In other words, if the empty KB is a conflict set – or, equivalently, an empty conflict set exists w.r.t. a DPI –, then the DPI is not admissible.

Proposition 4.2. Let be a DPI and K be invalid w.r.t. . Then, there exists a minimal conflict set w.r.t. iff is admissible.

Proof. Since K is not valid w.r.t. , there must be at least one conflict set w.r.t. by Proposition 4.1. Assume that there exists a minimal conflict set w.r.t. . This can be true iff is not a (minimal) conflict set w.r.t. . By Corollary 4.1 and Definition 3.3, this is equivalent to the fact that does not violate any and does not entail any . By Proposition 3.4, this holds iff there exists a diagnosis w.r.t. . By Definition 3.6, this is equivalent to being admissible.

The following proposition provides information about the relationship between (minimal) conflict sets and the background knowledge as well as the positive test cases.

Proposition 4.3. Let be a DPI and C a conflict set w.r.t. . Then the following holds:

1. C ∩ B = ∅.

2. If C is a minimal conflict set w.r.t. , then .

Proof. 1): holds since (Definition 4.1) and (Definition 3.1).

2): Assume that C is a minimal conflict set w.r.t. and . Since C is a conflict set, we have that violates some or entails some by Corollary 4.1 and Definition 3.3. Since and , this implies that is a conflict set w.r.t. which in turn implies that which is a contradiction.

4.2 Conflict Sets versus Justifications

The notion of a conflict set is closely related to the notion of a justification [HPS08, HPS09, HPS10, Hor11, HBP11, HPS12a] which is frequently adopted in the field of the Semantic Web (cf. Section 2.2) in order to find minimal explanations for particular entailments in DL ontologies. Thus, the paradigm of a justification can be a useful aid in the debugging of faulty ontologies [Kal06]. Note that sometimes justifications are referred to as MinAs (Minimal Axiom Sets) [BP08] or MUPS (Minimal Unsatisfiabil-ity Preserving Sub-TBoxes) [SHCH07] where the latter term is mostly used in the context of ontology debugging. The notion of a (minimal) conflict set, on the other hand, has been mainly adopted in the Diagnosis community [Rei87, dKW87, PW03, WSM02, FFJS04]. In this section we want to establish a relationship between these two widely used instruments used for debugging. It will turn out that both terms are strongly related, but in debugging systems like the ones proposed in our work conflict sets are better suited as they automatically focus only on the minimal explanations for faults in a KB.

For example, the author of [Kal06] i.a. discusses the use of justifications to aid the debugging of incoherent ontologies, i.e. ontologies that include unsatisfiable concepts (cf. Section 2.2). If there are multiple unsatisfiable concepts, then some of these might be only unsatisfiable due to the unsatisfiability of another concept. Assume, for instance, an incoherent DL KB . In K there are two unsatisfiable concepts A and B where A’s unsatisfiability is dependent on B’s unsatisfiability. Using the terminology of [Kal06, Hor11], A would be called a purely derived unsatisfiable concept whereas B would be called a root unsatisfiable concept. Because the (only) justification for the unsatisfiability of A is whereas the (only) justification for the unsatisfiability of B is . Therefore, [Kal06] proposes to resolve root unsatisfiable concepts first since this might resolve some (purely) derived concepts as well, as in this example. However, finding out whether a concept is root or derived involves the computation of justifications for all unsatisfiable concepts in a KB. On the other hand, reliance on minimal conflict sets would implicate a direct focus on the faultiness (in this example: the incoherency) of the KB and not necessarily on the exact explanations of all unsatisfiable concepts that cause the incoherency. In this vein, no justification for a purely derived concept can be a minimal conflict set. So, the computation of minimal conflict sets involves only the determination of those justifications for faults that must necessarily be resolved. Therefore, for the given example, the only minimal conflict set is .

A justification for a given formula (axiom) relative to a KB is a (subset-)minimal subset of the KB that entails the given formula.

Definition 4.2 (Justification for a Formula). [KPHS07] Let K be a KB and a formula, both over L. Then is called a justification for w.r.t. K, written as , iff and for all it holds that .

Since we consider test cases which are sets of formulas over L, we generalize the definition of a justification as follows:

Definition 4.3 (Justification for a Set of Formulas). Let be KBs over L. Then is called a justification for w.r.t. K, written as , iff and for all it holds that .16

In order to express the connection between justifications and conflict sets, we require yet another generalization of this definition. To this end, the following definition characterizes a justification for a set X of KBs relative to a KB K as a (subset-)minimal subset of K such that this subset entails some KB in X.

Definition 4.4 (Justification for a Set of Sets of Formulas). Let K be a KB over L and X a set of KBs over L. Then is called justification for X w.r.t. K, written as , iff for some and for all it holds that for all .

Based on Definition 4.4, the relation between conflict sets and justifications is captured by the following Proposition 4.4. Intuitively, any conflict set w.r.t. is the part of a justification for a fault that is relevant for the debugging task, where fault refers to an inconsistency (and/or incoherency) and/or a negative test case entailed by . Since debugging focuses on the deletion of KB formulas only, “relevant” in this context refers to the subset of the justification that does not contain any sentences in B and , but solely sentences from K. Importantly, there may be justifications, in general, the relevant subset of which is not a minimal conflict set. The reason why this case can arise in spite of the set-minimality of justifications is that the relevant part of a justification (for some set of sentences , e.g. a negative test case ) may be a superset of the relevant part of another justification (for some other set of sentences , e.g. another negative test case ) whereas both justifications are not in a subset-relationship (i.e. contain different sentences from B and/or ). This circumstance is illustrated by the following example:

Example 4.1 Let a DPI be defined as

We have that is consistent and thus no requirement in R is violated. But, the two negative test cases are both entailed by wherefore K is invalid w.r.t. . The set of justifications for the violation of the first negative test case is ; for the second one it is . The relevant subset of the justification in is (since is in B) whereas the relevant subset of the justification in is , , i.e. despite that there is no set subset-relationship between and . Hence, there are two justifications that explain the invalidity of K w.r.t. , but there is only one minimal conflict set w.r.t. .

So, generally, the set of minimal conflict sets w.r.t. a DPI is a subset of the set of justifications for faults in , which is due to the focus on just the parts of justifications that are relevant for the KB debugging task.

Proposition 4.4. Let be a DPI. Additionally, let

(b) if R = {consistency}.17

Then the following holds:

1. If C is a minimal conflict set w.r.t. , then there is some such that .

2. For all it is true that is a conflict set w.r.t. , but not necessarily a minimal one.

Proof. 1): Assume that and for all it holds that . There are two cases to distinguish between: (a) there is some sentence in that is not in C and (b) there is some sentence in C that is not in .

Let us first assume (a), i.e. for all it holds that there is some sentence ax in that is not in C. Additionally, assume there is a such that . We can write J as for and . Since it must hold in particular that and therefore . However, by assumption, since and , and since and . This is a contradiction. Hence, for all it holds that . Since X captures all and , we can conclude that C is not a conflict set w.r.t. which is a contradiction to .

Let us now assume (b), i.e. for all it holds that there is some sentence ax in C that is not in . Since C is a conflict set and since X captures all and , we have that for some . So, there must be some such that . As , there cannot be any with for arbitrary . This must hold in particular for which implies that which is equivalent to . As (1) (Definition 4.1) and, by Proposition 4.3 and by the fact that , (2) , we can conclude that which is a contradiction since there cannot be a ax in C that is not in .2): If , then, by Definition 4.4, for some and . So, wherefore by monotonicity of L. As and X captures all the reasons why some or some may not be fulfilled (cf. the discussion in Chapter 3), we have that violates some or entails some . This implies that . Since is also true, by Definition 4.1.

To see that holds in general, reconsider Example 4.1 where holds for the justification and the minimal conflict set C.

4.3 The Relation between Conflict Sets and Diagnoses

A minimal conflict set has the property that deletion of any formula in it yields a set of formulas which is correct in the context of B, P, N and R.

Proposition 4.5. If C is a minimal conflict set w.r.t. , then is valid w.r.t. for each .

Proof. Since , it must hold that . Then, by Corollary 4.1, is valid w.r.t. .

Hence, by deletion of at least one formula from each minimal conflict set w.r.t. , a valid KB can be obtained from K. Thus, a solution KB can be obtained by calculation of a hitting set D of all minimal conflict sets in . The Hitting Set problem is defined as follows:

Definition 4.5 (Hitting Set). Let be a set of sets. Then, H is called a hitting set of S iff and for all i = 1, . . . , n.A hitting set H of S is minimal iff there is no hitting set of S such that .

Proposition 4.6. [FS05] A (minimal) diagnosis w.r.t. the DPI is a (minimal) hitting set of all minimal conflict sets w.r.t. .

Now, we want to contemplate two example DPIs and analyze them regarding the their minimal conflict sets and minimal diagnoses:

Example 4.2 In this example, we analyze the PL DPI given by Table 15.3. There are two minimal conflict sets w.r.t. , i.e. .18

Why is a conflict set w.r.t. ? We recall Definition 4.1 and argue as follows to deduce the entailment where (left of the colon: the formulas used in the deduction are underlined; right of the colon: the relevant implications are underlined):

Minimality of is obvious from this argumentation. i.e. we cannot deduce if any one of the formulas 1, 2 or 5 is omitted, and there is no other fault except for the violation of .

Why is a conflict set w.r.t. ? We recall Definition 4.1 and argue as follows to deduce the entailment where (left of the colon: the formulas used in the deduction are underlined; right of the colon: the relevant implications are underlined):

Minimality of is obvious from this argumentation. i.e. we cannot deduce if any one of the formulas 1, 2 or 7 is omitted, and there is no other fault except for the violation of . There are no further minimal conflict sets w.r.t. . This is fairly easy to see since

cannot be inconsistent due to the fact that the only negative literal occurring on the righthand side of an implication is and A does not occur at the righthand side of any implication in ,

• there is no other way to deduce than using a superset of the formulas in or and

• is the only negative test case in N .

Hence, the set of all minimal diagnoses is obtained by computing all minimal hitting sets of (cf. Proposition 4.6).

Example 4.3 In this example, we analyze the DL DPI given by Table 4.2. There are four minimal conflict sets w.r.t. , i.e.

Why is a conflict set w.r.t. ? We recall Definition 4.1 and argue as follows to deduce the entailment where (left of the colon: the formulas used in the deduction are underlined;

right of the colon: the relevant implications are underlined):

Minimality of is follows from this argumentation. i.e. we cannot deduce if any one of the formulas 1, 2 or 5 is omitted, and from the fact that we cannot deduce an incoherency (), inconsistency () or the entailment of any other negative test case for any KB for any .

Why is a conflict set w.r.t. ? We recall Definition 4.1 and argue as follows to deduce that is incoherent and thus violates the requirement (left of the colon: the formulas used in the deduction are underlined; right of the colon: the relevant implications are underlined):

Since we cannot deduce an incoherency (), inconsistency () or the entailment of any negative test case for any KB for any , the minimality of follows.

Why is a conflict set w.r.t. ? We recall Definition 4.1 and argue as follows to deduce that is inconsistent and thus violates the requirement (left of the colon: the formulas used in the deduction are underlined; right of the colon: the relevant implications are underlined):

No inconsistency () or incoherency () can be derived and no negative test case is entailed from any for . Hence, is a minimal conflict set w.r.t. .

Why is a conflict set w.r.t. ? We recall Definition 4.1 and argue as follows to deduce the entailment where (left of the colon: the formulas used in the deduction are

underlined; right of the colon: the relevant implications are underlined):

No inconsistency () or incoherency () can be derived and no negative test case is entailed from any for . Thus, is a minimal conflict set w.r.t. .

Hence, the set of all minimal diagnoses , obtained by computing all minimal hitting sets of (cf. Proposition 4.6), comprises ten minimal diagnoses for i = 1, . . . , 10:

Although the DPI is very small in size, i.e. number of formulas occurring in it is very small, the reader might agree that it is not trivial on the one hand (1) to realize which subsets of this KB K are (minimal) conflict sets, (2) to see that or why a subset of this KB K along with the background knowledge B and the union of the positive test cases is a (minimal) conflict set (cf. [HBP11]), and (3) to assess that there are no further minimal conflict sets w.r.t. . This example gives a little bit of an impression that tool assistance in the debugging of KBs is inevitable especially for real-world KBs that are huge in size and/or complex in terms of the expressivity of the used logic or in terms of their “debugging properties”, i.e. large number and/or size of minimal conflict sets and/or minimal diagnoses.

A means to handle problems (1) and (3) is provided by some method for the computation of a minimal conflict set (e.g. QX given by Algorithm 1 below, see Section 4.4.1) coupled with a hitting set tree algorithm (e.g. HS described by Algorithm 2 below, see Section 4.5) for the systematic computation of different minimal conflict sets, or other mechanisms such as the ALL_JUST_ALG presented in [KPHS07] which computes all justifications for some particular entailment (but, some post-processing of the justifications is necessary to obtain minimal conflict sets, cf. Section 4.2).

Problem (2) and its complexity for humans has been studied in [HBP11] with a focus on justifica-tions in DL or OWL KBs. Since a minimal conflict set can be regarded as the relevant (i.e. potentially faulty) part of a justification for some undesired entailment (i.e. a violated requirement or test case) as we analyzed in Section 4.2, the cognitive complexity model proposed by [HBP11] applies also to minimal conflict sets. Ways to facilitate the understanding of justifications for humans (that might be successfully applied also to conflict sets) have been addressed in [HPS10, HPS09, HPS08]. Moreover, there is an ontology editing browser SWOOP [KPS06] equipped with a strikeout feature [Kal06] that highlights parts of justifications that are relevant for the entailment by striking out all irrelevant parts. This is more or less the automation of our analyses of the conflict sets by underlining the relevant parts of the formulas in this example and Example 4.2.

Table 4.1: Propositional Logic Example DPI

4.4 Methods for Diagnosis Computation

Two common methods employed for the computation of (minimal) diagnoses [SFFR12, RSFF13] are the QuickXPlain algorithm [Jun04] (in short QX) and a hitting set search tree [Rei87, GSW89] (in short HS). Thereby, QX serves as a deterministic method for computing one minimal conflict set w.r.t. a given DPI per call. Since a diagnosis is a hitting set of all minimal conflict sets, more than one minimal conflict set is generally required to compute a diagnosis. Due to its determinism, however, QX always computes the same minimal conflict set for the same input DPI. Thus, in order to compute different (or all) minimal conflict sets, the input to QX needs to be varied accordingly. This can be done by means of HS which serves as a search tree to systematically and successively explore all minimal conflict sets w.r.t. an initially given DPI. Note that often not all minimal conflict sets w.r.t. a DPI are necessary to obtain a minimal diagnosis w.r.t. this DPI. This is the case when different minimal conflict sets overlap, i.e. have a non-empty intersection. In the extreme case, when all minimal conflict sets w.r.t. a DPI share some formulas, then the computation of any single minimal conflict set can suffice to obtain a minimal diagnosis, which is actually even a minimum cardinality diagnosis.

Another approach for computing a minimal conflict set (or justification) is the “expand-and-shrink” algorithm presented in [KPHS07]. However, empirical evaluations and a theoretical analysis of the best and worst case complexity of the “expand-and-shrink” method compared to QX performed in [SFJ08] revealed that the latter is preferable over the former.

Also, alternative strategies for the computation of minimal diagnoses have been suggested. One common method is to avoid the indirection of diagnosis computation via minimal conflict sets and use algorithms that determine diagnoses directly [SU06], i.e. without the necessity to compute conflict sets. This approach has been applied for the non-interactive debugging of ontologies [DQPS11] and constraints [FSZ11]. In our previous work, we adopted such a direct technique for the interactive debugging of KBs [SFRF14c]. The reason why we stick to the conflict-based approach in this work is that we want to present best-first algorithms that figure out minimal diagnoses in descending order of their probability. This is not (systematically) realizable with a direct approach.

Table 4.2: Description Logic Example DPI

4.4.1 Computation of a Minimal Conflict Set

The QX algorithm takes a DPI over some monotonic logic L as input and returns a minimal conflict set w.r.t. as output, if some conflict set exists for the DPI, and ’no conflict’ otherwise.

Monotonic Properties. Basically, QX can be employed to find for an input set X a set-minimal subset that has a certain property prop for problems of completely different nature such as propositional unsatisfiability or over-constrainedness of constraint satisfaction problems. The only postulated prerequisite for QX to work correctly is that prop is a monotonic property. A property is monotonic if and only if the binary function that returns 1 if the property holds for the input set and 0 otherwise is a monotonic function.

Definition 4.6 (Binary Monotonic Function). Let X be a set and be a binary function defined for all subsets of X. Then, f is monotonic iff

So, prop is monotonic iff, given that prop holds for some set , it follows that prop also holds for any superset of . Note that, by simple logical transformation, an equivalent statement can be derived from Definition 4.6; namely that, given that prop does not hold for some set , it follows that prop does not hold for any subset of either.

As inconsistency and incoherency as well as the entailment of some over some monotonic language L are clearly monotonic properties, the following proposition holds.

Proposition 4.7. Let be a DPI. Then, the invalidity of w.r.t. (as per Definition 3.3) is a monotonic property.

By Corollary 4.1, a (minimal) conflict set w.r.t. is a (minimal) invalid sub-KB of K w.r.t. . Therefore:

Corollary 4.2. Let be a DPI. Then, being a conflict set w.r.t. is a monotonic property.

Thus, QX is applicable for the problem of finding a minimal conflict set w.r.t. a DPI. As we shall see later in Chapter 8, another monotonic property will enable us to apply QX also for the minimization of queries asked to an interacting user in the interactive debugging of KBs.

How QX (Algorithm 1) Works. After verifying that the trivial cases, i.e. is already a valid KB w.r.t. or , are not met, a non-empty minimal conflict set w.r.t. , must exist. So, the algorithm enters the recursive procedure QX. Note that the parameters P, N , R of QXare used for validity tests (ISKBVALID, line 9) only and are maintained invariant during the entire recursive execution. In case is not a singleton, i.e. it does not hold for sure that is an element of a minimal conflict set w.r.t. , the idea is to apply a divide-and-conquer strategy to reduce into two subproblems and solve one subproblem first, i.e. find a minimal conflict set for this subproblem, and then the second subproblem. The union of the minimal conflict sets found for the subproblems is then a minimal conflict set for the original problem. This division into smaller problems is recursively executed for each subproblem until the trivial case, i.e. the KB of the subproblem that is analyzed includes only one element, occurs. Then this element is an element of a minimal conflict set w.r.t. the original problem.

Simply put, one can imagine that QX takes , partitions it into and and first considers the DPI with KB and background knowledge (line 16). If the latter already includes a conflict set (second condition in line 9), then can be safely discarded and does not need to be further considered. Instead, is further investigated, i.e. the DPI with KB and background knowledge where and partition . Notice that, in this way, sentences can be dismissed by a single call to ISKBVALID which is the only function in Algorithm 1 that calls a reasoner.

If, on the other hand, includes no conflict set, is partitioned into and and the two DPIs, the first with KB and background knowledge and the second with KB and background knowledge , are recursively analyzed where is the result computed for the first DPI.

This recursion is executed until encountering a trivial case, i.e. a leaf node of the recursion tree, along each path. Then, the recursion unwinds by building the union of all leaf nodes, i.e. the union of all returned sets for subproblems where a trivial case occurred.

The next example illustrates one execution of QX which computes one minimal conflict set:

Example 4.4 Let us consider the DL example DPI depicted by Table 4.3. We will now demonstrate how a minimal conflict set is computed by Algorithm 1 (see Fig. 4.1). Since K is not the empty set and not a valid KB w.r.t. the DPI (conditions in lines 4 and 2 are false), QXis called in line 7. This call is illustrated by the root node (node 1) of the recursion tree given in Fig. 4.1 (whereas the evaluations made by QX prior to this call are not depicted in the figure). Notice that each node in the tree shows only the values of C, K and B since all other parameters P, N and R are invariant throughout the entire execution of Algorithm 1.

Due to the fact that and K includes five formulas and is thus not a singleton, , is partitioned into and and QXis recursively called in line 16 with parameters and which is expressed in the figure by a left branch to node 2. This call, however, returns directly since is already invalid w.r.t. because which is a negative test case, i.e. must not

Algorithm 1 QX: Computation of a Minimal Conflict Set

be entailed by a solution KB w.r.t. the input DPI (the parts of the formulas relevant for the entailment to hold are underlined). Returning in this case means discarding .

So, the algorithm opens a right branch from the root to node 3by calling QX(line 17) with parameters (result of left branch), and B = B. During the execution of this call is partitioned into (left branch to node 4) and (right branch to node 5). In node 4, it holds that can be extended to a solution KB by adding , i.e. is valid. As it is already an established fact since the execution of node 2that is invalid, it must be the case that is an element of a minimal conflict set w.r.t. the input DPI (as there is a conflict set w.r.t. the input DPI in , but there is none in ). The algorithm accounts for that by checking whether K is a singleton (line 11) in which case it is guaranteed that K is a subset of a minimal conflict set w.r.t. the input DPI. So, node 4returns . This procedure is continued until each path from the root node reaches a node where a trivial case is met. Then the recursion unwinds and, when arrived at the root node, the minimal conflict set is returned.

That is indeed a conflict set can be recognized easily by the underlinings in the formulas given before. Minimality is given since is neither inconsistent nor incoherent and the deletion of any formula from C breaks the entailment of . Hence, QX has returned a sound output.

Table 4.3: Description Logic Example DPI 2

The complexity of Algorithm 1 in terms of the number of calls to the function ISKBVALID, which is the only place in the algorithm where a reasoning service is consulted, is captured by the following proposition.

Proposition 4.8 (Complexity of QX). [Jun04] Let be a DPI and the function SPLIT (line 13 of Algorithm 1) be defined as SPLITwhere n is a natural number. Then, the worst case number of calls to ISKBVALID during one call to QXis in where C is the output of QX.

For any other definition of the function SPLIT, the worst case number of ISKBVALID invocations gets larger.

4.4.2 Correctness of Conflict Set Computation

This section is dedicated to the proof of correctness of Algorithm 1. First, we show some essential properties of QX by various Lemmata which will finally be exploited to demonstrate the overall soundness of QX.

The QX algorithm accepts a DPI over some monotonic language L as input and returns a minimal conflict set w.r.t. as output. First, the algorithm checks whether is a valid KB w.r.t. the input DPI (line 2). If so, there is no conflict set for the DPI by Proposition 4.1 and the algorithm returns ’no conflict’. Otherwise, the test is performed (line 4). If so, then the negative outcome of the validity test executed in line 2 actually means that one of the two criteria of Proposition 3.4 is violated which, by Definition 3.6, implies that the DPI is not admissible. Invalidity of w.r.t. and non-admissiblity of mean that there is only one minimal conflict set by Proposition 4.2. Thus, is returned in line 5.

Lemma 4.1. Let be an admissible DPI and K be invalid w.r.t. . Then, there is a minimal conflict set w.r.t. .

Proof. The proposition is a direct consequence of Proposition 4.2.

Figure 4.1: Recursion tree produced during the computation of the minimal conflict set w.r.t. the DPI shown by Table 4.3 using Algorithm 1. Nodes in the depicted tree represent calls QX

and are written in format is a counter starting from 1 that indicates when the respective call is made. A recursive call to QX(left branch = call in line 16; right branch = call in line 17) is denoted by a normal arrow whereas the return of a set is visualized by a dashed arrow.

So, if both initial tests (lines 2 and 4) are negative, then, by Lemma 4.1, there is a non-trivial minimal conflict set w.r.t. wherefore the algorithm enters the recursion by a call to the procedure QX.

The argumentation so far proves the following lemma.

Lemma 4.2.

• QXreturns ’no conflict’ iff there is no (minimal) conflict w.r.t. .

• QXreturns iff is the only (minimal) conflict w.r.t. .

• QXreturns QXiff there is some minimal conflict w.r.t. .

Corollary 4.3. QXreturns QXiff is an admissible DPI.

Proof. By the third proposition of Lemma 4.2 and Proposition 4.1 we have that QXreturns QXiff K is invalid w.r.t. . By Proposition 4.2, we can then conclude that QXreturns QXiff is an admissible DPI.

The input arguments (at any call) to QXare (a) some subset C of the original input KB to QX and (b) a DPI where and .

The principle of QXrelies on the following fact.

Lemma 4.3. [Jun04] Let be a partition of K. If is a minimal conflict set w.r.t. and is a minimal conflict set w.r.t. , then is a minimal conflict set w.r.t. .

Proof. Since is a minimal conflict set w.r.t. , we have that is invalid w.r.t. . From that we obtain that must be invalid w.r.t. . Further on, by the fact that partition K we have that since is a minimal conflict set w.r.t. and since is a minimal conflict set w.r.t. . Consequently, must be true. So, by Corollary 4.1, is a conflict set w.r.t. .

To show the minimality of , assume that is a minimal conflict set w.r.t. , . Due to and and , it must hold that . Thus, (1) or (2) .

Let us assume (1) holds. Then, C is invalid w.r.t. , i.e. violates some or some where . This, however, is a contradiction to the minimality of the conflict set w.r.t. .

Now, let us assume (2) holds. Then, C is invalid w.r.t. , i.e. violates some or some where . By monotonicity of L and , this implies violates some or some , i.e. is a conflict set w.r.t. which is a contradiction due to and the minimality of the conflict set w.r.t. .

QXcomputes a minimal conflict set w.r.t. in a divide-and-conquer fashion whereby the argument C is the set of sentences of that has been added to B in the current iteration. That is, in this iteration QXwill output either (1) if the current B (which includes C) already contains a minimal conflict set w.r.t. the original DPI or (2) a minimal conflict set w.r.t. the current DPI (i.e. a subset of a minimal conflict set w.r.t. the original DPI) which does not include any sentence from C.

Lemma 4.4.

1. For each call QXwithin Algorithm 1 it holds that .

2. If QXis called in line 16 of Algorithm 1, holds.

3. If QXreturns , then there is some non-empty minimal conflict set w.r.t. .

4. If QXreturns , then is the only minimal conflict set w.r.t. .

5. QXterminates.

Proof.

1): There are three situations when QXis called within Algorithm 1, namely in lines 7, 16 and 17. In line 7, holds. In line 16, holds. In line 17, holds.2): In line 16, QXis called with , which is always not the empty set due to the definition of the SPLIT function in line 13 that is used to extract from K.

3): The first observation is that QXcannot return if as in this case the first condition in line 9 is not met. Thus, in particular, QXcannot return if called in line 7.

So, can be returned by QXonly if it is called (1) in line 16 or (2) in line 17.

If QXreturns , then and B is invalid w.r.t. (line 9), i.e. B contains a minimal conflict set w.r.t. which is non-empty by Proposition 4.2 since is an admissible DPI by admissibility of the input DPI and the invariance of P, N , R throughout QX. Additionally, holds by the first proposition of this lemma. Now, assume that there is no non-empty (minimal) conflict set w.r.t. . Then, for each minimal conflict set (which we know is non-empty) w.r.t. it must hold that , i.e. there is already a non-empty minimal conflict set w.r.t. .

Case (1): Let us assume first that the call to QXwas made in line 16. Then, before this call to QX, B was exactly B \ C. By the second proposition of this lemma, as QXwas called in line 16. Thus, before the current call to QX, the algorithm must have already returned (both conditions in line 9 are met) in line 10 which is a contradiction to the assumption that QXwas called in line 16.

Case (2): Now, assume that the call to QXwas made in line 17. Then is the result of the call to QXin line 16. By the argumentation above, we have that and there is a non-empty minimal conflict set w.r.t. . Moreover, we have that there is a non-empty minimal conflict set w.r.t. . However, as QXin line 16 did not return and by the second proposition of this lemma, it must hold that is valid w.r.t. , i.e. there is no (minimal) conflict set w.r.t. . By monotonicity of L, this is a contradiction to the fact that there is a non-empty minimal conflict set w.r.t. .

4): Assume QXreturns and there is some non-empty minimal conflict set w.r.t. . Since is returned, both conditions in line 2 must be met, i.e. in particular B must be invalid w.r.t. which means that is not admissible. By Proposition 4.2, there cannot be a non-empty (minimal) conflict set w.r.t. . This yields a contradiction.

5): QXeither returns in line 10 iff the conditions in line 9 are met or otherwise returns K in line 12 iff |K| = 1 or otherwise calls itself recursively in lines 16 and 17. However, for each recursive call QXwithin QXit holds that as and due to the definition of the SPLIT function in line 13 that is used to compute and from K in lines 14 and 15. Hence, each recursive call must finally reach the stopping criterion |K| = 1 and return K if it does not reach the stopping criterion in line 9 before.

Lemma 4.5. Let be an admissible DPI. If QXis called, then at least one of the immediate recursive calls of QXin line 16 or line 17 is given an admissible DPI as argument.

Proof. Let us assume that is an admissible DPI. Within QX, the immediate recursive call is QXin line 16 and QXin line 17 where is a partition of K and is the result of QX. If is admissible, then the proposition of the lemma is fulfilled. So, assume that that is not admissible. Due to this non-admissibility, it must hold that is invalid w.r.t. , so the second condition in line 2 is met. As the call to QXwas made in line 16, it must be true by Lemma 4.4, prop. 2 that wherefore the first condition in line 2 is met as well. Thus, the result of the call of QXin line 16 must be . So, the call of QXin line 17 looks like QX. However, the DPIs and are identical except for the first entries, i.e. and K. We know that the latter DPI is admissible. Due to the fact that admissibility of a DPI is defined independently of the KB (the first entry of the DPI tuple), we have that must be admissible. This completes the proof.

As long as the algorithm goes downwards in the recursion tree (and has never gone upwards), (1) the invariant that a minimal conflict set exists for each recursive call to QXholds, (2) each call to QXthat returns, returns a singleton or empty set and (3) the two calls to QXimmediately before going upwards in the recursion tree for the first time must both return either a singleton or an empty set.

Lemma 4.6 (QX: Downwards Correctness). Let be an admissible DPI and let there be a non-empty minimal conflict set w.r.t. . Then, the following propositions hold:

1. Before line 18 has ever been reached during the execution of QX, the following holds: If some call to QXreturns a set S, then or |S| = 1.

2. Before line 18 has ever been reached during the execution of QX, the following holds: If QXis recursively called, then there is some non-empty minimal conflict set w.r.t. .

3. Before line 18 has ever been reached during the execution of QX, the following holds: If some call to QXreturns a set S, then S is a minimal conflict set w.r.t. .

4. When line 18 is reached for the first time, each of the calls to QXimmediately before in lines 16 and 17 must have returned or some K with |K| = 1.

Proof.

1): Assume the opposite, i.e. some call to QXreturns a set S with |S| > 1before line 18 has ever been reached. There are three places where QXcan return, namely in line 10, in line 12 or in line 18. However, in line 10, only and in line 12 only a singleton set can be returned. That is, S must be returned in line 18 which is a contradiction to the assumption that line 18 has not yet been reached.

2): Induction Base: The first recursive call QXcan only occur at line 16 where and and is a partition of K as per the definition of the SPLIT and GET functions in lines 13-15. So, and . The latter holds since and for each DPI holds by Definition 3.1. As there is a non-empty minimal conflict set w.r.t. we have that there is a non-empty minimal conflict set w.r.t. by the fact that . Thus, the existence of a non-empty minimal conflict set w.r.t. is given during the execution of the first recursive call to QX.

Induction Assumption: Now, let us assume that the existence of a non-empty minimal conflict set w.r.t. is given during some call QX. The goal is now to show that the existence of a non-empty minimal conflict set w.r.t. is given during any recursive call QXthat is invoked during execution of QX.Induction Step: Now, there are three cases where this recursive call to QXcan take place, namely (1) in line 16, (2) in line 17 where the result of QXin line 16 is and (3) in line 17 where the result of QXin line 16 is some with . The case where some with is returned by QXin line 16, is impossible due to the assumption that line 18 has not yet been reached and the first proposition of this lemma.

Case (1): Let us assume that the call QXis made in line 16. Since that call is made within QX, it must hold that some condition in line 2 during QX, is violated, as otherwise a return would have taken place in line 10 which is a contradiction to the assumption that QXis called in line 16.

Let us first assume that holds. In this case, the first condition in line 2 is violated and, by the Induction Assumption, it is true that there is a non-empty minimal conflict set w.r.t. the DPI which is equal to the DPI by . So, an equal argumentation to the one of the Induction Base can be applied to derive that there is a non-empty minimal conflict set w.r.t. .

If holds, on the other hand, then the first condition in line 2 is satisfied wherefore the second condition in line 2 must be violated. That is, there is no conflict set w.r.t. . As there is a non-empty minimal conflict set w.r.t. by the Induction Assumption, by Lemma 4.4, prop. 1 and by the fact that there was no return in line 12, there must be a non-empty minimal conflict set w.r.t. . Again, an equal argumentation to the one of the Induction Base can be applied to derive that there is a non-empty minimal conflict set w.r.t. .

Case (2): Here, we assume that the recursive call QXis made in line 17 and the result of QXin line 16 is . So, it holds that and , i.e. the recursive call can be written as QX. By the fact that QXcalled in line 16 returned , both conditions in line 2 during QXmust have been met. Thus, in particular the existence of a non-empty minimal conflict set w.r.t. must be given. Further on, by the Induction Assumption there is a non-empty minimal conflict set w.r.t. .

Let us first assume . In this case can be written as and it holds that there is a non-empty minimal conflict set w.r.t. , i.e. K is invalid w.r.t. . By Proposition 4.2, this implies that is admissible. In other words, there is no conflict set w.r.t. . Consequently, there must be a non-empty minimal conflict set w.r.t. .

If , on the other hand, then the second condition in line 2 during QXmust be invalid, i.e. there is no conflict set w.r.t. . Consequently, there must be a non-empty minimal conflict set w.r.t. .

Case (3): Here, we assume that the recursive call QXis made in line 17 and the result of QXin line 16 is . As and line 18 has never been reached by assumption, must have been returned in line 12 of QX(which was called in line 16) wherefore must hold. So, it holds that and , i.e. the recursive call can be written as QX. By the Induction Assumption, there is a non-empty minimal conflict set w.r.t. . Moreover, by Lemma 4.4, prop. 1 and (*) there is a non-empty minimal conflict set w.r.t. the DPI which is equal to the DPI by the fact that partition K as per the definition of the SPLIT and GET functions in lines 13-15.

What must still be proven, is (*): Let us first assume that holds. In this case, and thus there is a non-empty minimal conflict set w.r.t. .

If , on the other hand, then the second condition in line 2 during QXmust be invalid as otherwise would have been returned which is a contradiction to the assumption that the recursive call QXwas invoked in line 17. So, there is no conflict set w.r.t. . Consequently, there must be a non-empty minimal conflict set w.r.t. due to by Lemma 4.4, prop. 1.

3): Case : By and the fact that line 18 has not yet been reached, we obtain by the first proposition of this lemma that |S| = 1 must hold.

There are two cases that can trigger QXto return K with |K| = 1, i.e. case 1 involving and case 2 involving .

In case 1, B must be valid w.r.t. as otherwise would be returned in line 10. So, there is no (minimal) conflict set w.r.t. .

As |K| = 1 by assumption and by the fact that (holds by Lemma 4.4, prop. 1) and there is some non-empty minimal conflict set w.r.t. (holds by the second proposition of this lemma), K must include a non-empty minimal conflict set w.r.t. . Since the only proper subset of K is the empty set, K must be a minimal conflict set w.r.t. .

Case 2 can arise only when QXis called in line 7 or line 17. In line 16 QXis called with by Lemma 4.4, prop. 2.

In line 7 QXis called with and, by Corollary 4.3, with an admissible DPI for

which a non-empty minimal conflict set exists as arguments. By the second proposition of this lemma, there is some non-empty minimal conflict set w.r.t. , and, by admissibility of , there is no (minimal) conflict set w.r.t. . By |K| = 1, K must be a minimal conflict set w.r.t. .

A necessary condition for QXto be called with in line 17 is obviously that QXcalled in line 16 returns . By the Lemma 4.4, prop. 3, there is some non-empty minimal conflict set w.r.t. . In line 17, the call QXis made which, by assumption, returns with . That means is a minimal conflict set w.r.t. .

Case : Here, both conditions in line 2 must be met, i.e. in particular B is invalid w.r.t. which implies that K is invalid w.r.t. and is admissible. Therefore, by Proposition 4.2, there is no non-empty minimal conflict set w.r.t. . However, since K is invalid w.r.t. , there must be a conflict set w.r.t. . So, there is only the empty minimal conflict set w.r.t. .

4): This proposition is an immediate consequence of the first proposition of this lemma.

Lemma 4.7. Let be a non-admissible DPI. Then, is the only minimal conflict set w.r.t. and QXwith returns immediately in line 10.

Proof. Since is non-admissible, violates some or for some . Therefore, is invalid w.r.t. , which, by Corollary 4.1, implies that is a (minimal) conflict set w.r.t. .

QXreturns in line 10 as both conditions in line 9 are satisfied due to and the non-admissibility of .

Lemma 4.8. Let be an admissible DPI. Then QXdoes not return in line 10.

Proof. By Definition 3.6, B must be valid w.r.t. . Hence, the second condition in line 9 is not satisfied wherefore a return cannot take place in line 10.

Lemma 4.9. Let be an admissible DPI and let there be a non-empty minimal conflict set w.r.t. . Then the following holds: When QXreaches line 18 for the first time, is a non-empty minimal conflict set w.r.t. .

Proof. The premises of this lemma are the same as those of Lemma 4.6. By Lemma 4.6, prop. 4 we know that for and that are returned by the the calls to QXin lines 16 and 17 and holds. Moreover, we know by Lemma 4.3 that is a minimal conflict set w.r.t. .

What remains open is to show that . To this end, we first assume that . Then, by Lemma 4.7, must be an admissible DPI since it does not return in line 10, but only in line 18.

If, on the other hand, holds, we can apply Lemma 4.6, prop. 2 to obtain that there is a non-empty minimal conflict set w.r.t. . This implies that K is invalid w.r.t. . Therefore, we can conclude by means of Proposition 4.2 that is an admissible DPI. Thus, in both cases we have that is an admissible DPI. Applying Lemma 4.5 yieldsthat at least one recursive call to QXin lines 16 and 17 is given an admissible DPI as argument. By Lemma 4.8, this call cannot return in line 10. So, it must return in line 12 by the assumption that line 18 has not yet been reached before, wherefore it must return a set of cardinality 1. This completes the proof.

As long as the algorithm goes upwards after going upwards for the first time, a non-empty minimal conflict set is propagated upwards.

Lemma 4.10 (QX: Upwards Correctness). Let be an admissible DPI and let there be a non-empty minimal conflict set w.r.t. . Then: After QXhas reached line 18 for the first time, the following holds: As long as line 16 is not reached, each return in line 18 returns a minimal conflict set w.r.t. .

Proof. The premises of this lemma are the same as those of Lemma 4.6. By Lemma 4.9 we know that a non-empty minimal conflict C set is returned at the first return that is made in line 18. As, by assumption, C is not the result of a prior call to QXin line 16, it must be the result of a prior call to QXin line 17. Since the premises of Lemma 4.6 are fulfilled, Lemma 4.6 can be applied. Since the call QX(that returned ) in line 16 took place before line 18 was first reached, we have that is a minimal conflict set w.r.t. by Lemma 4.6, prop. 3. By Lemma 4.3, we have that is a minimal conflict set w.r.t. . As long as line 16 is not reached, the same argumentation can be used to show that a minimal conflict set is returned in line 18.

When the algorithm goes downwards again after going upwards for the first time, the invariant that that a minimal conflict set exists for each recursive downwards call to QXholds.

Lemma 4.11 (QX: Downwards-after-upwards Correctness). Let be an admissible DPI and let there be a non-empty minimal conflict set w.r.t. . Then: After QX, has reached line 18 for the first time, the following holds: If line 16 is reached for the first time, then, if the DPI which is the argument to the immediate call QXin line 17 is admissible, then there is a non-empty minimal conflict set w.r.t. .

Proof. The premises of this lemma are the same as those of Lemma 4.6. Since line 16 is first reached after line 18 has been reached for the first time, it must hold that QXin line 16 was called before line 18 has been reached. The reason for this to hold is the fact that only returns and no new calls to QXcan have been made between the first occurrence of line 18 and the next occurrence of line 16.

Therefore, the result of the call QXin line 16 is a minimal conflict set w.r.t. due to Lemma 4.6, prop. 3. As a consequence, violates some or some . As the DPI is admissible by assumption, it holds that does not violate any or . Hence, must be invalid w.r.t. which implies that there must be a non-empty minimal conflict set S w.r.t. .

By applying the argumentation of Lemmas 4.6, 4.10 and 4.11 recursively on the entire recursion tree, we can prove the correctness of QX.

Lemma 4.12. If QXis called in line 7 by Algorithm 1, it returns a non-empty minimal conflict set w.r.t. .

Proof. If QXis called in line 7 of Algorithm 1, it must be true, by Lemma 4.2, prop. 4.2 and Corollary 4.3, that is an admissible DPI for which a non-empty minimal conflict set exists. As a consequence, the premises of Lemma 4.6 are met for .

There are two cases to consider: Either (a) or (b) for the initial call to QXin line 7. In case (a), cannot hold as there must be a non-empty minimal conflict set C w.r.t. due to Lemma 4.2, prop. 4.2. Since must hold for C, this would be a contradiction to .

So, holds in case (a). In this case, QXreturns immediately in line 12, since and thus the conditions checked in line 9 cannot be met. In this case, is indeed a non-empty minimal conflict set since for the DPI given as argument there is a non-empty minimal conflict set by Lemma 4.2, prop. 4.2. Therefore cannot be a conflict set w.r.t. this DPI whereby is the only possible minimal conflict set due to .

Case (b): In this case, a direct return can neither take place in line 10 by nor in line 12 by . So, QXis called recursively in lines 16 and 17. Since QXterminates due to Lemma 4.2, prop. 5, QXmust reach line 18. The first time some recursive call QXreaches line 18, it returns a non-empty minimal conflict set w.r.t. due to Lemma 4.9.By Lemma 4.10, as long as line 16 is not reached, i.e. no “left branch” (call to QXin line 16) but only “right branches” (calls to QXin line 17) return, a minimal conflict set S is returned for each call to QXthat “wraps” (is higher in the recursion tree than) the call that was the first to reach line 18. It holds that since S is a union of sets including the non-empty set returned when line 18 was first reached.

When it comes to an execution of line 16, i.e. the left branch returns, then the algorithm will take the right branch by executing line 17, i.e. calling QX, and go downwards in the recursion tree.

Now, there are two cases. First, is non-admissible. Then, by Lemma 4.7, there is only one minimal conflict set w.r.t. , namely , and QXdirectly returns . As also the result of the call to QXimmediately before in line 16 is a minimal conflict set w.r.t. , as established above, we can apply Lemma 4.3 to derive that indeed a minimal conflict set w.r.t. is returned in line 18. Thus, Lemma 4.10 can be further applied to move upwards in the recursion tree until line 16 occurs again.

Second, is admissible. Then, by Lemma 4.11, there is a non-empty minimal conflict set w.r.t. . Hence, Lemma 4.6 can be used again for the subtree of the recursion tree rooted at the call QX. That is, it can be used to show that each call to QXwithin this subtree returns a minimal conflict set w.r.t. the DPI given as argument as long as the algorithm moves downwards in the tree. Having reached line 18 for the first time, Lemma 4.9 lets us conclude again that a non-empty conflict set w.r.t. the respective argument DPI is actually returned at this place. Subsequently, Lemma 4.10 can be applied to show that each return gives back a minimal conflict set w.r.t. the argument DPI of the respective call, as long as the algorithm moves upwards in the recursion tree.

What is still open is to show that the call QXin line 17 that is made immediately after the algorithm first reached line 16 after moving upwards after reaching line 18 for the first time returns a minimal conflict set w.r.t. , indeed. This holds by the fact that Lemmas 4.6 and 4.10 guarantee that a left branch always returns a minimal conflict set, Lemma 4.11 guarantees that Lemmas 4.6 and 4.10 can be applied after making a single right branch. However, as QXterminates the recursion tree is finite and thus the case must arise where the right branch directly returns. In case the DPI given as argument for this right branch is non-admissible, the only minimal conflict set is returned, as established above. If the DPI given as argument for this right branch is admissible, on the other hand, then we have already shown above that there is a non-empty minimal conflict set w.r.t. this DPI. Moreover, |K| = 1 must hold due to the fact that this right branch directly returns (without entering a further recursion). Therefore, K is returned which is actually a minimal conflict set w.r.t. as K is the only non-empty subset of K.

Proposition 4.9. Let be a DPI. Then, QXterminates and returns

• ’no conflict’ iff there is no conflict w.r.t. (K is valid w.r.t. )

iff is the only minimal conflict set w.r.t. (DPI is non-admissible)

• a non-empty minimal conflict set w.r.t. iff there is a non-empty minimal conflict set w.r.t. (DPI is admissible and K is invalid w.r.t. ).

Proof. The proposition is a direct consequence of Lemma 4.2 and Lemma 4.12.

4.5 Hitting Set Tree Based Diagnosis Computation

One way to compute minimal diagnoses from minimal conflict sets is to use a hitting set tree algorithm which was originally proposed by Reiter [Rei87]. In this work we describe methods for non-interactive and interactive diagnosis computation based on the ones used in [FS05, SF10, SFFR12] which are closely related to the original hitting set tree algorithm. Differences of the described non-interactive algorithm to the original one of Reiter are

1. the usage of different edge weights (probabilities) inducing an order of node generation (uniform-cost) different to breadth-first and

2. the opportunity to specify an execution time threshold t as well as a minimal () and maximal () desired number of minimal diagnoses to be computed by the algorithm.

In this vein, the algorithm computes at least the most-probable minimal diagnoses w.r.t. the given probabilities and goes on computing further next most-probable minimal diagnoses until either overall computation time reaches the time limit t or diagnoses have been computed.

Such a time threshold and an interval of minimal and maximal number of diagnoses is particularly relevant in settings where not all potential minimal faulty sets need to be computed, such as iterative, interactive settings where reaction time is crucial (since a user is waiting to interact with the system). Instead, in such settings only a “representative” set of minimal diagnoses is exploited to decide which question to ask a user such that the answer to that question allows the constructed partial tree to be pruned. After pruning, the tree is expanded again to compute another “representative” set of minimal diagnoses. Such an interactive KB debugging algorithm will be presented in Part II. The non-interactive version of the KB debugging algorithm is delineated by Algorithm 2 and described next.

Inputs. The algorithm takes as input an admissible DPI , some computation timeout t, a desired minimal () and maximal () number of minimal diagnoses to be returned, and a function that assigns to each formula a weight that represents the (estimated) likeliness of ax to be faulty and thereby determines the search strategy, e.g. breadth-first or uniform-cost. Within the algorithm, p() is used to impose an order on open nodes that tells the algorithm which node to expand next. Details concerning the function p() will be discussed in Section 4.6 after demonstrating various ways of obtaining information relevant to p() and detailing how p() can be defined by means of such information. Throughout the rest of the current Section 4.5 we assume that p() implies a first-in-first-out sorting of open nodes, i.e. a breadth-first search strategy as described in [Rei87].

4.5.1 Breadth-First Diagnosis Computation

Algorithm Overview and Implementation Remarks. To compute minimal diagnoses w.r.t. , from minimal conflict sets w.r.t. , the algorithm produces a labeled tree where a non-closed node is labeled by a minimal conflict set and a closed node is labeled by either valid or closed. From a non-closed node labeled by a minimal conflict set there are |C| outgoing edges, each labeled by one and each leading to a new node that needs to be labeled. Closed nodes are leaf nodes of the produced tree, i.e. they have no successor nodes, and correspond to non-minimal or duplicate hitting sets (label closed) or to minimal hitting sets (label valid) of all minimal conflict sets w.r.t. the input DPI . Conflict sets to label nodes are computed only on-demand for time efficiency after the attempt to reuse an already computed one fails. In case an appropriate order of node labeling (e.g. breadth-first tree construction) is used, the complete tree given when all nodes in the tree are closed contains all minimal diagnoses w.r.t. the DPI provided as input. In this complete tree, the set of edge labels on each path from the root node to a node labeled by valid is a minimal diagnosis.

What Algorithm 2 actually does is building up a pruned HS-tree for a given DPI. So, we next provide formal definitions of a (partial) HS-tree and a (partial) pruned HS-tree based on the definitions given in [Rei87].

Definition 4.7 (HS-Tree). Let be an admissible DPI. An edge-labeled and node-labeled tree T is called an HS-tree w.r.t. iff it is a smallest tree with the following properties:

1. The root of T is labeled by valid if K is valid w.r.t. . Otherwise, the root is labeled by a conflict set w.r.t. .

2. If n is a node of T, define H(n) to be the set of edge labels on the path in T from the root node to n. If n is labeled by valid, it has no successor nodes in T. If n is labeled by a conflict set C w.r.t. , then for each has a successor node joined to n by an edge labeled by ax. The label for is a conflict set w.r.t. such that if such a set exists. Otherwise, is labeled by valid.

T is called a partial HS-tree w.r.t. iff T is a HS-tree w.r.t. where not all nodes in T are labeled and non-labeled nodes have no successors.

Definition 4.8 (Pruned HS-Tree). Let be an admissible DPI. An edge-labeled and node-labeled tree T is called a pruned HS-tree (pHS-tree) w.r.t. iff T is the result of constructing an HS-tree w.r.t. with due regard to the following rules:

1. Label nodes in the HS-tree in breadth-first order.

2. Use only minimal conflict sets w.r.t. to label nodes in T.

3. Reusing node labels: If node n is labeled by C and is a node such that , label by C.

4. Non-minimality pruning rule: If node n is labeled by valid and node is such that ,label by closed.

5. If node n is labeled by closed, it has no successors.

6. Duplicate pruning rule: If node n is next to be labeled and there is some node such that H(n), then label n by closed.

T is called a partial pruned HS-tree iff T is a pruned HS-tree where not all nodes in T have been labeled yet and non-labeled nodes have no successors.

Remark 4.1 Notice that we use a definition of a pruned HS-tree that slightly differs from the definition given in [Rei87] in that we inherently assume that only minimal conflict sets w.r.t. the given DPI are used to label nodes in the tree. Therefore we could omit the last rule in the definition of [Rei87]. Namely, such a situation where some node has been labeled by a subset of the label of another node cannot arise in our definition since no minimal conflict set can be a subset of another different minimal conflict set w.r.t. the same DPI.

In general, there are multiple different pHS-trees w.r.t. one and the same DPI [GSW89]. Reason for this is that

• the order of adding successor nodes (on the same tree level) to the queue Q and

• which of generally multiple minimal conflict sets to (re)use to label a node

is not determined by Definition 4.8.

By [Rei87, Theorem 4.8] and Proposition 4.6, the following holds:

Proposition 4.10. Let be an admissible DPI and T a pHS-tree w.r.t. . Then, {H(n) | n is a node of T labeled by , i.e. the set of all minimal diagnoses w.r.t. .

Remark 4.2 A node nd in Algorithm 2 is defined as the set of formulas that label the edges on the path from the root node to nd. In other words, we associate a node n with H(n). In this vein, Algorithm 2 internally does not store a labeled tree, but only “relevant” sets of nodes and conflict sets. That is, it does not store any

• non-leaf nodes,

• labels of non-leaf nodes, i.e. it does not store which minimal conflict set labels which node,

• edges between nodes,

• labels of edges and

• leaf nodes labeled by closed.

Let T denote the (partial) pHS-tree produced by Algorithm 2 at some point during its execution (Corollary 4.4 will show that Algorithm 2 using breadth-first search in fact produces a (partial) pHS-tree). Then, Algorithm 2 only stores

• a set of nodes where each node corresponds to the edge labels along a path in T leading to a leaf node that has been labeled by valid (minimal diagnoses w.r.t. ),

• a list of open (non-closed) nodes Q where each node in Q corresponds to the edge labels along a path in T leading from the root node to a leaf node that has been generated, but has not yet been labeled and

• the set of already computed minimal conflict sets w.r.t. that have been used to label non-leaf nodes in T.

We call the relevant data of T. If T is a pHS-tree, then Q is the empty list.

This internal representation of the constructed (partial) pHS-tree by its relevant data does not constrain the functionality of the algorithm. This holds as diagnoses are paths from the root, i.e. nodes in the internal representation, and the goal of a (partial) pHS-tree is to determine minimal diagnoses w.r.t. the given DPI. The node labels or edge labels along a certain path and their order along this path is completely irrelevant when it comes to finding a label for the leaf node of this path. Instead, only the set of edge labels is required for the computation of the label for a leaf node. Also, to rule out nodes corresponding to non-minimal diagnoses, it is sufficient to know the set of already found diagnoses . No already closed nodes are needed for the correct functionality of Algorithm 2.

Initialization. First, Algorithm 2 initializes the variable with the current system time (GETTIME), the set of calculated minimal diagnoses to the empty set and the ordered queue of open nodes Q to a list including the empty set only (i.e. only the unlabeled root node).

The Main Loop. Within the loop (line 5) the algorithm gets the node to be processed next, namely the first node node (GETFIRST, line 6) in the list of open nodes Q ordered by the function and removes node from Q (DELETEFIRST, line 7). Note that can be directly obtained from p(). As mentioned before, for the moment the reader should simply suppose that imposes an order on Q which effectuates a breadth-first labeling of open nodes in the tree. A definition of will be given by Definition 4.9 after a motivation and detailed explanation of will have been given in Section 4.6.

Computation of Node Labels. Then, a label is computed for node in line 8. Nodes are labeled by valid, closed or a minimal conflict set w.r.t. by the procedure LABEL (line 18 ff.). This procedure gets as inputs the DPI , the current node node, the set of already computed minimal conflicts () and minimal diagnoses () and the queue Q of open nodes, and it returns an updated set of computed minimal conflicts and a label for node. It works as follows:

A node node is labeled by closed iff (a) there is an already computed minimal diagnosis D in that is a subset of this node, i.e. , which means that node cannot be a minimal diagnosis (non-minimality criterion, lines 19-21) or (b) there is some node nd in the queue of open nodes Q such that node = nd which means that one of the two tree branches with an equal set of edge labels can be closed, i.e. removed from Q (duplicate criterion, lines 22-24).

If none of these closed-criteria is met, the algorithm searches for some C in , the set of already computed minimal conflict sets, such that and returns the label C for node (reuse criterion, lines 25-27). This means that the path represented by node cannot be a diagnosis as there is (at least) one minimal conflict set, namely C, that is not hit by node.

If the reuse criterion does not apply, a call to QXis made (line 28) in order to check whether there is a not-yet-computed minimal conflict set that is not hit by node. Note that the KB K \ node that is given to QX as part of the argument DPI ensures that only minimal conflict sets can be computed, i.e. ones that do not share any single formula with node (cf. Section 4.4.1).

Remark 4.3 A minimal conflict set computed by QXis a minimal conflict set w.r.t. indeed since (i) QXreturning a set C means that C is a minimal conflict set w.r.t. by Proposition 4.9 and (ii) the “” direction of Corollary 4.1 implies that C is not valid w.r.t. and (iii) the “” direction of Corollary 4.1 lets us conclude that C is a minimal conflict w.r.t. where X is any superset of C, in particular X := K.

QX may then return (a) ’no conflict’, i.e. K \ node is already valid w.r.t. , or (b) a new conflict set such that . Note that the case of the output of QX cannot arise since (i) the DPI provided as input to the algorithm is assumed to be admissible, (ii) no other DPI for which QX is called can be non-admissible since admissibility is defined only by the sets B, P, N , R which remain unmodified throughout the execution of Algorithm 2, and (iii) as per Proposition 4.9, QX returns only if the DPI given to it as an argument is non-admissible. Further on, we point out that the conflict set L in case (b) must be a new conflict set since the reuse criterion is always checked before the call to QX and thus must be negative. That is, each is hit by node and L is not hit by node wherefore must hold for all .

In each of the described cases, the LABEL procedure returns a tuple including the respective label as explained and the set where is equal to the input argument in all cases except for the case where a new minimal conflict set is computed by QX. In this case, the newly computed conflict set is added to (line 32) before the procedure returns.

Processing of a Node Label. Back in the main procedure, is updated (line 9) and then the label L returned by procedure LABEL is processed as follows:

If L = valid, then there is no minimal conflict set w.r.t. that is not hit by (i.e. has an empty intersection with) the current node node. Thus, node is added to the set of calculated minimal diagnoses . Minimality of diagnoses added to is guaranteed by the pruning rule (lines 19- 21) which eliminates non-minimal nodes (paths) and the way the tree is built level by level by the used breadth-first strategy. In case a uniform-cost variant of tree construction is used, certain properties of the function p() need to be postulated to preserve this minimality guarantee. We discuss these properties in Section 4.6.

If, on the other hand, L = closed is the returned label of the procedure LABEL, then there is either a minimal diagnosis in that is a subset of the current node node or a duplicate of node is already included in Q. Consequently, node must simply be removed from Q which has already been executed in line 7.

In the third case, if a minimal conflict set L is returned in line 8, then L is a label for node meaning that |L| successor nodes of node need to be added to Q in sorted order using the function (INSERTSORTED, line 15), as will be explained in more detail in Section 4.6.

Recap. To summarize, in each iteration, the node node that is the first element of the queue Q is deleted from Q and,

1. if node is a diagnosis, it is added to the set

2. if there is some diagnosis in that is a proper subset of node or node is equal to some other node in Q, no action is performed, i.e. the algorithm deletes node without substitution

3. if there is some minimal conflict set that node does not hit, then such a conflict set C is computed and for each a new node is added to Q.

We call each node nd that is added to Q in the latter case a successor of the node node.

4.5.2 Correctness of Breadth-First Diagnosis Computation

For the discussion of the output of Algorithm 2 we will exploit the following result saying that Algorithm 2 computes all and only minimal diagnoses, if it executes until the queue of open nodes becomes the empty set.

Proposition 4.11 (Soundness and Completeness of Algorithm 2 using Breadth-First Search). Let , be an admissible DPI given as input to Algorithm 2. If Algorithm 2 using a breadth-first tree construction strategy terminates due to Q = [], then the algorithm returns exactly the set of all minimal diagnoses w.r.t. .

Proof. This proposition is a consequence of Proposition 4.10 and the following Lemma 4.13 which witnesses that Algorithm 2 using a breadth-first tree construction strategy produces a pHS-tree as per Defi-nition 4.8.

Lemma 4.13. Algorithm 2 with the admissible input DPI using a breadth-first tree construction strategy is a procedure for producing a pHS-tree T w.r.t. .

Proof. We verify whether all rules given by Definitions 4.7 and 4.8 are satisfied by Algorithm 2.

• Definition 4.7, rule 1: The root node which is the only element of the initial list Q is labeled by the first call to LABEL for in line 8. If valid is returned, then QXmust have returned ’no conflict’ which is the case if K is valid w.r.t. .

Otherwise, if valid is not returned by LABEL, then some minimal conflict set L w.r.t. must have been returned in line 33. L is a minimal conflict set w.r.t. by Proposition 4.9 and since QXhas not returned ’no conflict’ as otherwise valid would have been returned contradicting our assumption and since is an admissible DPI by assumption. LABEL cannot have returned earlier in line 21 or line 24, since is the empty set and Q the empty list at this time. The former holds since is only extended in line 11 which cannot ever have been reached before the first call to LABEL has returned. The latter holds as Q initially contained only and as was deleted from Q in line 7 before the call to LABEL was made in line 8.

• Definition 4.7, rule 2: Suppose a node node is labeled by valid, then it is added to in line 11. Since node can only get a label different from closed if it is the only exemplar of this node in Q due to the duplicate criterion (lines 22-24), it must be the case that (line 7) after node has been labeled by valid. Only nodes that get labeled by a conflict set can have successor nodes added to Q in line 15. Only nodes in Q can get a label (cf. lines 6 and 8). For node to be added to Q at some later point in time there must be a proper subset of node that is still in Q as each node newly added to Q is a proper superset of some node in Q (cf. line 15 which is the only position in the algorithm where nodes are added to Q). This is impossible due to the breadth-first tree construction strategy which implies that all nodes of cardinality have already been labeled (and thus deleted from Q in line 7) when node is being labeled. Hence, if node is labeled by valid, then it has no successors.

If node is labeled by some conflict set L, then Algorithm must come to line 15, where a successor is added to Q for all .

How node must be labeled is overridden by the rules 3, 4 and 6 of Defini-tion 4.8 (see below).

• Definition 4.8, rule 1: This is true by our assumption about p() and .

• Definition 4.8, rule 2: This holds since QXcomputes only minimal conflict sets w.r.t. (cf. Remark 4.3).

• Definition 4.8, rule 3: All minimal conflict sets that have been used to label nodes so far are stored in . Before a minimal conflict to label node might be computed by a call to QX in line 28, the reuse criterion in lines 25-27 checks whether there is a set C in with . If positive, C is returned as a label for node.

• Definition 4.8, rule 4: This is accomplished by the non-minimality criterion in lines 19-21 which checks for existence of a node already labeled by valid which is a subset of the node to be labeled right now. All nodes labeled by valid are stored in (cf. lines 10 and 11).

• Definition 4.8, rule 5: If some node node is labeled by closed, then no action is performed (cf. line 12). Before each node is labeled in line 8, it is deleted from Q in line 7. That node cannot be inserted into Q at some later point in time follows from the argumentation used above to demonstrate that Definition 4.7, rule 2 is met.

• Definition 4.8, rule 6: This is achieved by the duplicate criterion in lines 22-24 where Q is browsed for some node equal to the one that is to be labeled right now. When some node node is next to be labeled, then all duplicates of node must already be in Q as reasoned above in the argumentation to show that Definition 4.7, rule 2 is satisfied. Thus, the criterion must search for duplicates in no other collections than Q. Indeed, only one (i.e. the last non-deleted) exemplar of these duplicates of node in Q can get a label other than closed due to the duplicate criterion which closes duplicates as long as there are any.

We conclude that Algorithm 2 is a procedure for constructing a pHS-tree.

By Proposition 4.11 and the fact that there is no place in Algorithm 2 where nodes are removed from (which implies that only minimal diagnoses can be added to ), the following corollary is obvious.

Corollary 4.4. Algorithm 2 with the admissible input DPI using a breadth-first tree construction strategy stores by the relevant data of

• a pHS-tree w.r.t. if Algorithm 2 stops due to Q = [],

• a partial pHS-tree w.r.t. otherwise.

If a pHS-tree is computed in breath-first order, minimal diagnoses are generated with increasing cardinality, as the following Corollary 4.5 attests. Consequently, for the generation of all minimum cardinality diagnoses, only the first level of the tree has to be generated, where a node is labeled.

Corollary 4.5. The following holds for the set D returned by Algorithm 2 using breadth-first search: If D contains some diagnosis of cardinality k, then it includes all diagnoses w.r.t. of cardinality lower than k.

Proof. By Proposition 4.11, it is a fact that Algorithm 2 computes all and only minimal diagnoses w.r.t. . As these are computed in breadth-first order, the first computed diagnoses must be the minimum cardinality ones. To see this, assume that Algorithm 2 returns D which includes one nonminimum cardinality diagnosis D and does not comprise a minimum cardinality diagnosis , i.e. |D| > . By breadth-first search, nodes are labeled in ascending order of their cardinality. And, if the first node of cardinality k is labeled, no more nodes of cardinality can be in Q (cf. proof of Lemma 4.13). So, we have that the pHS-tree obtained by further execution of the algorithm until Q = [] can never label since and D has already been labeled. Hence, the algorithm would not return in its final output D. Since each minimum cardinality diagnosis is a minimal diagnosis, is a minimal diagnosis. Thus, we have a contradiction to the fact that the algorithm computes all minimal diagnoses.

Output. The repeat-loop is iterated until the stop criterion (line 16) applies. In case at least minimal diagnoses w.r.t. exist, there are two cases:

• If the finding of the -th minimal diagnosis happens after time has passed since the start of Algorithm 2, then the algorithm will continue iterating and terminate only if execution time amounts to at least t time or at the time line 16 is processed.

• Otherwise, if the detection of the -th minimal diagnosis takes place after processing longer than t time, then the algorithm will terminate immediately after having determined the -th minimal diagnosis.

In both cases, the output is a set D of minimal diagnoses w.r.t. such that and D is the set of best minimal diagnoses as per p(), in this case the set of minimal diagnoses with minimum cardinality since p() is assumed to be specified as to cause a breadth-first tree construction.

If fewer than minimal diagnoses exist w.r.t. , then Q = [] will be the cause for the algorithm to terminate. In this case, the pHS-tree w.r.t. has been built up and all minimal diagnoses w.r.t. are stored in . Thus, the output is the set of all minimal diagnoses w.r.t. .

Termination. The next proposition shows that Algorithm 2 must yield a set of minimal diagnoses after finite time.

Proposition 4.12. Algorithm 2 always terminates.

Proof. This is due to the fact that minimal conflict sets used to label non-leaf nodes are subsets of K and that nodes in Q are subsets of K, which is a finite set by Definition 3.1. Moreover, a node in Q is either deleted without substitution from Q if valid or closed (line 7) or deleted (line 7) and replaced by proper supersets of it (INSERTSORTED in line 15). This means that the cardinality of all nodes in Q is strictly monotonically increasing. Thus each node (path) node is guaranteed to be closed (valid or closed) when node = K as in this case node must hit all possible (minimal) conflict sets w.r.t. since holds by Definition 4.1. So, after finite time the queue Q definitely becomes the empty list which is a stop criterion (line 16).

The argumentation so far proves the following

Proposition 4.13. Let be an admissible DPI, and de-fined in a way that Q is always ordered first-in-first-out. For these inputs, Algorithm 2 always terminates and returns a set D of minimal diagnoses w.r.t. which is

• the set of the |D| minimal diagnoses of minimum cardinality w.r.t. (i.e. the first |D| elements in if is assumed to be sorted in ascending order by cardinality) such that , if at least minimal diagnoses exist w.r.t. , or

• the set of all minimal diagnoses w.r.t. , otherwise.

4.6 Diagnosis Probability Space

The induction of a probability space [Dur10] over diagnoses facilitates incorporation of well-established probability theoretic methods into the process of KB debugging; for example, a Bayesian approach [SFFR12, RSFF13, dKW87] for identifying the true diagnosis, i.e. the one which leads to a solution KB with the desired semantics, by repeated measurements (see Part II). Let the true diagnosis be denoted as in the sequel.

The Probability Space of All Diagnoses. From the point of view of probability theory, a diagnosis can be viewed as an atomic event in a probability space defined as follows:

• is the sample space consisting of all possible diagnoses w.r.t. a DPI , i.e. ,

is a sigma-algebra on , in our case the powerset of , and

• p is a probability measure assigning a probability to each event in E, i.e. such that which means .

So, p({D}) for can be seen as the probability that D is the true diagnosis, i.e. the probability of the event (or ). Consequently, p({D}) for is the probability distribution of the random variable , i.e. the probability distribution of the true diagnosis. In this vein, the probability of a set is interpreted as the likeliness of this set to comprise the true diagnosis . That is,

means that is an element of with 30% probability. Note that singletons are often written without curly braces, i.e. is usually written as ; we will also do so in the rest of this work.

The elements of the sample space of a probability space are often called atomic events because they must be mutually exclusive (i.e. two atomic events cannot “happen” at the same time as an outcome of the fictive experiment a probability space describes) and exhaustive (i.e. for each “execution” of the experiment the probability space describes one atomic event must “happen”). Since the true diagnosis must be a diagnosis w.r.t. and by definition comprises all such diagnoses, exhaustiveness is clearly fulfilled. Mutual exclusiveness is a consequence of the fact that each diagnosis D gives complete information about the correctness of each formula . In other words, is a shorthand for the statement that all are faulty and all are correct. Thus, any two different diagnoses are mutually exclusive events, i.e. implies for all such that .

The probability measure p is completely defined if a probability p(D) for each diagnosis is given. Then, by the mutual exclusiveness of events and for , the probability

for each event .

Restricted Probability Spaces of Diagnoses. In many cases, only a restricted set of diagnoses w.r.t. a DPI is considered relevant for the debugging task. That is, the focus is on locating the true diagnosis among a predefined subset of all diagnoses . This involves an adaptation of the probability space, in particular of the set . For instance, if not the set of all, but only the set of minimal diagnoses w.r.t. should be considered by a debugging system – as motivated in Section 3.1 – then . The other properties and remain the same for each restricted probability space, but depend on . Thus, for example, a probability p(D) for must be generally defined differently, i.e. assigned a higher value, when instead of . This is due to the condition that all probabilities of atomic events in must sum up to 1. In practice, because of the computational complexity of diagnosis computation, the used probability space will usually need to be restricted even further in that comprises only a set of “leading diagnoses” which is a subset of all minimal diagnoses w.r.t. a DPI (see Chapter 7).

4.6.1 Construction of a Probability Space

Since a diagnosis constitutes an assumption about the correctness of each formula in the KB, the probability of a diagnosis D (to be the true diagnosis ) can be computed by means of fault probabilities of formulas. In other words, computing the probability of the event corresponds to computing the probability of the event that exactly all formulas in D are faulty and all other formulas in the KB are correct.

Estimating Fault Probabilities of Formulas in the KB

Next we discuss various possibilities of how the probability of an might be assessed. To this end, we first make a distinction between situations where some useful empirical data is available or not and then we differentiate between different sorts of such available data and how to take advantage of it.

Empirical Data is Accessible. Let us first reflect on how to utilize different empirical data sources in order to compute formula probabilities. Data can be of the following kinds (enumeration may not be complete):

(a) Regarding formulas: Change logs of formulas in the KB

(b) Regarding the user: Data about common mistakes of the user who has formulated the KB

Ad (a): Prerequisite for the availability of change logs of formulas in the KB is the usage of some KB engineering software with integrated logging or change management. Examples of such KB (ontology) developing environments are Protégé [NSD00], Web Protégé [TNNM13], SWOOP [KPS06], OntoEdit [SEA02] or KAON2.19 Given a formula and its change log, the fault probability p(ax) of this formula can be estimated by counting the number of modifications accomplished for ax in the change log. The intuition is, the more often ax has been altered, the more uncertain the (set of) author(s) might be about its correctness. This method of probability computation however suffers from a cold-start problem. If a KB is completely newly created, then such information is not available at all. On the other hand, for KBs that are being developed over a long period of time, this method can be assumed to be a rather reliable way of assessing the likeliness of formulas to be faulty.

Ad (b): Clearly, data about common mistakes of a user has to be related to some type of entity that is recurrent and not dependent on a particular KB. Formulas are therefore not suitable and too coarsegrained since one and the same formula will rarely occur in many KBs. More adequate entities to relate a user fault to are predicates (terms) and logical connectives – these usually (re-)appear in many different KBs. In this way, the extrapolation and reusability of collected personal fault information of a user within one KB and between different KBs is granted.

One way of obtaining data about common mistakes of user u on this syntactical level is, for instance, the examination of diagnoses got as a result of past debugging sessions performed on KBs authored by u. Another way is, again, to use the change logs (if available) of formulas in KBs user u has created in the past.

Given such a past diagnosis D, we know that all formulas that had been written by u have been confirmed to be faulty by a user. So, these formulas could be analyzed for contained predicates (terms) and logical connectives and the probability of being faulty of those syntactical constructs could be raised relative to those constructs that do not occur in formulas in D. At this, the following assumptions could be made:

• If a formula has been confirmed to be faulty by the user, then the meaning of all predicates (terms) appearing in this formula is not correct (because in the domain that should be modeled the relationship between the predicates (terms) occurring in the formula stated by the formula must not hold). So, all predicates (terms) in ax get more suspicious of being faulty in general if for some past solution diagnosis D.

• If a formula including some logical connective is part of some past solution diagnosis, then this type of logical connective gets more suspicious of being faulty in general.

When exploiting change logs of formulas authored by u, the following assumptions could be made:

• If a formula has been modified, then a user has changed the meaning of all predicates (terms) appearing in this formula. So, all predicates (terms) in ax get more suspicious of being faulty in general if ax has been edited at least once. The more often it has been altered, the more suspicious the predicates (terms) get.

• If some logical connective in a formula is modified, i.e. deleted or added, then this type of logical connective gets more suspicious of being faulty in general.

The following example should give an intuition of these assumptions:

Example 4.5 Imagine the situation where the author of formula is known to have only vague knowledge about the predicate pet and to frequently interchange and when formulating logical formulas. This could be reflected by the assignment of higher fault probability to the predicate pet than to the predicates animal, hasChild and person and by raising the fault probability of as well as compared to other logical connectives available in the used logic L. Then, formula ax should intuitively have a higher probability of being faulty than, e.g., formula since does not include any of the “suspicious” terms or connectives as ax does.

A probability of 0.25 of some predicate (term) a occurring in K could then account for the observation made in the logs that, in past debugging sessions (not necessarily related to the current KB K), every fourth formula formulated by user u which includes the term a was modified at least once. Similarly, another term b could be assigned fault probability 0.5 which could reflect that formulas formulated by u including b have been altered twice as often as formulas formulated by u comprising a. Given additionally that a occurred in two formulas formulated by u of past diagnoses whereas b did not occur in any, the probability of a could be increased by some addend or factor to take account of this.

Concerning some logical connective, say , the observation that all past diagnosis formulas contained and in 80% of formulas formulated by this user including the connective has been modified at least once, the fault probability of might be assigned rather high. In comparison, the probability of some other connective, say , occurring in no diagnosis and having been altered only in 10% of the formulas comprising , the probability of the connective might be estimated rather low.

A shortcoming of this approach is again a cold-start problem. If a user is new to conceptualizing knowledge in a structured logical manner or at least in the given logical language L, then no such (personalized) past diagnoses or change logs will be available. So, this issue especially concerns beginners who are usually anyhow more prone to errors than expert-users. On the positive side, utilization of such empirical data can yield to fault information that is very well tailored for the user and that can imply a significant reduction of computation time and user effort necessary for debugging of the KB at hand [SFFR12].

No Empirical Data is Available. If no data of the kinds (a) and (b) discussed above is available to a debugging system, then we have the following possibilities:

(c) Common fault patterns

(d) Subjective self-assessment of a user

(e) Examination of structural complexity of logical formulas

(f) Using no probabilities

Ad (c): A common fault pattern [RDH04, CRV09, KPSCG06], also called anti-pattern, refers to a set of formulas that either leads to an inconsistency (logical anti-pattern) or corresponds to a potential modeling error that – alone – does not lead to a inconsistency or incoherency (non-logical anti-pattern), but still might become a source of inconsistency if merged with other formulas (cf. Section 3.2). Although most of these patterns incorporate more than one formula which makes the individual consideration of a formula in terms of fault probability calculation difficult, an idea to incorporate knowledge about anti-patterns to probability estimation of formulas could be to count for each in how many different (logical or non-logical) anti-patterns it occurs. The higher this count, the more likely a formula might be involved in a conflict set and thus in the true diagnosis.

A drawback of this method could be that most of the formulas involved in a KB might not correspond to any formula occurring in an anti-pattern. Thus, one might end up with no probability estimate for most of the formulas in a KB K. Besides that, the information provided by these anti-patterns is not personalized at all and therefore might significantly diverge from the true fault probabilities for a user and lead to a false bias in the used fault data. This justifies to basically rely on another approach to get a first estimate of a formula’s likeliness of being faulty and use this method only to make adaptations to already established probabilities.

Ad (d): The method of a user’s self-assessment of own fault probabilities supposes a user to be able to specify fault probabilities of predicates (terms), logical connectives or complete formulas by themselves. Since users not always have a clear picture of own strengths and weaknesses, this variant must be regarded with suspicion. Furthermore, in settings where several persons are involved in the engineering of the KB, a reasonable rating of fault probabilities of terms, connectives or formulas authored by other persons might be difficult or impossible for a user.

Ad (e): Here the idea is to examine “grammatical” (i.e. syntactical) aspects of formulas such as the “nesting depth” of subordinate clauses or the mere “length” of a formula. The underlying assumption can be that higher length and/or deeper nesting means higher complexity and cognitive difficulty in understanding of the formula’s semantics – as it does in natural language. For instance, it is reasonable to expect formulas like to tend to be more error-prone and more likely to be faulty than . This intuition is modeled by the maximum nesting depth as well as by the length of in comparison to . Using the analogy to natural language, the maximum nesting depth of a formula could roughly be defined as the maximum number of encapsulated subordinate clauses that cannot be “flattened” occurring in the natural language translation of the formula. For formula , this would imply a maximum nesting depth of two; for it would amount to zero. The reason is that stated in natural language would sound “if somebody X is a, then there is somebody Y , who satisfies property with X and for whom anybody, who sat-isfies property with Y is b”. In this natural language formulation, there are two subordinate clauses, i.e. the clauses beginning with the word “who”; the first is at nesting depth one and the second at depth two. These subordinate clauses cannot be flattened, i.e. be brought to some lower depth, because the Z is related to the Y which in turn is related to the X. The length of formulas could be defined similarly as in [HPS08] which provides such a definition for DL languages. In this case the length of and would be four (roughly: four predicates in ) and two (two predicates in ), respectively.

A disadvantage of such a “grammatical” approach gets evident when most of the formulas in a KB are rather “simple”, i.e. have a low nesting depth and a short length. In such case this method will give little differentiation between different formulas and should thus be combined with another method of probability estimation in general.

Ad (f): In a situation where all the aforementioned ways of gauging probabilities do not apply or are believed to have a too high risk of introducing a false bias into the debugging system, the solution is to define all formulas to be equally probably faulty. The obvious pro of this is that the system cannot get misled by unreasonable fault probabilities whereas the con is that possibly well-suited probabilistic information cannot be exploited. Moreover, experiments in our previous work [SFFR12] have manifested that fault information of only “average” quality most often leads to a better performance than no fault information. Apart from that, we have suggested a reinforcement learning “plug-in” to a debugger which could successfully mitigate the negative effect of low-quality fault information and in many cases, in spite of the low-quality fault information, even led to lower resource consumption (user, time) than a debugger without this plug-in using good fault information [RSFF13].

Collaborative KB Development. In a collaborative development scenario involving several authors, provenance information could be additionally leveraged to refine probability estimates (cf. [KPSCG06]). At this point, user skills could come into play; that is, formulas authored by more experienced authors get a lower overall fault probability as opposed to beginners concerning KB engineering or logic skills or expertise in the modeled domain. This probability adaptation can also affect syntactical elements in that one and the same predicate (term) or logical connective can get a different probability depending on in which formula it occurs and who authored that formula.

Remark 4.4 Of course, these assumptions and methods of obtaining fault probabilities of syntactical elements and formulas are only some possible ways of doing so. For example, one might argue that the “authorship” of a formula is somewhat not clearly defined. What if user has originally written formula ax and then user alters the formula to become ? Who is the author of or both? For whose fault probability computation should the renewed modification of to count? Questions like this one need to be discussed and maybe evaluations using real data need to be accomplished in order to find a practical answer; or perhaps to find out that completely different approaches turn out to be reasonable. This is a topic of our future work.

Remark 4.5 By the definition of a DPI (Definition 3.1) stating that the KB K must be disjoint with the background knowledge B and the role B has within a DPI, namely to comprise all formulas that are definitely correct, we postulate that no formula must have a probability of zero. In a situation when this is not the case, a modified DPI must be used where such formulas have been moved from K to B.

Computation of Diagnosis Probabilities. In the following, we denote by ax (K) the set of logical connectives and quantifiers occurring in a formula ax (in the KB K) and by ( ) the signature of ax (of K).

Example 4.6 Considering the DL formula ax := Pet Animal hasOwner.Person, we have that and Pet, Animal, hasOwner, Person}.

We now suppose that either a fault probability is faulty”) of each element or the fault probability is faulty”) of each formula is given. For estimation of these probabilities any (combination) of the methods mentioned above might be employed. In case formula probabilities are given, diagnosis probabilities can be directly computed by Formula 4.3. Otherwise, the following pre-computations must be performed.

The fault probability p(ax) of ax can be calculated as the probability that at least one (occurrence of a) syntactical element in ax is faulty. So, p(ax) is equal to 1 minus the probability that none of the syntactical elements occurring in ax is faulty. Hence, under the assumption of mutual independence of syntactical faults concerning elements ,

where n(e) is the number of occurrences of syntactical element e in ax.

If p(ax) for all is known, the fault probability p(D) of any diagnosis can be determined as the probability that each formula in D is faulty whereas each formula in K \ D is correct, i.e. not faulty. Thence,

Recall that probabilities of all atomic events in a well-defined probability space must sum up to 1. As not every subset of K is a diagnosis, this is in general not the case. Therefore, diagnosis probabilities need to be normalized, i.e. each diagnosis probability p(D) must be divided by the sum of all diagnosis probabilities for diagnoses in . That is, the following adjustment is necessary:

We want to emphasize that the probability measures p(e) of syntactical elements e and p(ax) of formulas ax are not required to satisfy any conditions except for and for all and all (see Remark 4.5 why the intervals (0, 1] are open). In particular, no normalization is needed. The reason for this is that “e is faulty” and “ax is faulty” are assumptions about a single logical connective and a single logical formula, respectively. “D is the true diagnosis”, to the contrary, is an assumption about each formula in the KB K. So, the probabilities of two different syntactical elements are computed on the basis of two different probability spaces, namely is faulty”is not faulty”} and is faulty”is not faulty”} which clearly do not depend on each other at all. The same argumentation holds for probabilities of formulas.

More Reliable Probabilities through Observations. As we argued before, the basic fault information from which diagnosis probabilities are deduced might be rather vague. A usual way of dealing with scenarios of that kind, is to regard the initial probabilities as a first (a-priori) estimation and to gather additional information, e.g. by making measurements or observations, and exploit this information to adapt the a-priori estimation in order to obtain a more reliable a-posteriori estimation. The more additional information has been accumulated and incorporated, the more realistic is the resulting updated estimation of probabilities.

A well-known technique enabling computation of a-posteriori probabilities from a-priori probabilities is Bayes’ Theorem. Let p(D) be the a-priori probability of some and Obs be a new observation. Then, the a-posteriori probability p(D | Obs) of D, i.e. the probability that the true diagnosis taking into account the new information Obs, is computed according to Bayes’ Theorem as

where p(Obs) is the (a-priori) probability that observation Obs is made and p(Obs | D) is the (a-priori) probability that the observation Obs is made under the assumption that D is the true diagnosis, i.e. . That is, the a-priori probability p(D), i.e. the probability that without any additional knowledge, must be multiplied by p(Obs | D)/p(Obs) which is often referred to as the support Obs provides for D. If the support is greater than 1, then the a-posteriori probability of D is greater than its a-priori probability, otherwise the a-posteriori probability gets smaller after incorporating the new information Obs. Note that Bayes’ Theorem is only applicable to KB debugging if a suitable class of observations can be defined such that p(Obs) and p(Obs | D) can be computed for observations Obs of this class. As we shall see in Chapter 7, the assignment of test cases to either P or N is one such class of observations. For instance, and for sets of formulas over L are two such observations.

4.6.2 Using Probabilities for Diagnosis Computation

If available, formula fault probabilities can be exploited during construction of the pHS-tree (Algorithm 2, Chapter 4) in that most probable instead of minimum cardinality diagnoses are calculated first. To achieve that, breadth-first construction of the tree must be replaced by uniform-cost order of node expansion by means of the function p() that assigns a fault probability to each formula . Thereby, the “probability” p(nd) of a node in Algorithm 2 is defined through as

Notice that this formula extends the definition of Formula 4.3 to arbitrary subsets of K, not only diagnoses. Thus, Formula 4.3 is a special case of Formula 4.6.

First, note that we put “probability” of a node in quotation marks as, to be concise, each node (path) which is not yet a diagnosis, i.e. needs to be further expanded to become one, has probability zero (of being the true diagnosis ). For, a probability space is defined on a set of diagnoses and not on a set of arbitrary subsets nd of the KB. However, we misuse the diagnosis probability space in this case to determine the probability of “pseudo-diagnoses” in order to impose an order on the queue of open nodes in the tree. This will guarantee the finding of the most probable diagnoses first, as we shall see below (Proposition 4.17).

Second, note that no normalization, i.e. application of Formula (4.4), is necessary within the scope of the non-interactive Algorithm 2 since the aim here is only the expansion of nodes nd in the order of p(nd) and the return of the most probable identified diagnoses at a certain point in time. For this, the comparison of the probability of one node nd with the probability of another node suffices. Thus, no other calculations using the properties of a probability space are performed by Algorithm 2. We shall recognize in Chapter 9 that this will not hold for the interactive Algorithm 5 where Formula (4.4) is essential.

So, nodes nd are inserted into Q in a way descending order of node probabilities in Q is always maintained. Consequently, nodes with highest fault probability are processed first. This is practical since a user will usually be most interested in seeing those possible faults first that have the highest (estimated) probability to be the actual fault they seek.

However, one needs to be careful when using probabilities as weights in order not to lose the property of Algorithm 2 to compute minimal diagnoses only. To this end, the formula probabilities p(ax) for all must be adapted as

where the factor c is an arbitrary positive real number smaller than 0.5, e.g. . This transformation effects that all probabilities p(ax) become smaller than 50%. In other words, each formula must be more likely to be correct than faulty which in turn means that a minimal diagnosis is more likely than any of its supersets.

Definition 4.9. Let be some function that assigns to each some [0, 1]. Then, we denote by the function that assigns to each node some which is obtained by means of Formula 4.6 and p().

Lemma 4.14. Let where and a function which assigns to each some probability . Then holds.

Proof. According to Formula 4.6 and Definition 4.9 we have that

Then the probability can be computed from in that, for each formula ax in , we multiply by a factor because ax “moves” from K \ nd to nd. However, holds due to p(ax) < 0.5 and thus .

This result will be a key to proving the completeness, soundness and correctness of Algorithm 2 in the next Section.

The next definition characterizes a (partial) weighted pHS-tree, the type of hitting set tree constructed by Algorithm 2 given any function for all as input which is not necessarily specified in a way a breadth-first tree construction is forced.

Definition 4.10 (Weighted Pruned HS-Tree). Let be an admissible DPI and let [0, 1] be a weight function which assigns a weight to each node with the property that if . An edge-labeled and node-labeled tree T is called a weighted pruned HS-tree (wpHStree) w.r.t. and w() iff T is the result of constructing an HS-tree w.r.t. with due regard to the following rule

and the rules 2 to 6 as per Definition 4.8.

T is called a partial weighted pruned HS-tree w.r.t. and w() iff T is a weighted pruned HS-tree w.r.t. and w() where not all nodes in T have been labeled yet and non-labeled nodes have no successors.

Then, we have the following relationship between a (partial) pHS-tree and a (partial) wpHS-tree. An explanation why this holds will be given in Section 4.6.4.

Proposition 4.14. A (partial) pHS-tree w.r.t. is a (partial) wpHS-tree w.r.t. and w() where w() is a weight function which, additionally to the property postulated in Definition 4.10, satisfies if .

In general, a (partial) wpHS-tree w.r.t. and w() is not a (partial) pHS-tree w.r.t. .

Lemma 4.15. Algorithm 2 is a procedure for producing a wpHS-tree T w.r.t. and .

Proof. First, the property if postulated by Definition 4.10 holds by Lemma 4.14 and the fact that the function p given as input to Algorithm 2 satisfies for all . Moreover, the DPI provided as an input to Algorithm 2 is admissible, as postulated by Definition 4.10.

The compliance with rule 1 of Definition 4.7 as well as with rules 2 to 6 of Definition 4.8 is a simple consequence of Lemma 4.13. In the following we prove that rule 2 of Definition 4.7 and rule 1 of Definition 4.10 are satisfied.

• Definition 4.7, rule 2: Suppose a node nd is labeled by valid. Then it is added to in line 11. Since nd can only get a label different from closed if it is the only exemplar of this node in Q due to the duplicate criterion (lines 22-24), it must be the case that (line 7) after nd has been labeled by valid. Only nodes that get labeled by a conflict set can have successor nodes added to Q in line 15. Only nodes in Q can get a label (cf. lines 6 and 8). For nd to be added to Q at some later point in time there must be a proper subset of nd that is still in Q as each node newly added to Q is a proper superset of some node in Q (cf. line 15 which is the only position in the algorithm where nodes are added to Q). This is impossible since Q is ordered descending by . Hence, each proper subset of nd must have been ranked before nd in Q and thus must have already been labeled because nd is already labeled by assumption. Hence, if nd is labeled by valid, then it has no successors.

• Definition 4.10, rule 1: That nodes are processed and labeled in order of descending follows from the fact that new nodes are inserted into Q only in a way that the order of Q by descending is maintained (INSERTSORTED in line 15) and by the fact that always the first element of Q is selected to be labeled next (GETFIRST in line 6).

This completes the proof.

Let the relevant data of a wpHS-tree be defined as for a pHS-tree (cf. Remark 4.2). By the correctness of Lemma 4.15, we have:

Corollary 4.6. Algorithm 2 stores by the relevant data of

• a wpHS-tree w.r.t. and if Algorithm 2 stops due to Q = [], and

• a partial wpHS-tree w.r.t. and otherwise.

4.6.3 Correctness of Weighted Diagnosis Computation