RE: [TED] Action-188, ISSUE: production rule systems have "difficulty" with recursive rules in RIF Core

If a forward chaining goal needs additional information, like
factorials, it is best done by pulling in the facts locally (i.e. not
asserted into the working memory) for unification - whether that is with
a backward chaining goal a jrules like 'from'.

 

JBoss Rules already supports 'from' in trunk and I'll be adding some
backward chaining predicate support, as shown in the wiki page, based on
a modified 'from' node.

 

"The issue here is:  is there a general strategy to evaluate recursive
positive Horn rules using forward chaining, so that every ruleset in RIF
Core can be translated to production rules?"

 

You really wouldn't want to simulate backward chaining this way with a
forward chaining engine -Instead you create special Rete node types that
are able to pull and unify data from a remote source - that remote
source could be the data propagated from another query. In a forward
chaining engine Queries and Rules are interchangeable, both have the
same left hand side syntax, the only differences is that a query returns
it's data.

 

Production Rule systems are starting to have more in built declarative
power - Jess 'accumulate', JRules 'collect' and 'from' (all of which are
now supported in jboss rules) and this will be extended to start
supporting Event Stream/Management Processing
http://wiki.jboss.org/wiki/Wiki.jsp?page=EventStreamAnalysis. Sure you
can simulate these one way or another and provide mappings, after all
these engines are turing complete, but the advantage of having them as
real syntax is that we gain real performance benefits and declaratives.
If I take my 'accumulate' node and simulate it with a series of rules
and facts I can no longer round trip, the declarative nature of that
single conditional element is lost and most likely some performance.

 

Mark

 

________________________________

From: Paul Vincent [mailto:pvincent@tibco.com] 
Sent: 12 December 2006 23:17
To: Mark Proctor; Boley, Harold; Gary Hallmark
Cc: W3C RIF WG
Subject: RE: [TED] Action-188, ISSUE: production rule systems have
"difficulty" with recursive rules in RIF Core

 

Gary's qu was:

>The issue here is:  is there a general strategy to evaluate recursive
positive Horn rules using forward chaining, so that every ruleset in RIF

> 

>Core can be translated to production rules?  I don't really know for
sure, but I suspect the answer is "no".  

 

