- From: Chris Welty <cawelty@gmail.com>
- Date: Fri, 23 Feb 2007 08:31:21 -0500
- To: Michael Kifer <kifer@cs.sunysb.edu>
- CC: Gary Hallmark <gary.hallmark@oracle.com>, "Rule Interchange Format (RIF) Working Group WG" <public-rif-wg@w3.org>
Yes, this is my understanding as well. For RIF, we are *less* concerned (but not unconcerned) with execution of the translated rules, and more with the fact that there is a translation. As we left it, it seemed that some meta-data annotation on a ruleset indicating the presence of things that may cause difficulties in execution (like recursion) would be the best way to address this. As I said at a telecon early this year, until we get an example that shows this would not be enough, that's where we'll go. -Chris Michael Kifer wrote: > So the issue is mainly in the execution strategy, not in the > semantics of the queries (as far as the core is concerned). > One can say that some queries are not thinkable in PR because they will be > horribly expensive or even won't terminate, but this is also true of Prolog. > > > --michael > > >> 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/ >>>>>> >>>>>> >>>>>> >>>>>> >>>>>> >>>>>> >>>>>> >>>>>> >>>>>> >>>>>> >>>>> >>>>> >>>>> >>>>> >>>>> >>>>> >>>> >>>> >>> >>> >>> >>> >> > > > > -- Dr. Christopher A. Welty IBM Watson Research Center +1.914.784.7055 19 Skyline Dr. cawelty@gmail.com Hawthorne, NY 10532 http://www.research.ibm.com/people/w/welty
Received on Friday, 23 February 2007 13:31:30 UTC