- From: Paul Vincent <pvincent@tibco.com>
- Date: Fri, 23 Feb 2007 06:53:27 -0800
- To: <kifer@cs.sunysb.edu>
- Cc: "Gary Hallmark" <gary.hallmark@oracle.com>, "Rule Interchange Format \(RIF\) Working Group WG" <public-rif-wg@w3.org>
Thanks - I think I get it: <<PR engines can simulate queries by implementing them as additional rules>>. Just like <<PR engines can simulate recursion by simulating backward chaining>>. I thought Gary was talking about a common technical feature of PR systems I wasn't familiar with :) Paul Vincent TIBCO - ETG/Business Rules -----Original Message----- From: kifer@cs.sunysb.edu [mailto:kifer@cs.sunysb.edu] Sent: 23 February 2007 14:26 To: Paul Vincent Cc: Gary Hallmark; Rule Interchange Format (RIF) Working Group WG Subject: Re: ISSUE-28: Recursion in the RIF Core Gary mentioned before that things can be achieved by translation. For instance, if you need to find ancestors of john as opposed to all ancestor-descendant pairs then you can add a rule like this: Answer(?X) :- ancestor(john,?X). So, at the semantic level, computing the entire Answer relation is the same as asking the query ?- ancestor(john,?X). Since RIF compliance is determined through translations, the above is an acceptable way to handle queries in RIF. --michael > << 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 14:54:07 UTC