/*-------------------------------------------------------------*/
/* DDIL - Data-Driven Inductive Inference */
/* An NCL program for inferring missing items in a set of */
/* ground two-argument atoms */
/* (C) 1993 Zdravko Markov, II-BAS */
/*-------------------------------------------------------------*/
/*
DESCRIPTION:
-----------
The system DDIL infers missing data in a set of examples and
derives ground clauses justifying these inferences. The DDIL
algorithm can be briefly described by the following problem:
Given a set of examples
T = {link(1,2),link(2,3),link(3,4),link(3,5),path(1,2),
path(1,3)}
Find the missing ones
S = {path(1,4),path(1,5),path(2,3),path(2,4),path(2,5),
path(3,4),path(3,5)}
The problem is solved in two steps:
Step 1. Building a network of literals for candidate clauses.
Let us denote the elements of T by Ti, i=1,2,...,6. Replace all
constants occurring in T by variables (different constants by
different variables), i.e. obtain
P = {link(A,B),link(B,C),link(C,D),link(C,E),path(A,B),
path(A,C)}
Step 2. Data-driven inference of ground clauses.
The basic procedure performed at this step is unifying Ti with Pj
for any i \= j. Let at some step of this process T1,T2,...,Tk
from T be successfully unified with P1,P2,...,Pk from P. Consider
now P1,P2,...,Pk as negative literals and T1,T2,...,Tk - as
positive ones (facts). Then the whole process can be seen as a
hyperresolution operation. The problem is to determine the head
of the mixed clause taking part in this operation (its body is
P1,P2,...,Pk). Since all other literals belonging to P could play
the role of a head of this clause, we have to restrict the
language in order to minimize the number of possible candidates.
Let Q be a candidate head. Three obvious restrictions on Q are
imposed:
1. All variables in Q must occur in the the clause body.
Since all currently bound variables in P occur also in
{P1,P2,...,Pk}, the candidate head Q conforming this
restriction should have all its variables bound.
2. To eliminate the trivially true clauses the body literals
are excluded too.
3. Finally, since our aim is to infer new (unknown facts), Q
should not appear in T.
This algorithm infers all element of the set S.
REFERENCE:
---------
Markov, Z. Inductive Inference in Networks of Relations, in:
Proceedings of the Third International Workshop on Inductive
Logic Programming (ILP'93), April 1-3, Bled, Slovenia, 256-277.
*/
/*-------------------------------------------------------------*/
make_net :-
bagof(example(P,X,Y),example(P,X,Y),L),
netmode(0),
top(T),
make_net(L),
gen(T),
netmode(3).
make_net([]) :-
!.
make_net([example(P,X,Y)|T]) :-
Q =.. [P,A,B],
asserta((Q:node(A,B,2,check(P,A,X,B,Y)))),
node(X,Y,_,_),
make_net(T).
check(_,X,X,Y,Y) :-
!,
fail.
check(P,A,_,B,_) :-
example(P,A,B),
!.
check(P,A,X,B,Y) :-
same_type(A,X),
Q =.. [P,A,B],
heads(H),
member(Q,H),!.
heads(Heads):[].
same_type(X,Y) :-
example(P,X,_),
example(P,Y,_).
ddil(Head,[FirstLit|Rest],K) :-
example(P,X,Y),
FirstLit =.. [P,X,Y],
call(FirstLit),
next_literals(K,Rest,Heads),
member(Head,Heads).
next_literals(1,[],Heads) :-
!,
heads(Heads),
nonvar(Heads),
terminate(Heads).
next_literals(K,[R|More],Heads) :-
node(_,_,1,check(P,A,_,B,_)),
get_example(P,A,B),
R =.. [P,A,B],
K1 is K-1,
next_literals(K1,More,Heads).
terminate([]) :-
!.
terminate([_|T]) :-
terminate(T).
get_example(P,A,B) :-
var(A),
!,
example(P,X,B),
X=A.
get_example(P,A,B) :-
example(P,A,B).
/*-------------------------------------------------------------*/
/*
EXAMPLES
--------
The file "family" contains a set of examples from the well-known
"family relationship" domain. To test the DDIL system remove any
of the examples and try the following queries. The missing
relations will be inferred in several ways as shown below:
?- [family]. Load the examples in the database
?- retract(example(father,christopher,arthur)). Remove example
?- make_net. Step 1 of the algorithm
?- ddil(Head,Body,1). Infer missing examples (1 body literal)
Head=father(christopher,arthur)
Body=[son(arthur,christopher)];
Head=father(christopher,arthur)
Body=[son(arthur,christopher)];
no
?- ddil(Head,Body,2). Infer missing examples (2 body literals)
Head=father(christopher,arthur)
Body=[husband(christopher,penelope),son(arthur,penelope)];
Head=father(christopher,arthur)
Body=[husband(christopher,penelope),son(arthur,christopher)];
...
*/