MCS-IE: Multi-Context Systems Inconsistency Explainer

Documentation

Topics

MCS-IE input language
command line options
output format
builtin external atom for contexts based on DLV
how to create custom external atoms for other context semantics

Overview

The Multi-context system (MCS) formalism allows to represent interlinking of knowledge bases (Brewka and Eiter 2007). An MCS consists of contexts, each with a knowledge base, a logic, and bridge rules which import knowledge from other contexts. The logic used for reasoning in each context can be individually chosen for each context, this allows to represent heterogeneous systems.

Semantics in MCSs is defined in terms of stable system states which are called equilibria. If some MCS has no equilibrium, it is called inconsistent.

The purpose of MCS-IE is to explain reasons for inconsistency in MCSs, using the notions of Diagnosis and Inconsistency Explanation that were introduced in (Eiter et al. 2010).

The MCS-IE plugin encapsulate the reasoning within contexts by using external atoms. As input, the plugin gets a master file which specifies the MCS architecture. Depending on commandline options, the output of the plugin contains

equilibria of the MCS (if existing)
diagnoses of the MCS (subset-minimal or all)
inconsistency explanations of the MCS (subset-minimal or all)

Input Language

The main input file for dlvhex contains the MCS topology:

Contexts are specified as follows:

#context(<i>,"<xatom>","<param>").

<i>

Index of the context (contexts must be numbered 1,2,3,...).

<xatom>

External atom used for evaluation of the semantics of that context.

<param>

Parameter to the external atom.

Bridge rules are specified as follows:

<name>: (<tgtctx>:<input>) :- (<ctx1>:<bel1>), ...
                              not (<ctx2>:<bel2>), ... .

<name>

Name of the rule (C-Identifier). This is only used for output.

Index of the context importing the information.

<input>

Information imported at context <tgtctx> if the rule is applicable (must be a C-Identifier).

<ctx1>

Index of context where belief <bel1> must be present for applicability of the rule.

<bel1>

Belief at context <ctx1>.

<ctx2>

Index of context where belief <bel2> must not be present for applicability of the rule.

<bel2>

Belief at context <ctx2>.

Bridge rule facts are specified as follows:

<name>: (<tgtctx>:<input>).

(see above)

Example input for the MCS used in (Eiter et al. 2010):

#context(1,"dlv_asp_context_acc", "kb1.dlv").
#context(2,"dlv_asp_context_acc", "kb2.dlv").
#context(3,"dlv_asp_context_acc", "kb3.dlv").
#context(4,"dlv_asp_context_acc", "kb4.dlv").

r1: (3:pneumonia) :- (2:xray_pneumonia).
r2: (3:marker) :- (2:blood_marker).
r3: (4:need_ab) :- (3:pneumonia).
r4: (4:need_strong) :- (3:atyppneumonia).
r5: (4:allow_strong_ab) :- not (1:allergy_strong_ab).

[ master.hex kb1.dlv kb2.dlv kb3.dlv kb4.dlv ]

Command Line Options and Invocation

The command line options are:

--ieenable
Enable the rewriting of MCS-IE.
This switch is useful if MCS-IE is installed with other dlvhex plugins, and only certain plugins shall be used at the same time.

--ieexplain={D,Dm,E,Em}
Calculates a certain type of explanation for inconsistency.
Without this option, the plugin calculates equilibria (which might not exist).
Any combination of the four possible values can be used, separated by commas.
The values D, Dm, E, and Em stand for diagnosis, subset-minimal diagnosis, inconsistency explanation, and subset-minimal inconsistency explanation, respectively.

--ienoprintopeq
Do not print output-projected equilibria for diagnosis output. (This ensures that no diagnosis is printed twice, even if it has two equilibria.)

--iebenchmark
Print time/call summary.

--ieuseKR2010rewriting
Use (nearly always) slower rewriting technique (as published in KR2010). Information about both rewriting techniques can be found here: MCS-IE: Comparison of HEX Rewritings (PDF manuscript).

