- From: Paul Vincent <pvincent@tibco.com>
- Date: Mon, 26 Feb 2007 12:34:06 -0800
- To: "Mark Proctor" <mproctor@redhat.com>
- Cc: "Gary Hallmark" <gary.hallmark@Oracle.com>, "Michael Kifer" <kifer@cs.sunysb.edu>, "Rule Interchange Format \(RIF\) Working Group WG" <public-rif-wg@w3.org>
- Message-ID: <8F4A4531BB49A74387A7C99C7D0B0E050223E8CD@NA-PA-VBE02.na.tibco.com>
Mark - correct: you can use a (PR) rule as a query (/a rule's condition as a query language). Of course, you might not want to do this for ad-hoc queries (via "ad-hoc rules"). Round-tripping was just mentioned today at the F2F as an "outstanding issue". So more to be discussed on that! Paul Vincent TIBCO - ETG/Business Rules <http://www.tibco.com/devnet/business_studio/default.jsp> ________________________________ From: Mark Proctor [mailto:mproctor@redhat.com] Sent: 26 February 2007 20:10 To: Paul Vincent Cc: Gary Hallmark; Michael Kifer; Rule Interchange Format (RIF) Working Group WG Subject: Re: ISSUE-28: Recursion in the RIF Core Many production rule systems like jess, jrules, jbossrules support a query facilitiy. A query in a production rule system is simply a rule with a special terminal node that adds all activations to a collection, a special fact is used to trigger the query. JSR94 does not support this type of query, it only supports a simple object type filter. Wouldn't round-tripping of core be a requirement? Mark Paul Vincent wrote: Thanks Gary: I am not a JSR-94 expert (indeed I can only find query references under: 6.5 Stateful Rule Session ... "A stateful rule session allows a client to have a prolonged interaction with a rule execution set. Input objects can be progressively added to the session and output objects can be queried repeatedly.") My problem is simply terminology confusion: I was thinking - "query" referred to something like SQL or SPARQL, as opposed to an object return mechanism, and - "working memory" referred to the internal engine state, not necessarily the objects mapped to Java. But these are moot anyway - "PR systems" (as opposed to languages) can generally handle recursion via functions etc. Of course, I would not want to propose round-tripping of recursive rules from Horn to PR back out again though! Paul Vincent TIBCO - ETG/Business Rules -----Original Message----- From: Gary Hallmark [mailto:gary.hallmark@Oracle.com] Sent: 26 February 2007 17:37 To: Paul Vincent Cc: Michael Kifer; Rule Interchange Format (RIF) Working Group WG Subject: Re: ISSUE-28: Recursion in the RIF Core it's required for JSR-94. I probably should have said, "all PR systems that support JSR-94 have a way to filter working memory after the rules have run" Paul Vincent wrote: << 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> <http://en.wikipedia.org/wiki/Forward_chaining> and backward chaining <http://en.wikipedia.org/wiki/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.htm l 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.htm l -- Dr. Axel Polleres email: axel@polleres.net url: http://www.polleres.net/
Received on Monday, 26 February 2007 20:35:43 UTC