Why would you want to define recursion
(http://en.wikipedia.org/wiki/Recursion) in a production rule system?
Recursion is also (/mainly) a feature of procedural programming
languages. The fact that you can define logical statements using
recursion is surely not very interesting, as you can simply map such
statements to a Java function (or equivalent procedural script). 

 

In terms of "business rules" (and BR Group members may correct me here),
the definition of "factorial" below is really a "computation rule" - not
an inference rule - and would realistically map to a function statement
(not a production rule) in most production rule languages. [And indeed,
I can usually map a computation statement written as a Java method into
something like PROLOG too.]

 

Issues: 

- doing such computation mappings may extend the scope of RIF too much
(do I want to map PROLOG to production rules + scripts?). We risk making
RIF too extensive (and a subset of something like ADM -
http://adm.omg.org/ ) 

- (my interpretation of) the goal is rule interchange primarily across
similar rule semantics; swapping rules across rule types may not be very
sensible (although vendors may want to extend their rule engines to
cover additional semantics, as Mark implies for JBoss Rules below).
Another example is a constraint rule. "There can never be more than 2
riders on a motorbike". If I have a rule that allocates an additional
rider to a motorbike, does my RIF translator need to be cognisant of all
such constraint rules to add a qualification to my production rule? And
how do I map a number of constraints to do some constraint based
reasoning using production rules? The latter *can* often be done, but
(again) is probably a research topic for a RIF translator...

 

So: good news for the academic community!

 

Paul Vincent

TIBCO - ETG/Business Rules 

 

 

 

-----Original Message-----
From: public-rif-wg-request@w3.org [mailto:public-rif-wg-request@w3.org]
On Behalf Of Mark Proctor
Sent: 12 December 2006 21:37
To: Boley, Harold; Gary Hallmark; W3C RIF WG
Subject: RE: [TED] Action-188, ISSUE: production rule systems have
"difficulty" with recursive rules in RIF Core

 

 

It is fully possible to have a pattern in rete that is goal seeking.

Jess already does this, but it's driven by naming conventions (ordered

facts) instead of arity. I'm looking to apply predicate style patterns

in our rule language. See the wiki for a rough brain dump:

http://wiki.jboss.org/wiki/Wiki.jsp?page=BackwardChaining

 

Mark

 

-----Original Message-----

From: public-rif-wg-request@w3.org [mailto:public-rif-wg-request@w3.org]

On Behalf Of Boley, Harold

Sent: 12 December 2006 20:59

To: Gary Hallmark; W3C RIF WG

Subject: RE: [TED] Action-188, ISSUE: production rule systems have

"difficulty" with recursive rules in RIF Core

 

 

> AFAIK, a complete solution is at least a research problem.

 

Related issues have been studied using "magic set" transformations:

http://www.informatik.uni-trier.de/~ley/db/conf/pods/MumickFPR90.html

http://www.sigmod.org/sigmod/pods/proc03/online/105-behrend.pdf

http://www.cs.bris.ac.uk/~john/transformation.html

http://indalog.ual.es/Xindalog/documentacion/transf_xindalog.html

. . .

 

-- Harold

 

 

-----Original Message-----

From: public-rif-wg-request@w3.org [mailto:public-rif-wg-request@w3.org]

On Behalf Of Gary Hallmark

Sent: Tuesday, December 12, 2006 4:17 PM

To: W3C RIF WG

Subject: [TED] Action-188, ISSUE: production rule systems have

"difficulty" with recursive rules in RIF Core

 

 

Production rule systems based on the rete algorithm 

(http://en.wikipedia.org/wiki/Rete_algorithm) have a procedural 

semantics characterized by forward chaining 

(http://en.wikipedia.org/wiki/Forward_chaining).  The inference engine 

fires rules whose conditions match data ("facts") in working memory.  

The rules may add facts or otherwise modify working memory, which may 

cause additional rules to fire, etc.

 

The current proposal for a RIF Core is positive Horn clauses.  Such 

clauses may be recursive, meaning that the relation name in the head of 

a rule also occurs (directly or indirectly) in the body of that rule.  

Because the semantics of a set of positive Horn clauses can be defined 

without reference to an evaluation strategy, an implementation is free 

to use something other than forward chaining.  In fact, most prolog 

implementations use backward chaining.

 

The issue here is:  is there a general strategy to evaluate recursive 

positive Horn rules using forward chaining, so that every ruleset in RIF

 

Core can be translated to production rules?  I don't really know for 

sure, but I suspect the answer is "no".  Here is a simple example to 

illustrate the problem:

 

Consider the 2 RIF Core rules below that define factorial (on 

non-negative integers).  We assume a built in successor function "succ" 

and multiply function "mult".

 

factorial(0 1)

factorial(?in ?out) :- factorial(?x ?y) & And(?in = succ(?x)  ?out = 

mult(?in ?y))

 

A naive translation from RIF Core to a "generic" production rule 

language might produce the following:

 

assert(factorial(0, 1))

IF factorial(?x, ?y)

THEN assert(factorial(?x + 1, (?x + 1) * ?y))

 

The problem with the naive translation is it will generate *all* 

factorial facts:

factorial(1 1)

factorial(2 2)

factorial(3 6)

factorial(4 24)

factorial(5 120)

...etc....

until memory is exhausted.  In other words, the naive translation using 

forward chaining is not "goal directed".  In contrast, a backward 

chaining implementation would start with a query such as:

 

:- factorial(4 ?out)

 

and may terminate after generating subgoals factorial(3 ?), factorial(2 

?), and factorial(1 ?).

 

One technique to make production rule systems more goal-directed is to 

explicitly represent subgoals as facts.  Jess and Haley (and probably 

others) PR systems even have some special syntax to make this a bit 

easier, but it is by no means hidden from the rule author. 

 

To illustrate the technique, we could translate the factorial rules (and

 

the query) from RIF Core to our "generic" PR language as follows:

 

// translation of rules

assert(factorial(0, 1))

IF need_factorial(?x) and not(factorial(?x, ?)) and not(factorial(?x - 

1, ?))

THEN assert(need_factorial(?x -1))

IF need_factorial(?x) and factorial(?x - 1, ?y)

THEN assert(factorial(?x, ?x * ?y))

 

// translation of query

assert(need_factorial(4))

IF factorial(4, ?out) THEN print("factorial of 4 is " ?out)

 

The above translation has some deficiencies, however. 

- The translation doesn't work for queries like :- factorial(?in, 24)

- The need_factorial subgoals are never removed from working memory. 

- More complex rules involving mutual recursion, double recursion, etc. 

are, well, more complex...

 

AFAIK, a complete solution is at least a research problem.