Towards a Policy Language for Managing Inconsistency in Multi-Context Systems?

Abstract

Multi-context systems are a formalism for interlinking knowledge based system (contexts) which interact via (possibly nonmonotonic) bridge rules. Such interlinking provides ample opportunity for unexpected inconsistencies. These are undesired, and come in different categories: some are serious and must be inspected by a human operator, while some should simply be repaired automatically. However, no one-fits-all solution exists, as these categories depend on the application scenario. To tackle inconsistencies in a general way, we thus propose a declarative policy language for inconsistency management in multicontext systems. We define syntax and semantics, give methodologies for applying the language in real world applications, and discuss a possible implementation.

Introduction

Powerful knowledge based applications can be built by interlinking smaller existing knowledge based systems. Multi-context systems (MCSs) [ 5 ], based on [ 18, 6 ], are a generic formalism that captures heterogeneous knowledge bases (contexts) which are interlinked using (possibly nonmonotonic) bridge rules.

The advantage of building a system from smaller parts however poses the challenge of unexpected inconsistencies due to unintended interaction of system parts. Such inconsistencies are undesired, as (under common principles) inference becomes trivial. Explaining reasons for inconsistency in MCSs has been investigated in [ 13 ]: several independent inconsistencies can exist in a MCS, and each inconsistency usually comes with more than one possibility to repair it.

For example, imagine a hospital information system which links several databases and suggests treatments for patients. A simple inconsistency which can be automatically ignored would be if a patient enters her birth date correctly at the front desk, but swaps two digits filling in a form at the X-ray department. An entirely different story is, if we have a patient who needs treatment, but all options conflict with some allergy of the patient. Here attempting an automatic repair may not be a viable option: a doctor should inspect the situation and make a decision. ? This research has been supported by the Vienna Science and Technology Fund (WWTF) project

ICT08-020.

In the light of such scenarios, tackling inconsistency requires individual strategies and targeted (re)actions, depending on the type of inconsistency and on the application. We thus propose IMPL, a declarative policy language providing a means to specify inconsistency management strategies for MCSs. Briefly, our contributions are as follows. • We define the syntax of IMPL, inspired by answer set programs (ASPs) [ 17 ]. In particular, we specify input for policy reasoning, in terms of reserved predicates. These predicates encode inconsistency analysis results in terms of [ 13 ]. Furthermore, we specify action predicates that can be derived in rules. Actions provide a means to counteract inconsistency by modifying the MCS, and may involve interaction with a human operator. • We define IMPL semantics in terms of a three-step process which calculates models of a policy, then determines effects of actions which are present in such model (this possibly involves user interaction), and finally applies these effects to the MCS. • We provide methodologies for integrating IMPL into application scenarios, and discuss useful language extensions and a potential realization using the acthex formalism [ 2 ]. 2

Preliminaries

Multi-context systems (MCSs). A heterogeneous nonmonotonic MCS [ 5 ] consists of contexts, each composed of a knowledge base with an underlying logic, and a set of bridge rules which control the information flow between contexts.

A logic L = (KBL, BSL, ACCL) is an abstraction which captures many monotonic and nonmonotonic logics, e.g., classical logic, description logics, or default logics. It consists of the following components, the first two intuitively define the logic’s syntax, the third its semantics: • KBL is the set of well-formed knowledge bases of L. We assume each element of

KBL is a set of “formulas”. • BSL is the set of possible belief sets, where a belief set is a set of “beliefs”. • ACCL : KBL → 2BSL assigns to each KB a set of acceptable belief sets. Since contexts may have different logics, this allows to model heterogeneous systems. Example 1. For propositional logic Lprop under the closed world assumption over signature Σ, KB is the set of propositional formulas over Σ; BS is the set of deductively closed sets of propositional Σ-literals; and ACC(kb) returns for each kb a singleton set, containing the set of literal consequences of kb under the closed world assumption.

A bridge rule models information flow between contexts: it can add information to a context, depending on the belief sets accepted at other contexts. Let L = (L1, . . . , Ln) be a tuple of logics. An Lk-bridge rule r over L is of the form (k : s) ← (c1 : p1), . . . , (cj : pj ), not (cj+1 : pj+1), . . . , not (cm : pm). (1) where k and ci are context identifiers, i.e., integers in the range 1, . . . , n, pi is an element of some belief set of Lci , and s is a formula of Lk. We denote by hb (r) the formula s in the head of r.

A multi-context system M = (C1, . . . , Cn) is a collection of contexts Ci = (Li, kbi, bri), 1 ≤ i ≤ n, where Li = (KBi, BSi, ACCi) is a logic, kbi ∈ KBi tu a knowledge base, and br i is a set of Li-bridge rules over (L1, . . . , Ln). By IN i = {hb (r) | r ∈ bri} we denote the set of possible inputs of context Ci added by bridge rules. For each H ⊆ IN i it is required that kbi ∪ H ∈ KBLi . Similar to IN i, OUT i denotes output beliefs of context Ci, which are those beliefs p in BSi that occur in some bridge rule body in brM as “(i:p)” or as “not (i:p)” (see also [ 13 ]). By brM = Sn i=1 br i we denote the set of all bridge rules of M , and by ctxM = {C1, . . . , Cn} the set of all contexts of M .