The MCS-IE system is realized as a plugin to dlvhex, therefore executing MCS-IE is done like executing dlvhex, but with additional command-line arguments.

If you want have checked out, built and "make check"-ed MCS-IE as shown above, you can execute our medical example manually as follows:

$ cd examples/
$ dlvhex --plugindir=../src/ --ieenable medExample/master.hex

This will not return anything, as there are no equilibria and no explanation mode was specified.

The following invocation will output the sets of minimal explanations and minimal diagnoses.

$ dlvhex --plugindir=../src/ medExample/master.hex --ieenable --ieexplain=Dm,Em
Em:({r1,r2,r4},{r5})
Dm:EQ:({r1},{}):({allergy_strong_ab},{blood_marker,xray_pneumonia},{})
Dm:EQ:({r2},{}):({allergy_strong_ab},{blood_marker,xray_pneumonia},{pneumonia},{})
Dm:EQ:({r4},{}):({allergy_strong_ab},{blood_marker,xray_pneumonia},{atyppneumonia,pneumonia},{})
Dm:EQ:({},{r5}):({allergy_strong_ab},{blood_marker,xray_pneumonia},{atyppneumonia,pneumonia},{})

If make check has been executed, the examples' dlvhex plugins have been built, including Context3.cpp as shown above.

To test this external plugin, the invocation must specify an additional path where to find plugin libraries. The following invocation should yield the same set of diagnoses and inconsistency explanations as above.

$ dlvhex --plugindir=../src/:./ medExample/master_cppcontext3.hex --ieenable --ieexplain=Dm,Em
Em:({r1,r2,r4},{r5})
Dm:EQ:({r1},{}):({allergy_strong_ab},{blood_marker,xray_pneumonia},{})
Dm:EQ:({r2},{}):({allergy_strong_ab},{blood_marker,xray_pneumonia},{pneumonia},{})
Dm:EQ:({r4},{}):({allergy_strong_ab},{blood_marker,xray_pneumonia},{atyppneumonia,pneumonia},{})
Dm:EQ:({},{r5}):({allergy_strong_ab},{blood_marker,xray_pneumonia},{atyppneumonia,pneumonia},{})

Output Format

Depending on the specified command line options, the output contains lines of the following format:

An equilibrium:
```
  EQ:(<S1>,<S2>,...)
```
Where <Si> is the set of beliefs at the context with index i.
Example:
```
  EQ:({tweedy_is_penguin},{},{do_nothing})
```
A diagnosis with one of its witnessing equilibria:
```
  D:EQ:(<D1>,<D2>):(<S1>,<S2>,...)
```
Where <D1>, and <D2> are the sets of bridge rules which must be removed, and added unconditionally, to get an equilibrium.
Example:
```
  D:EQ:({r1},{r3,r5}):({allergy_strong_ab},{blood_marker,xray_pneumonia},{},{})
```
A diagnosis without a witnessing equilibrium:
```
  D:(<D1>,<D2>)
```
A subset-minimal diagnosis plus one of its witnessing equilibria:
```
  Dm:EQ:(<D1>,<D2>):(<S1>,<S2>,...)
```
A subset-minimal diagnosis without a witnessing equilibrium:
```
  Dm:(<D1>,<D2>)
```
Example:
```
  Dm:({r1},{})
```
An inconsistency explanation:
```
  E:(<E1>,<E2>)
```
Where <E1>, and <E2> are the sets of bridge rules which must be present, and must not be added unconditionally, to get inconsistency.
Example:
```
  E:({r1,r2,r4},{r1,r2,r3,r4,r5})
```
A subset-minimal inconsistency explanation:
```
  Em:(<E1>,<E2>)
```
Example:
```
  Em:({r1,r2,r4},{r5})
```

The output contains no lines at all, if no explanation was requested and no equilibria exist.

External Atoms for Context Semantics

All external atoms which can be used for context semantics have the following signature:

&<atom>[Idx,Beliefs,Heads,Outputs,Param]()

