RE: ISSUE-28: Recursion in the RIF Core

<< all PR systems have a way to filter working memory after 
the rules have run>>

That's an interesting supposition. Care to elaborate?

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 Gary Hallmark
Sent: 22 February 2007 22:14
To: Michael Kifer
Cc: Rule Interchange Format (RIF) Working Group WG
Subject: Re: ISSUE-28: Recursion in the RIF Core


Yes, I think all PR systems have a way to filter working memory after 
the rules have run, so you could *filter* for "ancestor(John, ?x)".  
More complex queries may be more challenging, e.g. ancestor(John, ?x) & 
married(?x, Sally).
Perhaps such a query could be rewritten by the PR-RIF translation 
software as a rule "IF ancestor(John, ?x) & married(?x, Sally) THEN 
answer(?x)".  This rule would be merged with the RIF ruleset(s).  
Answers can then be collected using simple filtering. 

Michael Kifer wrote:

>Gary,
>A query is still a query. If you are asking for ancestors of John, you
should
>receive them in PR as well. It is just that PR will first compute the
whole
>thing first. Does Oracle's rule language have such postprocessing
>filtering capabilities?
>
>
>	--michael  
>
>
>  
>
>>My take-away from the email discussion on this issue is that PR can 
>>express recursive rules just as well as Horn. 
>>The real issue is how the rules are "executed". 
>>
>>With Horn (prolog), one "queries the KB" to execute rules.  The cool 
>>thing about queries is that they can (optionally) pass in bound 
>>variables to terminate the recursion.  E.g., with a simple factorial 
>>ruleset, the queries "factorial(?x, 24)" and "factorial(4, ?y)" 
>>terminate, whereas factorial(?x, ?y) does not.
>>
>>With PR, there is no query in the prolog sense.  One executes rules by

>>giving a run(n) command, where n is the number of rules to fire.  If n

