RE: ISSUE-28: Recursion in the RIF Core

> 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. 

Rule engines "execute rules", not "answer queries". You could argue the
*role* of the rule engine is to provide "answers", and that typically
the rule engine results will be queried post-execution. The latter query
is not necessarily a function of the rule engine. Or you could interpret
this phrase as meaning that the rule engine will "query" the rulesets to
find the appropriate rules to fire. Or even that the conditions of rules
are queries against the working memory.

Examples:
1. In a forward chaining PR system: I supply a ruleset and data, and
execute (forward chaining) rules which update the results. Whether I
bother to query the results is up to me - I might in fact be invoking
functions as a result of rule firings, so there might not be any "query"
action per se.
2. In a PROLOG system, you could easily argue that you use a "query" to
invoke the rule execution. Personally I would describe PROLOG as
somewhat more than just a "rule engine". 

I suggest this charter phrase be interpreted "liberally" (aka not
literally).



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: 22 February 2007 20:39
To: Gary Hallmark
Cc: Nichols, Deborah L.; Rule Interchange Format (RIF) Working Group WG
Subject: Re: ISSUE-28: Recursion in the RIF Core 



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 Thursday, 22 February 2007 21:12:40 UTC