RE: W3C RIF: "recursive rules" vs "recursive terms"

Sandro - actually the problem is more significant than that - and this is where RIF stumbles into the same space as OMG ADM and any other cross-compiler issues. We are effectively trying to alter syntax to match semantics without understanding the intent (such as provided by OMG SBVR).

In the "ancestor problem" you are defining a method for determining whether a is an ancestor of b based on known parent records. 

In a PR system I would want to know *when* I want this information:
- do I want to create new facts of all possible ancestors for some other system?
- do I have some condition in some other rule (such as a medical test) that requires simple ancestory information?

For the former I would probably not bother with a PR system: a simple loop through all my DB of people with recursive inner loop would built that table for me (or some other procedural strategy).

For the latter, then my ancestry test is likely to be a need to find (say) if any (known) ancestors of the patient had condition X.

A possible solution for this would be (assuming some sparse list of people with the condition X):
1. define a ruleVariable XPerson (or import a class with associated data filter) to match the target set of people with condition X
2. use a query in a rule condition 
e.g. if ancestor( patient, XPerson) then ...
3. define a recursive function ancestor( A, B) using the action language or Java.

The latter does not make efficient use of the Rete network, and defers the ancestor test to an action language. If I was doing the ancestor test more than occasionally, I would probably take the hit of designing my DB tables to include ancestry data to save recomputing it. 

So, the PR solution would be:
- if such recursive problems (to "find information") are used frequently or performance is critical, then it is probably more efficient to maintain the information in an easily queryable form (as opposed to calculated form) 
- if such recursive problems are used only occasionally and are not performance critical, then it may be simpler to derive the information at runtime
- if the problem space was such that much data needed to be derived recursively + performance was not critical (e.g. global concepts of the semantic web) I would assume that this was a problem not suited for current production rule systems!

In either case, for PR type systems, the problem is at best a boundary condition. 

Paul Vincent
TIBCO - ETG/Business Rules 
 

-----Original Message-----
From: Sandro Hawke [mailto:sandro@w3.org] 
Sent: 19 December 2006 00:06
To: Gary Hallmark
Cc: Paul Vincent; public-rif-wg@w3.org
Subject: Re: W3C RIF: "recursive rules" vs "recursive terms" 

> The naive translation of recursive rules into PR usually attempts to 
> produce all possible answers (all possible facts), until it runs out of 
> working memory.  In PR,  each answer is a fact is an "object" (i.e. 
> takes up some memory).  So the issue is, will the PR system run out of 
> memory before rules stop firing?  For the factorial and append examples, 
> there are an infinite number of answers and so the answer is no.  For 
> the ancestor example, it depends on the size of transitive closure vs. 
> memory size.   Note that without some kind of goal seeking "tricks" 
> added to the naive translation, you can't generate only relevant facts 
> for queries like "who are *my* ancestors" .
> 
> Fortunately, business users seem less concerned about their ancestry 
> than are academics ;-)

So ancestor basically works, but is calculated in an inefficient manner,
whereas human-parent (or factorial, or append) never works with PR.  I
think that means the first kind of ruleset should be allowed in
PR-friendly dialects and the second kind should be disallowed.  But I
don't know how to define the difference....

      -- Sandro


> Sandro Hawke wrote:
> 
> >>Sandro - PR rules are not explicitly referenced at runtime (ie they may
> >>be named for rule management, but not for execution). So they cannot
> >>"recurse" and I cannot build logical recursive definitions using PR.
> >>    
> >>
> >
> >Can you define "ancestor" in PR?   Something like:
> >
> >   if parent(x,y) then ancestor(x,y).
> >   if parent(x,y) and ancestor(y,z) then ancestor(x,z).
> >
> >That's a recursive ruleset, but it's not going to produce any infinite
> >loop, right?
> >
> >On the other hand, saying "everyone has a parent":
> >
> >  if human(x) then there exists y such that parent(x,y) and human(y)
> >
> >will cause an infinite loop (when turning to a Production Rule creation a
> >new object y for each firing).
> >
> >The danger, I *think* is not in creating new facts but in creating new
> >"objects" (which is essentially equivalent to having function terms in
> >logic), AND having recursion.  Maybe in some definable combination.  I'm
> >sure there's a formal result here that I don't know or can't quite
> >remember.
> >
> >  
> >
> >>My question (rhetorical at this stage is): why would I want to do =
> >>recursion?
> >>    
> >>
> >
> >The ancestor example above is probably compelling, right?   You see the
> >value of that kind of rule?
> >
> >The first program I got paid to write ($3/hr) figured out the cost of a
> >product based on the costs of all its components, and the costs of those
> >components based on their components, etc, recursively.  How's that for
> >a use case?  :-)  
> >
> >  
> >
> >>Some problems are best defined in terms of "rules" that =
> >>reference themselves (c.f "clever programming techniques" as implied in =
> >>http://blogs.msdn.com/ericlippert/archive/2004/07/21/189974.aspx ). =
> >>Recursion may be common in logic systems, but in PR systems (mostly =
> >>implementing business rules), it is so rare I am not aware of any =
> >>commercially successful PR system that provides it.
> >>    
> >>
> >
> >When you say that, you're talking about some different kind of recursion
> >than I am in this message, right?   
> >
> >  
> >
> >>Note also our previous discussions on recursion -  =
> >>http://lists.w3.org/Archives/Public/public-rif-wg/2006Mar/0106.html=20
> >>    
> >>
> >
> >Thanks for finding that.
> >
> >     - Sandro
> >
> >  
> >

Received on Tuesday, 19 December 2006 09:48:30 UTC