Path: utzoo!attcan!uunet!van-bc!ubc-cs!fornax!han
From: han@fornax.UUCP (Jiawei Han)
Newsgroups: comp.lang.prolog
Subject: Re: mutual recursion query
Summary: Two transformation methods
Message-ID: <718@fornax.UUCP>
Date: 24 May 90 14:17:43 GMT
References: <4176@munnari.oz.au> <10462@spool.cs.wisc.edu>
Organization: School of Computing Science, SFU, Burnaby, B.C. Canada
Lines: 92

It poses a quite interesting question.  Let me try it also.
The problem is whether it is worthwhile to compile a linear mutual 
recursion and in what way we should compile it.

We examine the same example.  The original linear mutual recursion is

	female_ancestor(X, X) :- female(X).
	female_ancestor(X, Y) :- mother(X, Z), female_ancestor(Z, Y).
	female_ancestor(X, Y) :- mother(X, Z),   male_ancestor(Z, Y).

	  male_ancestor(X, X) :-   male(X).
	  male_ancestor(X, Y) :- father(X, Z), female_ancestor(Z, Y).
	  male_ancestor(X, Y) :- father(X, Z),   male_ancestor(Z, Y).

Method 0:  Do not transform the recursion.  Use magic sets method to 
evaluate the recursion directly.  The magic sets method works on it
with no problem.

Method 1:  Transform a set of mutually recursive predicates into the
same predicate by introducing an extra argument and assign a distinct 
constant to it for each mutually recursive predicate in the recursion.

	        anc(c1, X, X) :- female(X).
	        anc(c1, X, Y) :- mother(X, Z),         anc(c1, Z, Y).
	        anc(c1, X, Y) :- mother(X, Z),         anc(c2, Z, Y).

	        anc(c2, X, X) :-   male(X).
	        anc(c2, X, Y) :- father(X, Z),         anc(c1, Z, Y).
	        anc(c2, X, Y) :- father(X, Z),         anc(c2, Z, Y).

The translated program is a multiple linear recursion (having multiple 
linear recursive rules).  However, the translated rule is not a chain 
rule any more.  We probably still want to evaluate it using the magic
sets method.  It works essentially in the same way with same level of
efficiency as Method 0.

Method 2:  Compile it based on the class of the linear mutual recursion.
We can simple present it in a short form as below (where we drop variables 
in the predicates since the recursive rules are chain-rules).

	        a1 :- female.
	        a1 :- m, a1.
	        a1 :- m, a2.

	        a2 :- male.
	        a2 :- f, a1.
	        a2 :- f, a2.

The rule set for a1 is essentially (where f+ is the transitive closure of f),

	        a1 :- female.
	        a1 :- m, a1.
	        a1 :- m, f+ , a1.
	        a1 :- m, f* , male.

Thus we have,
	        a1 = (m U mf+)* (female U  mf* male)
		   = (mf*)* (female U  mf* male)
		   = (mf*)* female U  (mf*)+ male
		   = m(m U f)* female U  female U m(m U f)* male
		   = m(m U f)* (female U male) U female

Let "parent = father U mother" and "person = female U male"
	        a1 = mother parent* (person) U female.
Similarly, we have
	        a2 = father parent* (person) U male.

That is, the rule is transformed to into a linear recursion as follows:

	female_ancestor(X, X) :- female(X).
	female_ancestor(X, Y) :- mother(X, Z), anc(Z, Y).

	male_ancestor(X, X) :-   male(X).
	male_ancestor(X, Y) :- father(X, Z), anc(Z, Y).

	anc(X, X) :- female(X); male(X).
	anc(X, Y) :- (father(X, Z); mother(X, Z)), anc(Z, Y).

It means that a person is a female_ancestor if she is a female or
someone's or his/her ancestor's mother.

It seems to me that method 2 gains both semantic cleaness and processing
efficiency.  It can be evaluated using the magic sets method or a typical 
transitive closure algorithm.  However, the latter is more efficient that
the former in deductive databases, which has been shown in Naughton's
SIGMOD'88 paper on separable recursions.

Please point it out if my understanding or any reasoning is wrong.

Cheers

- jiawei