The Belief Merging Plugin MELD

The mergingplugin (MErging Library for Dlvhex) consists of a set of external atoms and additional command-line optios for dlvhex, the definition of a merging plan language, and a command-line tool called mpcompiler (merging plan compiler).

Altogether these components can be used to merge several belief bases into one. Belief bases are considered to be given in form of HEX programs. The answer sets are assumed to be the knowledge stored in the bases. The result of a merging process will again be a set of answer sets.

For a quick introduction, take a look at our examples.

If you wish to write user-defined merging operators, read the section about operator implementation.

Application: An important application of the MELD system is the merging of decision diagrams. For more information we refer to the Decision Diagram Plugin.


External Atoms

Preliminary remark: Even though the external atoms can be used directly, they are rather considered to be a basis for the mpcompiler. This means, in practical applications, the user will use these atoms only indirectly when the merging task specification is translated into a semantically equivalent HEX program.

&hex takes two strings that describe a nested HEX program as input and returns a symbolic handle to the program result.

&hex[Prog,Args](A)
Input:
Prog
A string literal containing a valid HEX program to be executed
(Quoting: character " must be encoded as \' and character \ as \\)
[Args]
[optional] The command-line options for dlvhex when Prog is evaluated
Output:
A
A symbolic integer which refers to the result of the nested HEX program

Example:

handle(A) :- &hex["a. b.", ""](A).
This will deliver handle(0), where 0 is a handle to the answer of the nested HEX program. To look into this answer, see below.

&hexfile takes two strings that describe a nested HEX program as input and returns a symbolic handle to the program result.

&hexfile[File,Args](A)
Input:
Prog
A string literal containing the path and name of a valid HEX program to be executed
[Args]
[optional] The command-line options for dlvhex when File is evaluated
Output:
A
A symbolic integer which refers to the result of the nested HEX program

Example:

handle(A) :- &hexfile["./programs/myprog.hex", ""](A).
This will deliver handle(0), where 0 is a handle to the answer of the nested HEX program. To look into this answer, see below.

&callhex{n} takes the nested HEX program as string constant, n predicate names over which the input facts to the subprogram are specified (1 ≤ n ≤ 32), and an optional string constant containing the command line arguments to the reasoner. It returns a symbolic handle to the program result.

&callhex{n}[Prog,P[1],...,P[n],Args](A)
Input:
Prog
A string literal containing a valid HEX program to be executed
(Quoting: character " must be encoded as \' and character \ as \\)
P[1], ..., P[n]
Sequence of a n predicate names which specify the input facts to the subprogram. The number must match the {n}, where 1 ≤ n ≤ 32
[Args]
[optional] The command-line options for dlvhex when Prog is evaluated
Output:
A
A symbolic integer which refers to the result of the nested HEX program

Example:

isA(sue, cat).
isA(bob, dog).
isFemale(sue).
isMale(bob).
handle(A) :- &callhex3["a. b.", isA, isFemale, isMale, ""](A).
This will deliver handle(0), where 0 is a handle to the answer of the nested HEX programrun on the facts specified over isA, isFemale and isMale

&callhexfile{n} takes the filename of the nested HEX program as string constant, n predicate names over which the input facts to the subprogram are specified (1 ≤ n ≤ 32), and an optional string constant containing the command line arguments to the reasoner. It returns a symbolic handle to the program result.

&callhexfile{n}[File,P[1],...,P[n],Args](A)
Input:
File
A string literal containing the path and name of a valid HEX program to be executed
P[1], ..., P[n]
Sequence of a n predicate names which specify the input facts to the subprogram. The number must match the {n}, where 1 ≤ n ≤ 32
[Args]
[optional] The command-line options for dlvhex when File is evaluated
Output:
A
A symbolic integer which refers to the result of the nested HEX program

Example:

isA(sue, cat).
isA(bob, dog).
isFemale(sue).
isMale(bob).
handle(A) :- &callhexfile3["./programs/myprog.hex", isA, isFemale, isMale, ""](A).
This will deliver handle(0), where 0 is a handle to the answer of the nested HEX program run on the facts specified over isA, isFemale and isMale. To look into this answer, see below.

&answersets returns a list of handles to the answer sets of a given HEX program

&answersets[A](AS)
Input:
A
A handle to the result of a nested HEX program (as returned by &hex or &hexfile
Output:
AS
A list of handles to the answer sets withing answer A
Note: AS is only unique within an answer, i.e., a complete identification is only possible with the tuple (A, AS)

Example:

handles(A, AS) :- &hex["a v b.", ""], &answersets[A](AS).
This rule will deliver an answer set containing 2 handles since /a v b. has two answer sets. For looking into answer sets, see below.

&predicates returns a list of predicate/arity tuples contained in an answer set of a nested program.

&predicates[A, AS](Pred, Arity)
Input:
A
Handle to an answer
AS
Handle to an answer set within answer A
Output:
Pred
A predicate name occuring in A, AS
Arity
The arity of predicate Pred

Example:

preds(Pred, Arity) :- &hex["a. p(x).", ""], &answersets[A](AS),
                      &predicates[A, AS](Pred, Arity).
	
This rule will deliver two atoms upon preds, namely preds(a, 0) and preds(p, 1) since the inner program uses propositional atom a and unary predicate p.

&arguments returns a list of triplets describing the atoms upon a certain predicate name within an answer set.

&arguments[A, AS, Pred](I, ArgIndex, Value)
Input:
A
Handle to an answer
AS
Handle to an answer set within answer A
Pred
Some predicate name occurring in A, AS
Output:
I
A running index without any inherent meaning. The only purpose of this index is to allow the user to figure out which triples belong together (namely all with the same index)
ArgIndex
The argument index described by this triplet; this is either a value in range 0 to n-1 (with n being the arity of Pred) or the special value s to retrieve the sign of the atom (0 for positive, 1 for strongly negated)
Value
The value of argument with index ArgIndex in the I-th occurrence of the given predicate

Example:

pInner(Value1, Value2) :- &hex["p(x, y). p(a, b).", ""], &answersets[A](AS),
                          &arguments[A, AS, p](I, 0, Value1),
                          &arguments[A, AS, p](I, 1, Value2).
	
This rule will deliver two atoms upon pInner: pInner(x, y) and pInner(a, b).

Parameter I is used in both evaluations of &arguments. This makes sure that we actually retrieve the first and second argument (indices 0 and 1) of the same occurrence of this predicate.

&operator takes one string (operator name) and two binary predicates as parameters. Its output parameter is an integer handle to the operator's result.

&operator[OPName,Args,KVPairs](A)
Input:
OPName
A string literal containing the name of the operator to apply
Args
A binary predicate. Each tuple must contain a pair I,H, where I is a parameter index and H the handle to some program or operator result, which shall be passed to the operator as its I-th argument
KVPairs
A binary predicate with key-value pairs that describe additional parameters for this operator (operator dependent)
Output:
A
A symbolic integer which refers to the result of the operator application

Example:

args(0, A) :- &hex["a. b.", ""](A).
args(1, A) :- &hex["c.", ""](A).

innerPreds(Pred, Arity) :- &operator["union", args, kvpairs](H),
                           &answersets[H](AS),
                           &predicates[H, AS](Pred, Arity).
The program will evaluate both nested programs and pass their answers to operator union. Then, the operator result is investigated using atoms &answersets and &predicates. This will deliver the final result innerPreds(a, 0), innerPreds(b, 0) and innerPreds(c, 0).


Command-Line Options

The mergingplugin recognizes the following command line arguments

--operatorpath or --op

Using the syntax
--operatorpath=path1,path2,... or --op=path1,path2,...
additional paths where operators are loaded from can be specified. A path can point to a directory or a shared object library. In case of a directory, operator libs that are directly within this directory will be loaded (non-recursive!).

--inputrewriter or --irw

The syntax
--inputrewriter=program or --irw=program
specifies an input rewriter. This can be an arbitrary tool that reads from standard input and writes to standard output. The complete dlvhex input will be directed through this program before reasoning starts.

--operatorinfo or --opinfo

The syntax
--operatorinfo=OPERATOR_NAME or --opinfo=OPERATOR_NAME
prints some online help message for a certain operator, if available. Example: --opinfo=union

Merging Plan Language

The merging scenario is defined in merging plan files of the following form:

[common signature]
predicate: pred1/arity1;
...
predicate: predN/arityN;

[belief base]
name: nameOfBeliefBase1;
mapping: "head1 :- body1."
...
mapping: "headM :- bodyM."

...

[belief base]
name: nameOfBeliefBaseK;
mapping: "head1 :- body1."
...
mapping: "headJ :- bodyJ."

[merging plan]
{
	operator: someOperatorsName;
	key1: value1;
	...
	keyN: valueN;
	source: {
		operator: subPlanOperator;
		...
		source: {nameOfBeliefBase1};
		source: {nameOfBeliefBase2};
	};
	source: {
		...
	};
}
			
Essentially the file consists of 3 sections which are described in the following subsections.

Common Signature

In statements of form
predicate: pred1/arity1;
all relevant predicates that occur in the belief bases are defined. Those predicates will be output by dlvhex after the merging plan was processed.

Belief Bases

Belief bases can be any data source: relational databases, XML files, etc.. The only requirement is that they are accessible from dlvhex through an appropriate external atom. Belief bases are defined by blocks of form:

[belief base]
name: nameOfBeliefBase1;
mapping: "head1 :- body1.";
...
mapping: "headM :- bodyM.";
				
where the name defines a legal name for this belief base, followed by an arbitrary number of mappings. Mappings can essentially be arbitrary dlvhex code fragments. However, in reasonable applications they access the underlying (prorietary) belief base and map their content onto the common signature (see above). Alternatively they can also be defined by

[belief base]
name: nameOfBeliefBase1;
source: "externalfile.hex";
				
where "externalfile.hex" is an external file containing (computation source access rules and) mapping rules. Note that mapping and source cannot be used simultaneously.

Merging Plan

The merging plan is a hierarchical structure that combines the belief bases such that only one final result survives at the end of the day. A merging plan section is of form:

operator: XYZ.
key1: value1;
...
keyN: valueN;
source: ...;
source: ...;
				
Such a section defines the operator to apply, the key-value pairs that shall be passed to the operator and the sub merging plans (source). A sub merging plan (after a source statement) can either be a belief base (denoted as {bbName};) or a composed merging plan (i.e. the result of a prior operator application).

Syntax

The following table summarizes the complete syntax of merging task files.
Lexer
Literal=> -?Σp(((Σc|Σv)(,Σc|Σv)*))?
PredicateName=> [a-z] ( [a-z]|[A-Z]|[0-9])*
KBName=> ([a-z]|[A-Z]) ( [a-z]|[A-Z]|[0-9])*
OPName=> ([a-z]|[A-Z]) ( [a-z]|[A-Z]|[0-9])*
Variable=> [A-Z] ( [a-z]|[A-Z]|[0-9])*
Number=> ([1-9] [0-9]*) 0
General ASP Grammer
Fact=> RuleHead .
Constraint=> : - RuleBody .
Query=> not? Literal (, not? Literal)*
RuleHead=> Literal (v Literal)*
RuleBody=> Query
Merging Plan Specific Grammer
Program=> CommonSigDef Mappings MergingPlan
CommonSigDef=> [common signature] PredicateDefinition*
Mappings=> KnowledgeBase*
MergingPlan=> [merging plan] MergingPlanNode
MergingPlanNode=> { operator : OPName ; (key : value)* (source : MergingPlanNode ;)* } | KBName
PredicateDefinition=> predicate : PredicateName / Number ;
PredicateName=> [knowledge base] name : KBName ; (MappingRule*)|ExternalSource
MappingRule=> mapping> : " Rule " ;
ExternalSource=> source : Filename ;
stringliteral=> "{"}c " (where Sc is the complement of set S)
Filename=> stringliteral
key=> Σc|stringliteral
value=> Σc|stringliteral

Merging Plan Compiler

The merging plan compiler is a command-line tool which installed as part of the mergingplugin. It can be called in command-line by entering:
mpcompiler
with appropriate parameters. This tool translates a belief merging scenario into a dlvhex program. The merging scenario is defined in one or more input files or is read from standard input.

Options

The command-line options are: If no filenames are passed, the compiler will read from standard input. If at least filename is passed, standard input will not be processed by default. However, if -- passed as additional parameter, standard input will be read additionally to the input files.


Examples

The plugin comes with 4 built-in merging operators which are explained in the following subsections.

All examples can be tried out by copying them into a textfile plan.mp and executing
mpcompiler plan.mp | dlvhex --
Note that the output will contain some intermediate atoms due to technical reasons. To generate a more readable result, add parameter --filter= with the attributes mentioned in the common signature, e.g., in the first example: --filter=a,b,c

In the following examples, the source programs are directly embedded in the merging plan using mapping statements. This was only done to provide compact code snippets in single files. In realistic applications, one would rather use mapping rules that access some external source of computation by the use of appropriate external atoms.

Union

The union operator computes the pairwise union of answer sets of it's input belief bases. The following program delivers {a,b,c}

Example program:

[common signature]
predicate: a/0;
predicate: b/0;
predicate: c/0;

[belief base]
name: kb1;
mapping: "
	a.
";

[belief base]
name: kb2;
mapping: "
	b.
	c :- b.
";

[merging plan]
{
	operator: union;
	{
		kb1
	};
	{
		kb2
	};
}

Setminus

The setminus operator expects two parameters and computes the set difference between it's first input belief base and all answer sets of it's second one. The following program delivers {a,c}

Example program:

[common signature]
predicate: a/0;
predicate: b/0;
predicate: c/0;

[belief base]
name: kb1;
mapping: "
	a.
	b.
	c.
";

[belief base]
name: kb2;
mapping: "
	b.
";

[merging plan]
{
	operator: setminus;
	{
		kb1
	};
	{
		kb2
	};
}

Dalal's Operator

Dalal's operator computes an answer set, which is as similar to it's input answer sets as possible, without introducing logical contradictions. The following program delivers {} and {p(x)} Both answer sets have minimum distance to the sources. {} differs in 2 literals from bb1 and in 0 from bb2 and bb3, thus 2 in total. p(x) differs in 1 literal from bb1, in 1 from bb2 and in 0 from bb3, thus also 0 in total. For details about the distance computation we refer to the plugin's built-in documentation system.

Example program:

[common signature]
predicate: a/0;
predicate: p/1;

[belief base]
name: bb1;
mapping: "a. p(x).";

[belief base]
name: bb2;
mapping: "-a. -p(x).";

[belief base]
name: bb3;
mapping: "-a.";

[merging plan]
{
	operator: dalal;
	aggregate: "sum";
	{bb1};
	{bb2};
	{bb3};
}

Majority Selection

The majority selection operator expects the user to specify some propositional atom. Then it will check if the majority of the answer sets in it's first and only argument accept or deny this atom. Finally, all answer sets which do not follow the majority will be killed. The example delivers two answer sets: {a, d} and {a, b, d}, because the majority of the answer sets accept d. The third answer set, {b, -d}, does not follow the majority and is therefore killed.

Example program:

[common signature]
predicate: a/0;
predicate: b/0;
predicate: d/0;

[belief base]
name: bb;
mapping: "
	a1 v a2 v a3.
	a :- a1.
	d :- a1.

	b :- a2.
	-d :- a2.

	a :- a3.
	b :- a3.
	d :- a3.
";

[merging plan]
{
	operator: majorityselection;
	majorityOf: "d";
	{bb};
}

Operator Implementation

This section describes the principles for implementing user-defined merging operators. For a more detailed explanation we refer to the developer manual.

Operator Libraries

Operators are organized as operator libararies, where each library can contain arbitrary many operators. An operator library must be compiled as shared object library that is installed either in the system or the user plugin directory of dlvhex. Note: Additional plugin directories that are passed to dlvhex using the command line argument --plugindir (or -p) will not be searched for operator libraries. However, the mergingplugin provides an own command line parameter for specifying additional operator locations. Entry point of an operator library is a method with the following signature:
std::vector<IOperator*> OPERATORIMPORTFUNCTION()
This method must return a vector with pointers to instances of all the operator implementations in this library (see below). the mergingplugin will call this method on startup and load all operators that are returned by this function.

Operator Classes

Operators are C++ classes (within operator libraries) that implement the interface IOperator, which is installed in the following subdirectory of the include directory:
dlvhex/mergingplugin/IOperator.h
The interface defines two abstract methods, namely:

 

General
dlvhex source code @ github.com
Description-Of-A-Project

Popular Plugins
Action Plugin
DecisionDiagrams Plugin
Description Logics Plugin
Description Logics Lite Plugin
MELD: Belief Merging Plugin
Nested HEX Plugin
MCSIE Plugin
String Plugin
dlvhex-semweb Project

Documentation
User Guide
README
doxygen
Writing Plugins in C++
Writing Plugins in Python