Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!uwm.edu!uwvax!ricotta.cs.wisc.edu!raghu
From: raghu@ricotta.cs.wisc.edu (Raghu Ramakrishnan)
Newsgroups: comp.lang.prolog
Subject: Re: mutual recursion query
Summary: Mutual recursion is not the issue.
Message-ID: <10486@spool.cs.wisc.edu>
Date: 25 May 90 19:29:01 GMT
References: <4176@munnari.oz.au> <10462@spool.cs.wisc.edu> <718@fornax.UUCP>
Sender: news@spool.cs.wisc.edu
Organization: U of Wisconsin CS Dept
Lines: 103

(This is a somewhat technical message.  The next para should
let you skip the rest with little loss unless you have an
enquiring mind that wants to know.)

I think that mutual recursion is a red herring.  The opportunity for
the kind of optimization that Jiawei Han describes arises for
different reasons.  However, the example serves to illustrate 
some of the power of optimization techniques developed in the
deductive database literature; you may want to simply compare
the initial and optimized versions of the program below.

Raghu

---------------------------

In article <718@fornax.UUCP> han@fornax.UUCP (Jiawei Han) writes:
>
>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 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).
>
>	        ......
>	        
>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 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.
>- jiawei

Let us consider a query that binds the first argument, for concreteness.
The original program can be automatically compiled into the following
by directly applying magic sets and then ``factoring'' the resulting
program:

Program 1:

	m_fem_anc(jane).     /* jane is the query constant */
	m_fem_anc(Z) :- m_fem_anc(X), mother(X,Z).
	m_fem_anc(Z) :- m_mal_anc(X), father(X,Z).
	m_mal_anc(Z) :- m_fem_anc(X), mother(X,Z).
	m_mal_anc(Z) :- m_mal_anc(X), father(X,Z).

	fem_anc_2(X) :- m_fem_anc(X), female(X).
	fem_anc_2(Y) :- mal_anc_2(Y).
	mal_anc_2(X) :- m_mal_anc(X), male(X).

The property of the program that makes this (O(n^2) to O(n), where n
is the number of given facts) transformation possible is the
left-linearity of the recursive rules; the mutual recursion does
not play a role.  

Han's transformed program is also factorable.  By applying magic
sets and factoring, we get:

Program 2:

	m_fem_anc(jane).     /* jane is the query constant */
	m_anc(Z) :- m_fem_anc(X), mother(X,Z).
	m_anc(Z) :- m_anc(X), father(X,Z).
	m_anc(Z) :- m_anc(X), mother(X,Z).

	fem_anc_2(X) :- m_fem_anc(X), female(X).
	fem_anc_2(Y) :- anc_2(Y).
	anc_2(X) :- m_anc(X), male(X).
	anc_2(X) :- m_anc(X), female(X).

Programs 1 and 2 are both O(n), where n is the number of given facts;
the original program and its magic sets version are both O(n^2).
The difference between programs 1 and 2 is all that can be attributed
to eliminating mutual recursion.  (There is a difference, of course,
and in this particular example, m_fem_anc and m_mal_anc seem likely
to have a lot of overlap.  Eliminating the mutual recursion between
them aims to reduce the impact of this overlap.)

(See "Arity Reduction by Factoring", by Naughton, Ramakrishnan, 
Sagiv and Ullman in VLDB 89 for more on factoring.)