- From: Gary Hallmark <gary.hallmark@oracle.com>
- Date: Thu, 22 Feb 2007 14:13:45 -0800
- To: Michael Kifer <kifer@cs.sunysb.edu>
- CC: "Rule Interchange Format (RIF) Working Group WG" <public-rif-wg@w3.org>
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 Thursday, 22 February 2007 22:12:08 UTC