Example 2 (generalized from [ 13 ]). Consider a MCS M1 in a hospital which comprises the following contexts: a patient database Cdb , a blood and X-Ray analysis database Clab , a disease ontology Conto , and an expert system Cdss which suggests proper treatments. Knowledge bases are given below; initial uppercase letters are used for variables and description logic concepts.

kbdb = {person(sue, 02/03/1985 ), allergy (sue, ab1 )}, kblab = {customer (sue, 02/03/1985 ), test (sue, xray , pneumonia), test (Id , X, Y ) → ∃D : customer (Id , D)), customer (Id , X) ∧ customer (Id , Y ) → X = Y }, kbonto = {Pneumonia u Marker v AtypPneumonia}, kbdss = {give(Id , ab1 ) ∨ give(Id , ab2 ) ← need (Id , ab).

give(Id , ab1 ) ← need (Id , ab1 ).

¬give(Id , ab1 ) ← not allow (Id , ab1 ), need (Id , Med ).}.

Context Cdb uses propositional logic (see Example 1) and provides information that Sue is allergic to antibiotics ‘ab1 ’. Context Clab is a database with constraints which stores laboratory results connected to Sue: pneumonia was detected in an X-ray. Constraints enforce, that each test result must be linked to a customer record, and that each customer has only one birth date. Conto specifies that presence of a blood marker in combination with pneumonia indicates atypical pneumonia. This context is based on AL, a basic description logic [ 1 ]: KBonto is the set of all well-formed theories within that description logic, BSonto is the powerset of the set of all assertions C(o) where C is a concept name and o an individual name, and ACConto returns the set of all concept assertions entailed by a given theory. Cdss is an ASP that suggests a medication using the give predicate.

We next give schemas for bridge rules of M1.