>>is not specified, the PR system runs until no more rules fire.  
>>Essentially, the run command is like a query with all variables
unbound, 
>>but instead of the "answer" being returned as a set of variable 
>>bindings, the "answer" is left as a bunch of factorial tuples in
working 
>>memory. 
>>
>>So, I would withdraw the PR-recursion issue and raise a PR-query
issue.  
>>Per the charter,
>>
>>The core rule engine functionality is to load zero or more rulesets
(or 
>>datasets) and then answer zero or more queries against the merged 
>>contents. This functionality is largely independent of engine 
>>implementation strategies. (In particular, it works with both forward 
>>chaining <http://en.wikipedia.org/wiki/Forward_chaining> and backward 
>>chaining <http://en.wikipedia.org/wiki/Backward_chaining>.)
>>
>>We will have to be very careful about how to define a query against a
PR 
>>system.
>>
>>Nichols, Deborah L. wrote:
>>
>>    
>>
>>>First, my apologies for a late posting of the recursion issue to the
>>>Issues board.  Sponsor work has increased, and I haven't kept up to
>>>date properly.  That said, however, I still want to record the issue
>>>officially and clarify some aspects before stating the resolution.
>>>
>>>Axel's generalization of the issue makes an important point IMO.  If
>>>the RIF Core allows "degrees of freedom" that not all rule languages
>>>can express or implement, then should those features be restricted
(by
>>>putting them out of the Core) or restrictable (e.g., by profiles)?
>>>
>>>(Profiles is the next issue to be - finally - posted.)
>>>
>>>If we say that the Core should not be limited by what PR language can
>>>handle (vs. what PR implementations can handle) - Paul's point - and
we
>>>leave recursion in, then will a difficulty arise when compliance is
>>>defined?
>>>
>>>If we can come to a resolution by email, it isn't necessary to spend
>>>meeting time on discussion.
>>>
>>>Regards,
>>>Deborah
>>>
>>>-----Original Message-----
>>>From: public-rif-wg-request@w3.org
>>>[mailto:public-rif-wg-request@w3.org] On Behalf Of Paul Vincent
>>>Sent: Tuesday, February 20, 2007 6:39 AM
>>>To: Rule Interchange Format (RIF) Working Group WG
>>>Subject: RE: ISSUE-28: Recursion in the RIF Core 
>>>Importance: Low
>>>
>>>
>>> 
>>>
>>>      
>>>
>>>>	I thought that we did sort out this issue. Namely, that
>>>>   
>>>>
>>>>        
>>>>
>>>recursive 
>>> 
>>>
>>>      
>>>
>>>>	clauses can be expressed by PR. I am also confused why did this
>>>>   
>>>>
>>>>        
>>>>
>>>issue 
>>> 
>>>
>>>      
>>>
>>>>	came back.
>>>>   
>>>>
>>>>        
>>>>
>>>Gary suggested a scheme whereby it would be possible to map a
recursive
>>>PROLOG-type rule into a PR language (by effectively simulating bwd
>>>chaining). And of course procedural extensions to PR languages can
>>>certainly handle recursion (albeit not as "PR rules" per se). 
>>>
>>>But saying 
>>>"PR language implementations can handle recursion" 
>>>...does not equal 
>>>"PR can handle recursion" 
>>>(for me anyway). So this makes RIF Core "PR possible" rather than "PR
>>>friendly". Hence, I assume, the "outstanding issue" for RIF. 
>>>
>>>But is it worth debating further? That would be my question.
>>>
>>>[Conjecture:]
>>>Of course, the counterargument is that without recursion, RIF Core is
>>>"meaningless" (as a rule language or maybe as a rule representation).

>>>
>>>And of course, a countercounterargument is that RIF Core probably
>>>*cannot* be a core subset covering all rule language semantics and
>>>still
>>>be a useful language in its own right (eg RIF Horn profile), and
indeed
>>>this should not be its goal: at best it should represent some common
>>>expression representation scheme and/or a generalized rule metamodel
>>>and/or rule classification scheme. 
>>>
>>>Just my 2 eurocents...
>>>
>>>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 Michael Kifer
>>>Sent: 20 February 2007 09:51
>>>To: axel@polleres.net
>>>Cc: Rule Interchange Format (RIF) Working Group WG
>>>Subject: Re: ISSUE-28: Recursion in the RIF Core 
>>>
>>>
>>>
>>>I thought that we did sort out this issue. Namely, that recursive
>>>clauses
>>>can be expressed by PR. I am also confused why did this issue came
>>>back.
>>>
>>>
>>>	--michael  
>>>
>>> 
>>>
>>>      
>>>
>>>>Now I am a bit confused about that, to be honest, if I think it a
bit
>>>>   
>>>>
>>>>        
>>>>
>>> 
>>>
>>>      
>>>
>>>>further:
>>>>
>>>>if we assume that RIF core should be common to ALL rules languages 
>>>>around, would we also need to cut down other degrees of freedom
which
>>>>   
>>>>
>>>>        
>>>>
>>> 
>>>
>>>      
>>>
>>>>Core allows: e.g. that we do not differentiate between the symbols 
>>>>allowed for constants and function symbols, which some
>>>>   
>>>>
>>>>        
>>>>
>>>systems/languages 
>>> 
>>>
>>>      
>>>
>>>>do, that we allow the same symbol to be used with different arities,
>>>>which some systems don't allow.
>>>> Next, there are languages which e.g. restrict the allowed arity of 
>>>>predicates and thus would neither cover all of RIF Core, e.g. SWRL
>>>>only allows unary and binary preds in Horn rules.
>>>>
>>>>Would these then also be issues?
>>>>
>>>>I don't think we need to go that far. If we define the core really
>>>>   
>>>>
>>>>        
>>>>
>>>only 
>>> 
>>>
>>>      
>>>
>>>>as "what is expressible by any implemented rules system" then we'd 
>>>>probably end up with propositional nonrecursive horn-rules with one 
>>>>proposition in the antecedent?
>>>>
>>>>Probably I got this wrong, but it would be good if we define where
to
>>>>   
>>>>
>>>>        
>>>>
>>> 
>>>
>>>      
>>>
>>>>draw the line, right?
>>>>
>>>>just my 2 cents,
>>>>Axel
>>>>
>>>>Rule Interchange Format (RIF) Working Group Issue Tracker wrote:
>>>>   
>>>>
>>>>        
>>>>
>>>>>ISSUE-28: Recursion in the RIF Core
>>>>>
>>>>>http://www.w3.org/2005/rules/wg/track/issues/28
>>>>>
>>>>>Raised by: Deborah Nichols
>>>>>On product: Technical Design
>>>>>
>>>>>Issue:  Recursion in the RIF Core
>>>>>Opened by Deborah Nichols [on behalf of RIF Chairs]
>>>>>
>>>>>This issue concerns whether or not to include recursion in the
>>>>>     
>>>>>
>>>>>          
>>>>>
>>>specification 
>>> 
>>>
>>>      
>>>
>>>>>of the RIF Core.
>>>>>
>>>>>Summary of an argument for exclusion:  
>>>>>Assuming 
>>>>>(1) that the RIF Core consists of positive Horn clauses and 
>>>>>(2) that the RIF Core should be "common to" (i.e., translatable
>>>>>     
>>>>>
>>>>>          
>>>>>
>>>into) all RIF 
>>> 
>>>
>>>      
>>>
>>>>>dialects, and 
>>>>>(3) since positive Horn includes recursive formulas, 
>>>>>then (4) if Production Rules cannot support recursion, 
>>>>>the conclusion is (5) that would be no "compliant" PR dialect of
>>>>>     
>>>>>
>>>>>          
>>>>>
>>>the
>>>RIF 
>>> 
>>>
>>>      
>>>
>>>>>Core.  
>>>>>But it isn't acceptable not to have a PR dialect of RIF; 
>>>>>therefore, (6) recursion should be "removed" from the Core.
>>>>>(One method of "removal" would be to use profiles; see related
>>>>>     
>>>>>
>>>>>          
>>>>>
>>>Issue.)
>>> 
>>>
>>>      
>>>
>>>>>Background and discussion:
>>>>>
>>>>>At F2F4, Gary Hallmark took an action [#188] to address the
>>>>>     
>>>>>
>>>>>          
>>>>>
>>>question
>>>whether 
>>> 
>>>
>>>      
>>>
>>>>>recursive rules should be included in the RIF Core.  Of particular
>>>>>     
>>>>>
>>>>>          
>>>>>
>>>concern was 
>>> 
>>>
>>>      
>>>
>>>>>the handling of recursion for Production Rule (PR) systems.  Gary
>>>>>     
>>>>>
>>>>>          
>>>>>
>>>presented 
>>> 
>>>
>>>      
>>>
>>>>>the issue in email on 12 Dec 2006
>>>>>     
>>>>>
>>>>>          
>>>>>
>>>(http://lists.w3.org/Archives/Public/public-
>>> 
>>>
>>>      
>>>
>>>>>rif-wg/2006Dec/0035.html), questioning whether production-rule (PR)
>>>>>     
>>>>>
>>>>>          
>>>>>
>>>systems 
>>> 
>>>
>>>      
>>>
>>>>>can support recursion and could implement a Core that included it.
>>>>>     
>>>>>
>>>>>          
>>>>>
>>> 
>>>
>>>      
>>>
>>>>>"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 ....[factorial example follows]"
>>>>>
>>>>>The implication for the RIF Core, as Gary stated later in the
>>>>>     
>>>>>
>>>>>          
>>>>>
>>>thread, is that:
>>> 
>>>
>>>      
>>>
>>>>>"As I understand it, RIF Core should be common to *all* RIF
>>>>>     
>>>>>
>>>>>          
>>>>>
>>>dialects, 
>>> 
>>>
>>>      
>>>
>>>>>including a production rule dialect.  Now, it's clear that there
>>>>>     
>>>>>
>>>>>          
>>>>>
>>>are 
>>> 
>>>
>>>      
>>>
>>>>>aspects of production rules that probably won't translate to Core
>>>>>     
>>>>>
>>>>>          
>>>>>
>>>(e.g. 
>>> 
>>>
>>>      
>>>
>>>>>priority, retract).  That may be ok if we can add them to the
>>>>>     
>>>>>
>>>>>          
>>>>>
>>>dialect 
>>> 
>>>
>>>      
>>>
>>>>>without breaking the Core semantics.  On the other hand, it is
>>>>>     
>>>>>
>>>>>          
>>>>>
>>>critical 
>>> 
>>>
>>>      
>>>
>>>>>that *everything* in Core can be translated to PR, otherwise we
>>>>>     
>>>>>
>>>>>          
>>>>>
>>>have 
>>> 
>>>
>>>      
>>>
>>>>>dialects of Core itself, which means it really isn't a Core.
>>>>>     
>>>>>
>>>>>          
>>>>>
>>>Therefore, 
>>> 
>>>
>>>      
>>>
>>>>>if Core supports recursive rules, then so should PR.   If we don't
>>>>>     
>>>>>
>>>>>          
>>>>>
>>>think 
>>> 
>>>
>>>      
>>>
>>>>>it's practical to support recursive rules in PR, then we should
>>>>>     
>>>>>
>>>>>          
>>>>>
>>>remove 
>>> 
>>>
>>>      
>>>
>>>>>this feature from Core."
>>>>>
>>>>>This issue is related to the "profiles" issue:  If RIF supports
>>>>>     
>>>>>
>>>>>          
>>>>>
>>>profiles, then 
>>> 
>>>
>>>      
>>>
>>>>>recursion may be the most obvious feature to make "optional".  
>>>>>
>>>>>The recursion issue also has implications for defining conformance
>>>>>     
>>>>>
>>>>>          
>>>>>
>>>to the RIF 
>>> 
>>>
>>>      
>>>
>>>>>Core.  See Dave Reynolds' explanation 
>>>>>
>>>>>     
>>>>>
>>>>>          
>>>>>
>>>(http://lists.w3.org/Archives/Public/public-rif-wg/2007Jan/0079.html)
:
>>> 
>>>
>>>      
>>>
>>>>>"The specific issue that triggered a lot of this is the extent to
>>>>>     
>>>>>
>>>>>          
>>>>>
>>>which 
>>> 
>>>
>>>      
>>>
>>>>>existing production rule engines can implement recursive Horn rules
>>>>>     
>>>>>
>>>>>          
>>>>>
>>>and 
>>> 
>>>
>>>      
>>>
>>>>>so whether RIF Core should be RIF-Horn-without-recursion. Given a
>>>>>     
>>>>>
>>>>>          
>>>>>
>>>target 
>>> 
>>>
>>>      
>>>
>>>>>query pattern (or some other context of use information) then a PR
>>>>>     
>>>>>
>>>>>          
>>>>>
>>>RIF 
>>> 
>>>
>>>      
>>>
>>>>>translator can implement recursive horn rules but may be
>>>>>     
>>>>>
>>>>>          
>>>>>
>>>non-terminating 
>>> 
>>>
>>>      
>>>
>>>>>for unrestricted queries. So either RIF has to convey that context
>>>>>     
>>>>>
>>>>>          
>>>>>
>>>of 
>>> 
>>>
>>>      
>>>
>>>>>use, or the issue of ruleset termination is outside of RIF
>>>>>     
>>>>>
>>>>>          
>>>>>
>>>conformance, 
>>> 
>>>
>>>      
>>>
>>>>>or we need some other notion of RIF Core."
>>>>>
>>>>>Chris Welty summarized the discussion of the nature of the Core,
>>>>>     
>>>>>
>>>>>          
>>>>>
>>>from the 16 
>>    
>>
>>> 
>>>
>>>      
>>>
>>>>>Dec telcon
>>>>>     
>>>>>
>>>>>          
>>>>>
>>>(http://lists.w3.org/Archives/Public/public-rif-wg/2007Jan/0093): 
>>> 
>>>
>>>      
>>>
>>>>>"We then went on discussing the nature of the CORE. The discussion
>>>>>     
>>>>>
>>>>>          
>>>>>
>>>centered
>>> 
>>>
>>>      
>>>
>>>>>on whether or not all languages were required to be able to
>>>>>     
>>>>>
>>>>>          
>>>>>
>>>translate 
>>> 
>>>
>>>      
>>>
>>>>>FROM "all" of the CORE to be conformant.  Some continue to feel
>>>>        
>>>>
>>>>>     
>>>>>
>>>>>          
>>>>>
>>>this
>>>is 
>>> 
>>>
>>>      
>>>
>>>>>unrealistic, however we lack examples that demonstrate it.  Several
>>>>>     
>>>>>
>>>>>          
>>>>>
>>>expressed 
>>> 
>>>
>>>      
>>>
>>>>>support for a very limited notion of profiles for the CORE.
>>>>>     
>>>>>
>>>>>          
>>>>>
>>>Profiles would 
>>> 
>>>
>>>      
>>>
>>>>>specify features that we may consider "optional" or that may
>>>>>     
>>>>>
>>>>>          
>>>>>
>>>determine the 
>>> 
>>>
>>>      
>>>
>>>>>degree of conformance of a translation.  Examples of features in a
>>>>>     
>>>>>
>>>>>          
>>>>>
>>>possible 
>>> 
>>>
>>>      
>>>
>>>>>CORE profile were: recursion, decidability, complexity bounds,
>>>>>     
>>>>>
>>>>>          
>>>>>
>>>functions.
>>> 
>>>
>>>      
>>>
>>>>>"There seemed to be consensus that there is one core dialect with
>>>>>     
>>>>>
>>>>>          
>>>>>
>>>the 
>>> 
>>>
>>>      
>>>
>>>>>expressivity of about Horn and that we should move forward with the
>>>>>     
>>>>>
>>>>>          
>>>>>
>>> 
>>>
>>>      
>>>
>>>>>specification of that dialect, independently of other
>>>>>     
>>>>>
>>>>>          
>>>>>
>>>considerations.  If 
>>> 
>>>
>>>      
>>>
>>>>>there is a notion of profiles it should be extremely restricted so
>>>>>     
>>>>>
>>>>>          
>>>>>
>>>that 
>>> 
>>>
>>>      
>>>
>>>>>the "CORE is still a core".  At the moment, we do not have any 
>>>>>specific "features" of the CORE that anyone has objected to, except
>>>>>     
>>>>>
>>>>>          
>>>>>
>>>possibly 
>>> 
>>>
>>>      
>>>
>>>>>recursive rules, so it is still not clear that we need profiles for
>>>>>     
>>>>>
>>>>>          
>>>>>
>>>the CORE.
>>> 
>>>
>>>      
>>>
>>>>>"We discussed whether RIF dialects must include and extend the
>>>>>     
>>>>>
>>>>>          
>>>>>
>>>CORE.
>>>The 
>>> 
>>>
>>>      
>>>
>>>>>possibility of profiles opens the door for some dialects to
>>>>>     
>>>>>
>>>>>          
>>>>>
>>>eliminate certain 
>>> 
>>>
>>>      
>>>
>>>>>features (again, from a very restricted set).  In other words,
>>>>>     
>>>>>
>>>>>          
>>>>>
>>>profiles may 
>>> 
>>>
>>>      
>>>
>>>>>allow some dialects to extend a subset of the CORE."
>>>>>
>>>>>Links to related email threads concerning PR and recursion:
>>>>>http://lists.w3.org/Archives/Public/public-rif-wg/2006Dec/0035 
>>>>>http://lists.w3.org/Archives/Public/public-rif-wg/2006Dec/0127
>>>>>     
>>>>>
>>>>>          
>>>>>
>>>contains 
>>> 
>>>
>>>      
>>>
>>>>>discussion following on Gary's factorial example.
>>>>>http://lists.w3.org/Archives/Public/public-rif-wg/2006Mar/0202
>>>>>http://lists.w3.org/Archives/Public/public-rif-wg/2006Dec/0047.html
>>>>>     
>>>>>
>>>>>          
>>>>>
>>>questions 
>>> 
>>>
>>>      
>>>
>>>>>whether recursion should be included in a PR system.
>>>>>
>>>>>Related threads on "recursive rules" vs. "recursive terms":
>>>>>http://lists.w3.org/Archives/Public/public-rif-wg/2006Dec/0114 
>>>>>http://lists.w3.org/Archives/Public/public-rif-wg/2006Dec/0103 
>>>>>
>>>>>An earlier (March 2006) discussion of recursion: 
>>>>>http://lists.w3.org/Archives/Public/public-rif-wg/2006Mar/0106.html
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>     
>>>>>
>>>>>          
>>>>>
>>>>-- 
>>>>Dr. Axel Polleres
>>>>email: axel@polleres.net  url: http://www.polleres.net/
>>>>
>>>>
>>>>
>>>>
>>>>
>>>>
>>>>   
>>>>
>>>>        
>>>>
>>>
>>>
>>>
>>> 
>>>
>>>      
>>>
>>    
>>
>
>
>
>  
>

Received on Friday, 23 February 2007 08:19:14 UTC