In multi-context systems, heterogeneous contexts interact via nonmonotonic bridge rules. We seek to understand and give reasons for inconsistencies in such systems by means of diagnosis. For this purpose, we propose notions of consistency-based and abduction-based diagnosis, where diagnoses are characterized by sets of bridge rules. Interestingly, the notions of consistency-based and abduction-based diagnoses lead to the same sets of bridge rules which are potentially erroneous.
(1) where cs; c1 : : : ; cm are names of contexts and s; p1; : : : ; pm are beliefs of the respective contexts. Intuitively, rule (1) is applicable wrt. belief sets S1; : : : ; Sm of the respective contexts, if pi 2 Si, for 1 i j, and pk 62 Sk, for j+1 k m. If the rule is applicable, then its head s is added to the knowledge base of cs. Example 1. Assume a health care decision support system which contains the following contexts: a patient history database C1, a blood and X-Ray analysis database C2, a description logic ontology of diseases C3, and a disjunctive logic program implementing an expert system C4 which suggests proper treatments. ? This work was supported by the Vienna Science and Technology Fund (WWTF) under grant ICT 08-020.
Consider the following knowledge bases for these contexts, focusing on pneumonia (a lung disease treatable by antibiotics):
C1 = fallergy strong antibioticg C2 = f:blood marker ; xray pneumoniag C3 = fatypical pneumonia v pneumonia u marker g C4 = fgive s _ give w need antibiotic: give s need strong : ? give s; not allow strong : nothing required not need antibiotic; not need strong :g Contexts C1 and C2 provide the information that the patient is allergic to strong antibiotics, that a certain blood marker is not present, and that pneumonia was detected in the X-Ray. C3 classi es atypical pneumonia as a combination of pneumonia and the presence of a blood marker. C4 suggests a medication which is either a strong antibiotic s, a weak antibiotic w, or no medication at all.
The bridge rules of the MCS are given as: r1 = (3 : pneumonia(p)) r2 = (3 : marker (p)) r3 = (4 : need antibiotic) r4 = (4 : need strong ) r5 = (4 : allow strong ) (2 : xray pneumonia): (2 : blood marker ): (3 : pneumonia(p)): (3 : atypical pneumonia(p)): not (1 : allergy strong antibiotic): Rules r1 and r2 provide input for disease classi cation to the ontology, r3 and r4 link disease information with medication requirements, and r5 relates acceptance of strong antibiotics with an allergy check on the patient database. tu
The semantics of MCSs is de ned in terms of equilibria. An equilibrium consists of a belief state, i.e., a belief set Si for each context Ci, which is acceptable for Ci under the addition of beliefs from applicable bridge rules. Example 2. In our example there exists exactly one equilibrium S, and rules r1 and r3 are applicable wrt. S (for C3, a belief state S3 consists of all class instances):
S = (fallergy strong antibioticg; f:blood marker ; xray pneumoniag; fpneumonia(p)g; fneed antibiotic; give w g): tu Inconsistency in an MCS is the lack of an equilibrium. As the interaction and combination of heterogeneous systems can easily lead to unforeseen and intricate e ects, inconsistency is a major|according to our knowledge unaddressed| problem in MCSs. In order to provide support for restoring consistency, we seek to understand and give reasons for inconsistency by means of diagnosis. Example 3. As a running example, we consider a slightly modi ed version of Example 1, where the blood serum analysis shows presence of the blood marker:
C2 = fblood marker ; xray pneumoniag: This MCS is inconsistent since r2 and r4 become applicable, which require that strong antibiotic s is applied. This is in con ict with the patient's allergy.
We assume that every context is consistent without the in uence of bridge rules, therefore we characterize reasons for inconsistency in terms of bridge rules. De nition 1. Let M be an MCS and R a set of bridge rules. We write R j=M ? to say that the semantics of M using R as its set of bridge rules yields inconsistency. We write R 6j=M ? to say that M using R as its set of bridge rules has an equilibrium. In the following, BR denotes the original set of bridge rules of M , and heads(R) denotes the set of heads of rules in R transformed to facts. Diagnoses and Explanations for Inconsistency. In nonmonotonic reasoning, forcing rules to be applicable (or forcing them to be not applicable) can cause and prevent inconsistency. For our consistency-based diagnosis, we therefore consider pairs of sets of bridge rules, s.t. deactivating the rules in the one set and forcing the rules in the other to be active allows to establish consistency (i.e. an equilibrium) in the system.
De nition 2. A diagnosis D where R ; R+ BR and R
of an MCS M wrt. BR is a pair D = (R ; R+), \ R+ = ; s.t. BR n R [ heads(R+) 6j=M ?.
Noticeably, this de nition resembles the notion of anti-explanation [
Example 4. Notable diagnoses in our running example are the following: (fr1g; ;), (fr2g; ;), (fr4g; ;), and (;; fr5g).
Accordingly, deactivating r1, r2, or r3, resp. forcing r5 to be active, will result in a consistent MCS. All other diagnoses are pointwise supersets thereof. A research issue are preferred diagnoses wrt. an application domain. Minimality criteria (e.g. applied to preference orderings) can be used for this purpose. For domains where the removal of bridge rules is preferred to the forced activation of unjusti ed rules, we specialize D to obtain diagnoses of the form (R ; ;) only. We compare such diagnoses using subset-minimality as preference criterion. De nition 3. An s-diagnosis1 D of an MCS M wrt. BR is any set R s.t. BR n R 6j=M ?. An s-diagnosis is minimal i it is minimal wrt. . Example 5. Minimal s-diagnoses in our example are fr1g, fr2g and fr4g.
Motivated by abduction-based diagnosis, we consider an explanation as a pair of sets of rules whose joint (de-)activation reproduces the observed inconsistency. De nition 4. An inconsistency explanation E of an MCS M wrt. BR is a tuple E = (R ; R+), where R ; R+ BR and R \ R+ = ; s.t. R [ heads (R+) j=M ?.
Again we specialize the de nition to the rst component. In this case we additionally require that an explanation has no consistent superset, to avoid reproducing irrelevant inconsistencies. For instance, the program fa not a:g is inconsistent under the answer set semantics, but its superset fa not a: a:g is consistent. 1 The pre x s stands for simple.
tu BR tu Example 6. The only minimal s-inconsistency explanation E+ in our running example is fr1; r2; r4g; its rules are thus necessary to derive inconsistency. tu
The union of all minimal diagnoses (explanations) is a set of rules relevant for repairing (causing) inconsistency. Interestingly, these unions coincide (cf. also our example with minimal diagnoses fr1g, fr2g, fr4g, resp. explanation fr1; r2; r4g). Theorem 1. For an inconsistent MCS, the unions of all minimal s-diagnoses Dm and all minimal s-inconsistency explanations Em+ coincide, i.e., S Dm = S Em+ . Discussion and Future Work. Minimal D diagnoses, i.e., giving preference to rule deactivation, correspond to consistent MCSs, and thus may be used for restoring consistency. However, the resulting options for repair may be too limiting for certain application domains. In our example, the option to disregard the allergy and prescribe strong antibiotics is missed. Rule deactivation either ignores the X-Ray, respectively blood test results, or that atypical pneumonia requires strong antibiotics, with the e ect that either the disease is ignored at all, or a medication is suggested which might be to weak.
The study of more speci c preference relations between diagnoses is a further research issue in our ongoing project on inconsistency management for MCSs. In addition to an investigation of abstract properties, preferences between diagnoses that emerge from application speci c preferences on bridge rules or contexts, e.g., trust levels, are of particular interest. Moreover, we currently investigate approximations of diagnoses given incomplete information (when context knowledge is not fully disclosed), e.g., due to information hiding or security concerns.
Our aim is to provide support for resolving inconsistencies based on preferred diagnoses and inconsistency explanations. Note that due to presence of nonmonotonic contexts (witnessed by context C4 in our example) the problem is more general than the problem of ontology merging (which may serve to build part of an MCS, however). Moreover, a decision for repair may need to take further domain knowledge into account, as illustrated by our example, where it is not obvious how to resolve the dilemma. Providing a declarative policy language for (semi-)automatic support for repair is the suggestive goal. Also, we plan to apply and evaluate the developed techniques in real world applications.