<atom>

Name of the external atom, which is used for <xatom> in the #context input directive.

Idx

Index of the context which is evaluated.

Beliefs

Predicate which specifies output beliefs that are present at that context.

Heads

Predicate which specifies bridge rule heads that are active at that context.

Outputs

Predicate which specifies relevant output beliefs of that context.

Param

A string parameter which is passed to the external atom for arbitrary use. Most of the time this parameter will indicate the location of the knowledge base, while the external atom implements the logic of the context.

The atom returns true if, using the logic implemented in the atom, the knowledge base (indicated possibly by Param) plus the formulas Heads accepts a belief set such that the intersection of that belief set with beliefs specified by Outputs is equal to the beliefs specified by Beliefs.

External Atoms: DLV Contexts

The MCS-IE plugin provides one external atom which allows to use DLV programs as contexts. This external atom is used by the example input files above.

&dlv_asp_context_acc[Idx,Beliefs,Heads,Outputs,DLVFile]()

DLVFile

Path to file containing a DLV program.

The input from bridge rules - Heads - will be appended to the program as facts. For each acceptance check, dlv will be called.

External Atoms: User-defined Context Plugins

For contexts other than ASP programs, new external atoms can be created using a library provided by MCS-IE.

The way to write such an external atom is shown by the following example C++ source:

#include "ContextInterfaceAtom.h"
#include "ContextInterfacePlugin.h"

DLVHEX_MCSEQUILIBRIUM_PLUGIN(MedExamplePluginContext3,0,1,0)

namespace
{

DLVHEX_MCSEQUILIBRIUM_CONTEXT(Context3,"ontology_context3_acc")

std::set<std::set<std::string> >
Context3::acc(
  const std::string& param,
  const std::set<std::string>& input)
{
std::set<std::set<std::string> > ret;
// accept all input
std::set<std::string> s(input.begin(),input.end());
//s.insert(input.begin(), input.end());
if( input.count("pneumonia") == 1 && input.count("marker") == 1 )
{
  // additionally accept atyppneumonia
  s.insert("atyppneumonia");
}
ret.insert(s);
return ret;
}

void MedExamplePluginContext3::registerAtoms()
{
registerAtom<Context3>();
}

} // anonymous namespace

[Context3.cpp]

This file can be compiled and linked just like a dlvhex plugin, the result is a dlvhex plugin which provides an external atom named ontology_context3_acc that can be used as a context.

In our example above, we can replace kb3.dlv by the C++ context implementation above. We do this by changing the third line of the master input file. The new master file looks as follows:

#context(1,"dlv_asp_context_acc", "kb1.dlv").
#context(2,"dlv_asp_context_acc", "kb2.dlv").
#context(3,"ontology_context3_acc", "").
#context(4,"dlv_asp_context_acc", "kb4.dlv").

r1: (3:pneumonia) :- (2:xray_pneumonia).
r2: (3:marker) :- (2:blood_marker).
r3: (4:need_ab) :- (3:pneumonia).
r4: (4:need_strong) :- (3:atyppneumonia).
r5: (4:allow_strong_ab) :- not (1:allergy_strong_ab).

[ master_cppcontext.hex ]

For more examples and testcases, please see the examples/ directory in SVN, or view the directory online: dlvhex SVN Browser: dlvhex-mcs/mcs-ie/trunk/examples/ or dlvhex Trac: dlvhex-mcs/mcs-ie/trunk/examples/. (The current example is stored in medExample/.)

Internals

A documentation of the two rewriting techniques which are implemented in MCS-IE is available here: MCS-IE: Comparison of HEX Rewritings (PDF manuscript).

These rewritings transform the input into a HEX program which is then evaluated. Each answer set corresponds to a diagnosis and a witnessing equilibrium.

Links

MCS-IE Online Demo

dlvhex
HEX-Programs

Knowledge Based Systems Group

Research Project:
Inconsistency Management for
Knowledge Integration Systems