han@fornax.UUCP (Jiawei Han) (05/24/90)
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
raghu@ricotta.cs.wisc.edu (Raghu Ramakrishnan) (05/26/90)
(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.)
ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) (06/06/90)
In article <718@fornax.UUCP>, han@fornax.UUCP (Jiawei Han) wrote
in response to my question about transforming mutual recursion.
The bottom line was that transforming mutual recursion into linear
recursion permits the use of a transitive closure algorithm.
The question is, when is this a good idea?
Consider a grammar written in Datalog. For example,
s --> np(P,N,nom), vp(P,N).
np(P,N,C) --> word(X), {pronoun(X,P,N,C)}.
np(3,N,_) --> word(the), word(X), {noun(X,N)}, opt_rel.
opt_rel --> word(that), vp(_,_).
opt_rel --> [].
vp(P,N) --> word(X), {intrans(X,P,N)}.
vp(P,N) --> word(X), {trans(X,P,N)}, np(_,_,acc).
Here the EDB would be the lexicon
pronoun(i, 1,s,nom).
pronoun(me, 1,s,acc).
...
and the input sentence
word(the,0,1). word(cat,1,2). word(that,2,3). ...
The top level query might be
?- s(0, X).
(Note that because I used word(X) instead of [X] there are no actual
lists involved.)
Here we have a mutual recursion between np//3, opt_rel//0, and vp//2.
I have no difficulty at all in believing that some bottom-up query
evaluators might be able to handle this parsing problem efficiently.
(If someone who is really at home with magic sets would care to explain
what the magic sets method would do with this example I would be grateful.)
But I don't see how turning the example into simple linear recursion would
help. _Would_ it?
The practical question is whether "real" mutual recursions are more like
my thinly-disguised ancestor example or more like this one. "Parts
explosion" is more like ancestor, but is that the most useful case?
--
"A 7th class of programs, correct in every way, is believed to exist by a
few computer scientists. However, no example could be found to include here."warren@sbwarren.cs.sunysb.edu (David Scott Warren) (06/07/90)
In <3164@goanna.cs.rmit.oz.au>, ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) presents a Datalog example of a context-free grammar which includes mutual recursions and asks: >(If someone who is really at home with magic sets would care to explain >what the magic sets method would do with this example I would be grateful.) Not being an expert in magic sets, and at the risk of oversimplifying, I will try to give my intuitions about magic sets and grammars. The result of executing the ``Magic set''-transformed program bottom-up (semi-naive) is essentially the same as Extension Table (or OLDT) evaluation. (So one might think of Magic-sets as a ``compilation'' technique for extension tables.) And Extension Table evaluation is essentially the same as Earley Deduction. And Earley Deduction on Datalog grammars as Richard presented is Earley's context-free recognition algorithm. So by transitivity of ``essentially the same as'', magic sets on Datalog grammars is Earley recognition. Evidence for the validity of this claim is Raghu Ramakrishnan's comment that under magic sets, left-recursion is linear and right-recursion is quadratic, exactly as it is in Earley recognition. David S. Warren warren@sbcs.sunysb.edu
han@fornax.UUCP (Jiawei Han) (06/07/90)
In article <3164@goanna.cs.rmit.oz.au>, ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes: > In article <718@fornax.UUCP>, han@fornax.UUCP (Jiawei Han) wrote > in response to my question about transforming mutual recursion. > The bottom line was that transforming mutual recursion into linear > recursion permits the use of a transitive closure algorithm. > > The question is, when is this a good idea? > > Consider a grammar written in Datalog. For example, > s --> np(P,N,nom), vp(P,N). > np(P,N,C) --> word(X), {pronoun(X,P,N,C)}. > np(3,N,_) --> word(the), word(X), {noun(X,N)}, opt_rel. > opt_rel --> word(that), vp(_,_). > opt_rel --> []. > vp(P,N) --> word(X), {intrans(X,P,N)}. > vp(P,N) --> word(X), {trans(X,P,N)}, np(_,_,acc). > > Here the EDB would be the lexicon > pronoun(i, 1,s,nom). > pronoun(me, 1,s,acc). > ... > and the input sentence > word(the,0,1). word(cat,1,2). word(that,2,3). ... > > The top level query might be > ?- s(0, X). > ...... This is another interesting exmaple to show the compilation method works well. Let me try it. I write the grammar as follows. s :- np(P,N,nom), vp(P,N). np(P,N,C) :- pronoun(X,P,N,C). np(P,N,_) :- word(the), noun(X,N), opt_rel. opt_rel :- word(that), vp(_,_). opt_rel :- []. vp(P,N) :- intrans(X,P,N). vp(P,N) :- trans(X,P,N), np(_,_,acc). The transformation can be performed as follows: In this rule set, the mutually recursive predicates are np//3 and vp//2. We first remove the intermediate predicate: opt_rel//0. s :- np(P,N,nom), vp(P,N). np(P,N,C) :- pronoun(X,P,N,C). np(P,N,_) :- word(the), noun(X,N). np(P,N,_) :- word(the), noun(X,N), word(that), vp(_,_). vp(P,N) :- intrans(X,P,N). vp(P,N) :- trans(X,P,N), np(_,_,acc). Clearly, np is defined by the following rule set (with no mutual recursion): np(P,N,C) :- pronoun(X,P,N,C). np(P,N,_) :- word(the), noun(X,N). np(P,N,_) :- word(the), noun(X,N), word(that), intrans(Y,P,M). np(P,N,_) :- word(the), noun(X,N), word(that), trans(Y,P,M), np(_,_,acc). Then there is no difficulty to compile the rule set into a transitive closure: exit-portion(C) = pronoun(X,P,N,C) U (word(the), noun(X,N)) U (word(the), noun(X,N), word(that), intrans(Y,P,M) np(P,N,norm) = exit-portion(norm) U ((word(the), noun(X,N'), word(that), trans(Y,P',M))+ , exit-portion(acc)). Similarly, we can derive the formula for vp. Therefore, s can be generated accordingly, which can be processed by transitive closure algorithms. Actually, not all the linear mutual recursions are transformable into transitive closure operations although I believe more than 90% application examples are. Even if they are not, they should be able to be transformed into relatively simple linear recursive programs containing no mutually recursive predicates (as I discussed in my technical report). I wish that I can get a counter-example (real example, not those can never find semanitc explanations) to show that my method may have some difficulties. -jiawei
debray@cs.arizona.edu (Saumya K. Debray) (06/07/90)
Richard A. O'Keefe (ok@goanna.cs.rmit.oz.au) writes: > In article <718@fornax.UUCP>, han@fornax.UUCP (Jiawei Han) wrote > in response to my question about transforming mutual recursion. > The bottom line was that transforming mutual recursion into linear > recursion permits the use of a transitive closure algorithm. > > The question is, when is this a good idea? This is probably tangential to Richard's point, but there are transitive closure algorithms that require O(log N) iterations to compute the fixpoint, where the (semi)naive algorithm for fixpoint computation would require O(N) iterations. (There is, however, some growth in code size.:-) -- Saumya Debray CS Department, University of Arizona, Tucson internet: debray@cs.arizona.edu uucp: uunet!arizona!debray
ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) (06/08/90)
In article <3164@goanna.cs.rmit.oz.au>, I wrote > Consider a grammar written in Datalog. For example, > s --> np(P,N,nom), vp(P,N). > np(P,N,C) --> word(X), {pronoun(X,P,N,C)}. ... In article <792@fornax.UUCP>, han@fornax.UUCP (Jiawei Han) missed the point completely. > Let me try it. I write the grammar as follows. > s :- np(P,N,nom), vp(P,N). > np(P,N,C) :- pronoun(X,P,N,C). ... I used definite clause grammar notation (and referred to non-terminals with N arguments as P//N rather than to predicates with N+2 arguments as P/(N+2)) because I was writing a grammar. The first two clauses transliterate to s(S0,S) :- np(P, N, nom, S0, S1), vp(P, N, S1, S). If the method works well with what I actually wrote, it's interesting. If it works with some random thing with no sequence arguments, it isn't. Let me repeat the grammar, this time with the sequence arguments explicit, and one more rule which I accidentally forgot. s(S0,S) :- np(P,N,nom,S0,S1), vp(P,N,S1,S). np(P,N,C,S0,S) :- word(X,S0,S), pronoun(X,P,N,C). np(3,N,_,S0,S) :- word(the,S0,S1), word(X,S1,S2), noun(X,N), opt_rel(S2,S). opt_rel(S0,S) :- word(that,S0,S1), vp(_,_,S1,S). opt_rel(S0,S) :- word(that,S0,S1), np(P,N,nom,S1,S2), tv(P,N,S2,S). opt_rel(S,S). vp(P,N,S0,S) :- word(X,S0,S), intrans(X,P,N). vp(P,N,S0,S) :- tv(P,N,S0,S1), np(_,_,acc,S1,S). tv(P,N,S0,S) :- word(X,S0,S), trans(X,P,N). The rule which had been omitted lets us say "the rat that the cat chased" as well as "the cat that chased the rat", and it really made me look stupid leaving it out because the _point_ of my example was to show something that was naturally recurring in a "tree-structured" fashion. -- "A 7th class of programs, correct in every way, is believed to exist by a few computer scientists. However, no example could be found to include here."
han@fornax.UUCP (Jiawei Han) (06/09/90)
In article <3191@goanna.cs.rmit.oz.au>, ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes: ...... > Let me repeat the grammar, this time with the sequence arguments > explicit, and one more rule which I accidentally forgot. > > s(S0,S) :- np(P,N,nom,S0,S1), vp(P,N,S1,S). > > np(P,N,C,S0,S) :- word(X,S0,S), pronoun(X,P,N,C). > np(3,N,_,S0,S) :- word(the,S0,S1), word(X,S1,S2), > noun(X,N), opt_rel(S2,S). > > opt_rel(S0,S) :- word(that,S0,S1), vp(_,_,S1,S). > opt_rel(S0,S) :- word(that,S0,S1), np(P,N,nom,S1,S2), tv(P,N,S2,S). > opt_rel(S,S). > > vp(P,N,S0,S) :- word(X,S0,S), intrans(X,P,N). > vp(P,N,S0,S) :- tv(P,N,S0,S1), np(_,_,acc,S1,S). > > tv(P,N,S0,S) :- word(X,S0,S), trans(X,P,N). > > The rule which had been omitted lets us say "the rat that the cat chased" > as well as "the cat that chased the rat", and it really made me look > stupid leaving it out because the _point_ of my example was to show > something that was naturally recurring in a "tree-structured" fashion. > ...... I am not an expert on natural language processing. I am really sorry for not transforming fully your grammar into Prolog (the states S0, S1, etc. were missing). Let me try this new set of rules. The newly added rule makes the recursion not a single linear recursion but a multiple linear one. The "np" portion is transformed into a multiple linear recursion (without mutually recursive predicates) as follows. s(S0,S) :- np(P,N,nom,S0,S1), vp(P,N,S1,S). np(P,N,C,S0,S) :- word(X,S0,S), pronoun(X,P,N,C). np(3,N,_,S0,S) :- word(the,S0,S1), word(X,S1,S), noun(X,N). np(3,N,_,S0,S) :- word(the,S0,S1), word(X,S1,S2), noun(X,N), word(that,S2,S3), word(Y,S3,S), intrans(Y,P,M). np(3,N,_,S0,S) :- word(the,S0,S1), word(X,S1,S2), noun(X,N), word(that,S2,S3), word(Y,S3,S4), trans(Y,P,M), np(_,_,acc,S4,S). np(3,N,_,S0,S) :- word(the,S0,S1), word(X,S1,S2), noun(X,N), word(that,S2,S3), np(P,N1,nom,S3,S4), word(Y,S4,S), trans(Y,P1,N2). Similarly for "vp" portion as well. I understand the above "np" rule set as follows: np(_,_) :- Pronoun(X). np(3,_) :- "the", Noun(X). np(3,_) :- "the", Noun(X), "that", Intrans(Y). np(3,_) :- "the", Noun(X), "that", Trans(Y), np(_,acc). np(3,_) :- "the", Noun(X), "that", np(_,nom), Trans(Y). (Notice that in the real execution, we must associate it with all the proper states to make it complete. 3 means that all the generated Noun or Pronoun should be the third person, if my understanding is right). As I discussed in my "Processing Multiple Linear Recursions" paper, this multiple linear recursion cannot be evaluated by a transitive closure algorithm. However, it can be evaluated by side-relation unioned processing. We take the exit rule as e :- [Pronoun(X)] U ["the", Noun(X)] U ["the", Noun(X), "that", Intrans(Y)]. and the left portions of the second linear recursive rule as l2 :- "the", Noun(X), "that". The rule set is equivelent to, (Sorry for further simplification, we could associate more states but the results should be essentially the same). np(_) :- e. np(_) :- l2, Trans(Y), np(acc). np(_) :- l2, np(nom), Trans(Y). The trick in the evaluation of this multiple linear recursion is that every time after we go through the portion ["the", Noun(X), "that"], we set a flag [2]. If we go through one more portion [Trans(Y)], the flag is switched to [1]. Flag [1] should not have a matched Trans(Y) after np(acc) but Flag [2] needs the match of a Trans(Y) after np(nom). So the evaluation is quite close to the evaluation of a two-sided single linear recursion (e.g., the same-generation problem). That is, we may use the counting method or the magic sets method and treat it as if it were a single linear recursion. This is another good example which shows why deductive DB people want to study something beyond transitive closure (e.g. the same-generation recursion) in the evaluation of linear recursions. This is a very interesting example. Thanks. -jiawei