r1 = (lab : customer (Id , Birthday )) ← (db : person(Id , Birthday )). r2 = (onto : Pneumonia(Id )) ← (lab : test (Id , xray , pneumonia)). r3 = (onto : Marker (Id )) ← (lab : test (Id , bloodtest , m1 )). r4 = (dss : need (Id , ab)) ← (onto : Pneumonia(Id )). r5 = (dss : need (Id , ab1 )) ← (onto : AtypPneumonia(Id )). r6 = (dss : allow (Id , ab1 )) ← not (db : allergy (Id , ab1 ).

Rule r1 links the patient records with the lab database (so patients do not need to enter their data twice). Rules r2 and r3 provide test results from the lab to the ontology. Rules r4 and r5 link disease information with medication requirements, and r6 associates acceptance of the particular antibiotic ‘ab1 ’ with a negative allergy check on the patient database. tu

Equilibrium semantics [ 5 ] selects certain belief states of a MCS M = (C1, . . . , Cn) as acceptable. A belief state is a sequence S = (S1, . . . , Sn), s.t. Si ∈ BSi. A bridge rule (1) is applicable in S iff for 1 ≤ i ≤ j: pi ∈ Sci and for j < l ≤ m: pl ∈/ Scl . Let app(R, S) denote the set of bridge rules in R that are applicable in belief state S. Then a belief state S = (S1, . . . , Sn) of M is an equilibrium iff, for 1 ≤ i ≤ n, the following condition holds: Si ∈ ACCi(kbi ∪ {hd (r) | r ∈ app(br i, S)}).

In our running example we use bridge rules with variables, here we disregard the issue of instantiating these rules [ 16 ]. We denote by r[X|c] the ground version of bridge rule r where variable X has been substituted by constant c.

Example 3 (ctd). MCS M1 has one equilibrium S = (Sdb , Slab , Sonto , Sdss ), where Sdb = kbdb , Slab = {customer (sue, 02/03/1985 ), test (sue, xray , pneumonia)}, Sonto = {Pneumonia(sue)}, and Sdss = {need (sue, ab), give(sue, ab2 ), ¬give(sue, ab1 )}. Moreover, the following bridge rules of M1 are applicable under S: r1[Id |sue, Birthday |02/03/1985 ], r2[Id |sue], and r4[Id |sue]. tu Explaining Inconsistency in MCSs. Inconsistency in a MCS is the lack of an equilibrium[ 13 ]. Note that no equilibrium may exist even if all contexts are ‘paraconsistent’ in the sense that ACC is never empty. No information can be obtained from an inconsistent MCS, e.g., inference tasks like brave or cautious reasoning on equilibria become trivial. To analyze, and eventually repair, inconsistency in a MCS, we use the notions of consistency-based diagnosis and entailment-based inconsistency explanation [ 13 ], which characterize inconsistency by sets of involved bridge rules.

Intuitively, a diagnosis is a pair (D1, D2) of sets of bridge rules which represents a concrete system repair in terms of removing rules D1 and making rules D2 unconditional. The intuition for considering rules D2 as unconditional is that the corresponding rules should become applicable to obtain an equilibrium. One could consider more fine-grained changes of rules such that only some body atoms are removed instead of all. However, this increases the search space while there is little information gain: every diagnosis (D1, D2) as above, together with a witnessing equilibrium S, can be refined to such a generalized diagnosis. Dual to that, inconsistency explanations (short: explanations) separate independent inconsistencies. An explanation is a pair (E1, E2) of sets of bridge rules, such that the presence of rules E1 and the absence of heads of rules E2 necessarily makes the MCS inconsistent. In other words, bridge rules in E1 cause an inconsistency in M which cannot be resolved by considering additional rules already present in M or by modifying rules in E2 (in particular making them unconditional). See [ 13 ] for formal definitions of these notions, relationships between them, and more background discussion.

Example 4 (ctd). Consider a MCS M2 given by our example MCS M1 with different knowledge bases kbdb = {person(sue, 03/02/1985 ), allergy (sue, ab1 )} (i.e., month and day of the birth date are swapped) and kblab containing an additional finding test (sue, bloodtest , m1 ). M2 is inconsistent with Em±(M2) = {e1, e2} and Dm±(M2) = {d1, d2, d3, d4}, where e1 = ({r10}, ∅), e2 = ({r20, r0 , r50}, {r60}), d1 = ({r10, r20}, ∅), d2 = 3 ({r10, r30}, ∅), d3 = ({r10, r50}, ∅), d4 = ({r10}, {r60}), and where r10 = r1[Id |sue, Birthday |03/02/1985 ], and rj0 = rj [Id |sue], j ∈ {2, 3, 5, 6}. Em±(M2) characterizes two inconsistencies in M2, namely e1: Clab does not accept any belief set because constraint customer (Id , X) ∧ customer (Id , Y ) → X = Y is violated; furthermore e2: if we assume e1 is repaired, then Conto accepts AtypPneumonia(sue) in its unique accepted belief set, therefore r5[Id |sue] imports the need for ab1 into Cdss which makes Cdss inconsistent due to Sue’s allergy. 3

Policy Language IMPL

tu tu Dealing with inconsistency in an application scenario is difficult, because even if inconsistency analysis provides information how to restore consistency, it is not obvious which choice of system repair is rational. It may not even be clear whether it is wise at all to repair the system by changing bridge rules.

Example 5 (ctd). Repairing e1 by ignoring the birth date (which differs at the granularity of months) may be the desired reaction and could very well be done automatically. On the contrary, repairing e2 by ignoring either the allergy or the illness is a decision that should be left to a doctor, as every possible repair could cause serious harm to Sue. Therefore, managing inconsistency in a controlled way is crucial. To address these issues, we propose a declarative policy language IMPL, which provides a means to create policies for dealing with inconsistency in MCSs. Intuitively, an IMPL policy specifies (i) which inconsistencies are repaired automatically and how this shall be done, and (ii) which inconsistencies require further external input, e.g., by a human operator, to make a decision on how and whether to repair the system. Note that we do not rule out automatic repairs, but — contrary to previous approaches — automatic repairs are done only if a given policy specifies to do so, and only to the extent specified by the policy.

Since a major point of MCSs is to abstract away context internals, IMPL treats inconsistency by modifying bridge rules. For the scope of this work we delegate any potential repair by modifying the kb of a context to the user. The effect of applying an IMPL policy to an inconsistent MCS M is a modification (A, R), which is a pair of sets of bridge rules which can be (but not necessarily are) part of brM , and which are syntactially compatible with M . Intuitively, a modification specifies bridge rules A to be added to M and bridge rules R to be removed from M , similar as for diagnoses without restriction to the original rules of M .

In the following we formally define syntax and semantics of IMPL. 3.1

Syntax.

We assume disjoint sets C, V, Ord , Built , and Act , of constants, variables, ordinary predicate names, built-in predicate names, and action names, resp. An atom is of the form p(t1, . . . , tk), 0 ≤ k, ti ∈ T , where the set of terms T is defined as T = C ∪ V , and p is a (built-in or ordinary) predicate name or an action name. As usual, an atom is ground if ti ∈ C for 0 ≤ i ≤ k. The set AAct of action atoms has p ∈ Act , while AOrd , respectively ABuilt , denotes the set of ordinary atoms having p ∈ Ord , respectively the set of built-in atoms with p ∈ Built .

Definition 1. An IMPL policy is a set of rules of the form h ← a1, . . . , aj , not aj+1, . . . , not ak. (2) where h is an atom from AOrd ∪ AAct or ⊥, every ai is from AOrd ∪ ABuilt , for 1 ≤ i ≤ k, and ‘not‘ is negation as failure.

Given a rule r, we denote by H(r) its head, by B+(r) = {a1, . . . , aj } its positive body atoms, and by B−(r) = {aj+1, . . . , ak} its negative body atoms. A rule is ground if it contains ground atoms only. A ground rule with k = 0 is a fact.

An IMPL policy P is intended to be evaluted provided some input IM respresenting relevant information about a given MCS M . The idea is that its evaluation yields certain actions to be taken upon inconsistency, which effect modifications of the MCS with the goal of restoring consistency. For representing basic inputs and actions, we consider specific predicate and action names. Corresponding atoms follow a particular syntax and semantics. We first present their syntax and provide intuitions of their semantics. Reserved Predicates. Atoms with reserved predicate names provide a policy with information about the system at hand, and about results of inconsistency analysis on that system. Essentially, these atoms describe bridge rules, diagnoses, and explanations of a given MCS. Note that elements of these descriptions, like contexts, bridge rules, beliefs, etc., are assumed to be represented by suitable constants. For brevity, when referring to an element represented by a constant c, we identify it with the constant (omitting ‘represented by constant’). • ruleHead (r, c, s) denotes that the head of bridge rule r at context c is the formula s. • ruleBody +(r, c, b) (resp., ruleBody −(r, c, b)) denotes that bridge rule r contains body literal ‘(c : b)’ (resp., body literal ‘not (c : b)’). • modAdd (m,r) (resp., modDel (m,r)) denotes that modification m adds (resp., deletes) bridge rule r (r is represented using ruleHead and ruleBody ). • diag (m) denotes that modification m is a minimal diagnosis in M . • explNeed (e, r) (resp., explForbid (e, r)) denotes that the minimal explanation (E1,

E2) ∈ Em±(M ) identified by constant e contains bridge rule r ∈ E1 (resp., E2). • member (ms, m) denotes that modification m belongs to a set of modifications ms. • #id (t, c, i) is a builtin predicate with the intention to handle the assignment of ‘fresh’ constants (not appearing in the input to a policy) as identifiers more easily (i.e., it facilitates limited value invention). Intuitively, #id (t, c, i) is true iff c is a constant, i is a non-negative integer constant (from a fixed, finite range, see also Sec. 3.2), and t = ci, for a particular constant ci.

Further knowledge used as input for policy reasoning can easily be defined using additional (auxiliary) predicates. For instance, to encode preference relations (e.g., as in [ 14 ]) between system parts, diagnoses, or explanations, an atom preferredContext (c1, c2) could denote that context c1 is considered more reliable than context c2. The extensions of such auxiliary predicates need to be defined by the rules of the policy (ordinary predicates) or provided by the implementation (built-in predicates), i.e., the ‘solver’ used to evaluate the policy.

As for notation, given a set of ground atoms IM and a constant c, we denote by ruleI (c) the bridge rule identified by c and characterized in I by ruleHead and ruleBody ± atoms. Similarly, we denote by modificationI (c) = (A, R) the modification c characterized in I by modAdd , modDel , ruleHead and ruleBody ± atoms. Note, that reserved predicates, except for the built-in #id , are also allowed to occur in the head of policy rules.

Actions. Let us turn to the syntax and intuitive semantics of action atoms built from predefined action names. (We prefix action names from Act with @). We assume that actions are independent from one another and each action yields a modification of the MCS. This modification can depend on external input, e.g., obtained by user interaction.

We distinguish three categories of actions: (a) actions that affect individual bridge rules, (b) actions that affect multiple bridge rules, and (c) actions that involve user interaction (and affect individual or multiple bridge rules).

The following actions affect individual bridge rules. • @delRule(r) removes bridge rule r from the MCS (r is represented using ruleHead and ruleBody ). • @addRule(r) adds bridge rule r to the MCS. • @addRuleCondition+(r, c, b) (resp., @addRuleCondition−(r, c, b)) adds body literal (c : b) (resp., not (c : b)) to bridge rule r. • @delRuleCondition+(r, c, b) (resp., @delRuleCondition−(r, c, b)) removes body literal (c : b) (resp., not (c : b)) from bridge rule r. • @makeRuleUnconditional (r) makes bridge rule r unconditional.

The following actions (potentially) affect multiple bridge rules. • @applyMod (m) applies modification m to the MCS. • @applyModAtContext (m, c) applies those modifications of m to the MCS which modify bridge rules at context c. Subsequently, we call this the projection of modification m to context c.

The following actions involve user interaction. • @guiSelectMod (ms) displays a GUI for choosing from the set of modifications ms.

The chosen modification is applied to the MCS. • @guiEditMod (m) displays a GUI for editing modification m. The resulting modification is applied to the MCS. • @guiSelectModAtContext (ms, c) projects modifications in ms to c, displays a GUI for choosing among them and applies the chosen modification to the MCS. • @guiEditModAtContext (m, c) projects modification m to context c, displays a GUI for editing it, and applies the resulting modification to the MCS.

The core fragment of IMPL consists of actions @delRule, @addRule, @guiSelectMod , and @guiEditMod , which are sufficient for realizing all actions described above. Actions not in the core fragment exist for convenience of use: they provide a means for projection and modifying only parts of rules which otherwise would need to be encoded using auxiliary predicates and core actions.

Example 7. Given a set of ground atoms IM , making bridge rules r with foo(r) ∈ IM unconditional can be achieved using a single rule with the action:

@makeRuleUnconditional (R) ← foo(R).

The following IMPL policy fragment achieves the same using only core actions:

% associate new constant with R to get identifier for rule derived from R aux (Rid , R) ← foo(R), #id (Rid , R, 1). % copy existing rule heads (don’t copy body literals) ruleHead (Rid , C, S) ← ruleHead (R, C, S), aux (Rid , R). % trigger actions @delRule(R) ← aux (Rid , R).

@addRule(Rid ) ← aux (Rid , R). (Here and in the following, lines starting with % indicate comments.) tu tu Example 8 (ctd). Figure 1 shows three policies for managing inconsistency in M2. Let us briefly illustrate their intended behaviour (before turning to a formal definition of semantics next). P1 deals with inconsistencies at Clab : if an explanation concerns only bridge rules at Clab , an arbitrary diagnosis is applied at Clab , other inconsistencies are not handled. Intuitively, applying P1 to M2 yields M3 (any chosen diagnosis removes exactly r10 at Clab ): M3 is still inconsistent due to e2 but no longer due to e1. P2 extends P1 by adding an ‘inconsistency alert formula’ alert to Clab iff an inconsistency was automatically repaired at Clab . Finally, P3 is a different approach which displays a choice of all minimal diagnoses to the user if at least one diagnosis exists.

Note, that we did not combine automatic actions and user-interactions; this would require more involved policies or an iterative methodology (cf. Sec. 4). 3.2

Semantics

The semantics of IMPL is defined in three steps: (i) policy answer sets are defined for a policy together with some input, each answer set represents a set of actions (to be executed); (ii) every action has associated effects in terms of a modification (A, R), they can be nondeterministic (and thus only determined by executing the action). Finally (iii) materializing the effects of a set of (executed) actions is defined by combining their effects, i.e., modifications (componentwise union), and applying the respective changes to the MCS at hand. We next describe these steps more formally.

Action Determination. We define IMPL policy answer sets similar to the stable model semantics [ 17 ]. Given a MCS M , we associate with it a finite (nonempty) set of constants CM ⊂ C, used as identifiers for representing its elements by means of the (ordinary) reserved predicates, as well as a finite set of integer constants CN ⊂ C. Furthermore, let Cid be a set of ‘fresh’ constants, i.e., disjoint from CM ∪ CN , containing exactly one constant ci ∈ C for every (pair of constants) c ∈ CM and i ∈ CN , and let id be a fixed (built-in) one-to-one mapping from CM × CN to Cid .

For a policy P , let cons(P ) ⊂ C denote the set of constants appearing in P . The policy base BP of P (given M ) is the set of ground atoms that can be built using ordinary reserved predicate and action names, as well as any auxiliary ordinary predicate and action names appearing in P , and constants from CP,M = cons(P ) ∪ CM ∪ CN ∪ Cid .

The grounding of P , grnd (P ) is given by grounding its rules wrt. CP,M in the usual way. An interpretation is a set of ground atoms I ⊆ BP .

For an atom a ∈ BP , as usual I |= a iff a ∈ I, and for a ground built-in atom a of the form #id (t1, t2, t3), it holds that I |= a iff (t2, t3) is in the domain of id and t1 = id (t2, t3). For a ground rule r, (i) I |= B(r) iff I |= a for every a ∈ B+(r) and 8% domain predicate for eplanations 9 P1 = >>>>>>>>>>>>>>>><iiie%nnnxcccpfiLNNln(aoodEbttoLL)←uaa←tbbew((exEEhxpepl))t(lh←←NEere)eee,oxxdnnpp(eollEFNteoi,xenRrpecbdl)aNi(.dnEoa(ttE,eLioRxa,npR)bl,o(()rnEE,ulry)l)ue.c←lHeoHeneacexdeapr(dnlRFs(oR,brCr,biC,diFdg,e(F)E,r)uC,,l RCe6=s)6 =.actlacCbla.lbab. >>>>>>>>=>>>>>>>> >>>% guess a unique diagnosis to apply >>>> >>>in(D) ← not out (D), diag(D), incLab. out (D) ← not in(D), diag(D), incLab.>> >>>>>>>>>>:u@%saeapOpppnllyeyM←doiadignAn(otDCsios).np⊥treox←jetc(itDend,(cAtola)bC,)iln←ab( Biufs)oe,nADe i6=wagaB(s D.se⊥)l.e←ctednot useOne, incLab. >>>>>>>;>>> 8% inconsistency alert 9 P2 = <ruleHead (ralert , clab , alert ). = ∪ P1 :@addRule(ralert ) ← incLab.; 8% let the user choose from all diagnoses if there is a diagnosis9 P3 = <member (md , X) ← diag(X). = :@guiSelectMod (md ). ;

I 6|= a for all a ∈ B−(r), and (ii) I |= r iff I |= H(r) or I 6|= B(r). Then, I is a model of P , denoted I |= P , iff I |= r for all r ∈ grnd (P ). The FLP-reduct [ 15 ] of P wrt. an interpretation I, denoted fP I , is the set of all r ∈ grnd (P ) such that I |= B(r). Definition 2 (Policy Answer Sets). Let P be an IMPL policy P , and let IM ⊆ BP be an input for P . An interpretation I ⊆ BP is a policy answer set of P for IM iff I is a ⊆-minimal model of fP I ∪ IM . By AS(P, IM ) we denote the set of all policy answer sets of P for IM .

Effect Determination. We define the effects of action predicates @a ∈ Act by nondeterministic functions f@a. Nondeterminism is required to due to external input, resp. user interaction. An action is evaluated wrt. a policy answer set.

Definition 3. Given a policy answer set I, and an action α = @a(t1, . . . , tk) in I, an effect of α wrt. I, denoted effI (α), is a modification (A, R) = f@a(I, t1, . . . , tk). Action predicates of the IMPL core fragment have the following semantic functions. (For brevity we omit semantics of actions that are not in the core fragment.) • f@delRule (I, r) = (∅, {ruleI (r)}). • f@addRule (I, r) = ({ruleI (r)}, ∅). • f@guiSelectMod (I, ms) = modificationI (m), for some modification m such that m ∈ {m | member (ms, m) ∈ I} (the user’s selection after being displayed the choice among modifications {modificationI (m) | member (ms, m) ∈ I}). • f@guiEditMod (I, m) = (A0, R0), where (A0, R0) is some modification (resulting from the user interaction after being displayed an editor for the modification (A, R) = modificationI (m)).

Note, that no order of evaluating actions is specified or required. We say that a set EI of modifications is an effect set for a policy answer set I, iff it contains exactly one effect effI (α) for every α in I.

Effect Materialization Once the effects of actions have been determined, an overall modification is calculated by componentwise union over all individual modifications. Finally, this overall modification is materialized in the MCS.

Definition 4. Given a MCS M and a policy answer set I, a materialization of I in M is a MCS M 0 obtained from M by replacing its set of bridge rules brM by the set brM \ R ∪ A, where (A, R) = S(A,R) ∈ EI (A, R), for an effect set EI for I. Note that by definition addition of bridge rules has precedence over removal.3

Eventually, we can define modifications of a MCS that are accepted by a corresponding policy for managing inconsistency. Skipping a straightforward formal definition, let us say that a set of ground atoms IM is a proper input for an IMPL policy P wrt. a MCS M , if it properly encodes M , Dm±(M ), and Em±(M ) using reserved predicates. Definition 5. Given a MCS M , an IMPL policy P , and a proper input IM for P wrt. M , then a modified MCS M 0 is an admissible modification of M wrt. policy P iff M 0 is the materialization of some policy answer set I ∈ AS(P ∪ IM ).

Example 9 (ctd). For brevity we do not give a full account of a proper IM2 . Intuitively IM2 = Sa ∈ {e1,e2,d1,d2,d3,d4} Ia where Iei represents explanation ei and Idi represents diagnosis di, e.g., Ie1 is described in Ex. 6. Evaluating P2 ∪ IM2 yields four policy answer sets; one is I1 = IM2 ∪ {expl (e1), expl (e2), incNotLab(e2), incLab, in(d1), out (d2), out (d3), out (d4), useOne, ruleHead (ralert , clab , alert ), @addRule(ralert ), @applyModAtContext (d1, clab )}. Evaluating P3 ∪ IM2 yields exactly one policy answer set, which is I2 = IM2 ∪ {@guiSelectMod (diag )}.

From I1 we obtain a single admissible modification of M wrt. P2: add bridge rule ralert and remove r10. Determining the effect of I2 involves user interaction; thus multiple materializations of I2 exist. For instance, if the user chooses to ignore Sue’s allergy (and birth date) by selecting d4 (and probably imposing additional monitoring for Sue), we obtain an admissible modification of M which adds bridge rule r60 and removes r10. tu 4

Methodologies of Applying IMPL and Realization

For applying IMPL and integrating it with a MCS and user interaction, we next develop methodologies, based on a simple system design shown in Figure 2. Due to space constraints, we only give an informal discussion.

We represent the MCS as containing a store of modifications. The semantics evaluation component performs reasoning tasks on the MCS and invokes the inconsistency manager in case of an inconsistency. This inconsistency manager uses the inconsistency analysis component4 to provide input for the policy engine which calculates policy answer sets of a given IMPL policy wrt. the MCS and its inconsistency analysis result. This policy evaluation step results in action executions potentially involving user interactions and causes changes to the store of modifications, which are subsequently materialized. Finally the inconsistency manager hands control back to the semantics evaluation component. Let us discuss principal modes of operation and their merits next. 3 There is no particular reason for this choice of precedence; one just has to be aware of it when specifying a policy. 4 For realizations of this component we refer to [ 3, 13 ].

Multi

Context

System

Store of

Modifi cations

Semantics

Evaluation

Inconsistency

Analysis

Inconsistency

Manager

Policy

Engine

User

Interaction

Policy

control flow

data flow

Reason and Manage once. This mode of operation evaluates the policy once, if the effect materialization does not repair inconsistency in the MCS, no further attempts are made and the MCS stays inconsistent. This mode while simple may not be satisfying in practice.

We can improve on the approach by extending actions with priority: the result of a single policy evaluation step then is a sequence of sets of actions, corresponding to several attempts for repairing the MCS. This can be exploited for writing policies that ensure repairs, by first attempting a ‘sophisticated’ repair possibly involving user interaction, and — if this fails — to simply apply some diagnosis to ensure consistency while the problem may be further investigated.

Reason and Manage iteratively. We now consider a mode where failure to restore consistency simply invokes policy evaluation again on the modified but still inconsistent system. This is useful if user interaction involves trial-and-error, especially if multiple inconsistencies occur — some might be more difficult to counteract than others.

Another positive aspect of iterative policy evaluation is, that policies may be structured, e.g., as follows: (a) classify inconsistencies into automatically vs manually repairable; (b) apply actions to repair one of the automatically repairable inconsistencies; if such inconsistencies do not exist (c) apply user interaction actions to repair one (or all) of the manually repairable inconsistencies. Such policy structuring follows a divide-andconquer approach, trying to focus on individual sources of inconsistency and to disregard interactions between inconsistencies as much as possible. If user interaction consists of trial-and-error bugfixing, fewer components of the system are changed in each iteration, and the user starts from a situation where only critical (i.e. not automatically repairable) inconsistencies are present in the MCS. Moreover, such policies may be easier to write and maintain.

Termination of iterative methodologies is not guaranteed. However one can enforce termination by limiting the number of iterations, possibly by extending IMPL with a control action that configures this limit.

In iterative mode, passing information from one iteration to the next can be useful. This can be accomplished by extending IMPL with add and delete actions which modify an iteration-persistent knowledge base, which is given to a policy as further input facts, represented using an additional dedicated predicate.

Realization in acthex The acthex formalism [ 2 ] extends answer set programs with external computations in bodies of rules, and action in heads of rules. Actions have an effect on an environment and this effect can use information from the answer set in which the action is present. Using acthex for realizing IMPL is a good choice because acthex already natively provides several features necessary for IMPL: external atoms can be used to access external information, and acthex actions come with weights for creating ordered execution schedules for actions occurring withinin the same answer set of an acthex program. Based on this, IMPL can be implemented by a rewriting to acthex, with acthex actions implementing IMPL actions, and acthex external predicates providing information about the MCS to the IMPL policy.

Using acthex to implement IMPL facilitates further extensions of IMPL, since new actions and external atoms can be added to acthex with little effort. 5

Conclusion

A language related to IMPL is the action language IMPACT [ 22 ], a declarative formalism for actions in distributed and heterogeneous multi-agent systems. While most parts of IMPL could be embedded in IMPACT, the latter is a very rich general purpose formalism, which is difficult to manage compared to the special purpose language IMPL. Furthermore, user interaction is not directly supported in IMPACT.

Policy languages have been studied in detail in the fields of access control, e.g., surveyed in [ 4 ], and privacy restrictions [ 11 ]. Notably, PDL [ 10 ] is a declarative policy language based on logic programming which maps events in a system to actions. It is richer than IMPL wrt. action interdependencies, whereas actions in IMPL have a richer internal structure and depend on the content of a policy answer set. Similarly, inconsistency analysis input in IMPL has a deeper structure than events in PDL.

In the context of relational databases, logic programs have been used for specifying repairs for databases that are inconsistent wrt. a set of integrity constraints [ 19, 12, 20 ]. Thus, they may be considered fixed policies without user interaction akin to an IMPL policy simply applying diagnoses in a homogenous MCS. Note however that one motivation for developing IMPL is that attempting automatic repair may not always be a viable option to deal with inconsistency in a MCS. In order to specify repair strategies for inconsistent databases in a more flexible way, active integrity constraints (AICs) [ 7–9 ] and inconsistency management policies (IMPs) [ 21 ] have been proposed. AICs extend the notion of integrity constraints by introducing update actions, for inserting and deleting tuples, to be performed if the constraint is not satisfied; whereas an IMP is a function defined wrt. a set of functional dependencies that maps a given relation R to a ‘modified’ relation R0 obeying some basic axioms.

A conceptual difference between IMPL and the above approaches to database repair and inconsistency management is that IMPL policies aim at restoring consistency by modifying bridge rules leaving the knowledge bases unchanged rather than considering a (fixed) set of constraints and repairing the database. Moreover, IMPL policies operate on heterogeneous knowledge bases and may involve user interaction. Nevertheless, database repair programs, AICs and (certain) IMPs may by mimicked for particular classes of integrity constraints by corresponding IMPL policies given suitable encodings.

Ongoing work comprises the actual implementation of IMPL. Recalling that we currently just consider bridge rule modifications for system repairs, an interesting issue for further research is to drop this convention. This would mean to also allow modifications of knowledge bases of (some) contexts for repair, and to extend IMPL accordingly.

References

1. Baader , F. , Calvanese , D. , McGuinness , D. , Nardi , D. , Patel-Schneider , P . (eds.): The Description Logic Handbook: Theory, Implementation and Applications . Cambridge ( 2003 )

2. Basol , S. , Erdem , O. , Fink , M. , Ianni , G.: HEX programs with action atoms . In: ICLP . pp. 24 - 33 ( 2010 )

3. Bo¨gl, M. , Eiter , T. , Fink , M. , Schu¨ller, P.: The MCS-IE system for explaining inconsistency in multi-context systems . In: JELIA . pp. 356 - 359 ( 2010 )

4. Bonatti , P.A. , Coi , J.L.D. , Olmedilla , D. , Sauro , L. : Rule-based policy representations and reasoning . In: Bry, F. , Maluszynski , J . (eds.) REWERSE, vol. 5500 , pp. 201 - 232 ( 2009 )

5. Brewka , G. , Eiter , T. : Equilibria in heterogeneous nonmonotonic multi-context systems . In: AAAI Conference on Artificial Intelligence (AAAI) . pp. 385 - 390 ( 2007 )

6. Brewka , G. , Roelofsen , F. , Serafini , L. : Contextual default reasoning . In: IJCAI . pp. 268 - 273 ( 2007 )

7. Caroprese , L. , Greco , S. , Zumpano , E.: Active integrity constraints for database consistency maintenance . IEEE Trans. Knowl. Data Eng 21 ( 7 ), 1042 - 1058 ( 2009 )

8. Caroprese , L. , Truszczynski , M. : Declarative semantics for active integrity constraints . In: ICLP . vol. 5366 , pp. 269 - 283 ( 2008 )

9. Caroprese , L. , Truszczynski , M. : Declarative semantics for revision programming and connections to active integrity constraints . In: JELIA . vol. 5293 , pp. 100 - 112 ( 2008 )

10. Chomicki , J. , Lobo , J. , Naqvi , S.A.: A logic programming approach to conflict resolution in policy management . In: KR . pp. 121 - 132 ( 2000 )

11. Duma , C. , Herzog , A. , Shahmehri , N.: Privacy in the semantic web: What policy languages have to offer . In: POLICY. pp. 109 - 118 ( 2007 )

12. Eiter , T. , Fink , M. , Greco , G. , Lembo , D. : Repair localization for query answering from inconsistent databases . ACM Trans. Database Syst . 33 ( 2 ) ( 2008 )

13. Eiter , T. , Fink , M. , Schu¨ller, P. , Weinzierl , A. : Finding explanations of inconsistency in nonmonotonic multi-context systems . In: KR . pp. 329 - 339 ( 2010 )

14. Eiter , T. , Fink , M. , Weinzierl , A. : Preference-based inconsistency assessment in multi-context systems . In: JELIA . pp. 143 - 155 . LNAI ( 2010 )

15. Faber , W. , Pfeifer , G. , Leone , N.: Semantics and complexity of recursive aggregates in answer set programming . Artif. Intell . 175 ( 1 ), 278 - 298 ( 2011 )

16. Fink , M. , Ghionna , L. , Weinzierl , A. : Relational information exchange and aggregation in multi-context systems . In: LPNMR ( 2011 ), to appear.

17. Gelfond , M. , Lifschitz , V. : Classical negation in logic programs and disjunctive databases. New Generation Computing 9 ( 3 /4), 365 - 386 ( 1991 )

18. Giunchiglia , F. , Serafini , L. : Multilanguage hierarchical logics, or: How we can do without modal logics . Artificial Intelligence 65 ( 1 ), 29 - 70 ( 1994 )

19. Greco , G. , Greco , S. , Zumpano , E.: A logical framework for querying and repairing inconsistent databases . IEEE Trans. Knowl. Data Eng 15 ( 6 ), 1389 - 1408 ( 2003 )

20. Marileo , M.C. , Bertossi , L.E. : The consistency extractor system: Answer set programs for consistent query answering in databases . Data Knowl. Eng 69 ( 6 ), 545 - 572 ( 2010 )

21. Martinez , M.V. , Parisi , F. , Pugliese , A. , Simari , G.I. , Subrahmanian , V.S.: Inconsistency management policies . In: KR . pp. 367 - 377 ( 2008 )

22. Subrahmanian , V. , Bonatti , P. , Dix , J. , Eiter , T. , Kraus , S. , Ozcan , F. , Ross , R. : Heterogeneous Agent Systems: Theory and Implementation . MIT Press ( 2000 )