From: Boley, Harold <Harold.Boley@nrc-cnrc.gc.ca>

Date: Tue, 12 Dec 2006 15:59:20 -0500

Message-ID: <E4D07AB09F5F044299333C8D0FEB45E902F6D09C@nrccenexb1.nrc.ca>

To: "Gary Hallmark" <gary.hallmark@oracle.com>, "W3C RIF WG" <public-rif-wg@w3.org>

Date: Tue, 12 Dec 2006 15:59:20 -0500

Message-ID: <E4D07AB09F5F044299333C8D0FEB45E902F6D09C@nrccenexb1.nrc.ca>

To: "Gary Hallmark" <gary.hallmark@oracle.com>, "W3C RIF WG" <public-rif-wg@w3.org>

> AFAIK, a complete solution is at least a research problem. Related issues have been studied using "magic set" transformations: http://www.informatik.uni-trier.de/~ley/db/conf/pods/MumickFPR90.html http://www.sigmod.org/sigmod/pods/proc03/online/105-behrend.pdf http://www.cs.bris.ac.uk/~john/transformation.html http://indalog.ual.es/Xindalog/documentacion/transf_xindalog.html . . . -- Harold -----Original Message----- From: public-rif-wg-request@w3.org [mailto:public-rif-wg-request@w3.org] On Behalf Of Gary Hallmark Sent: Tuesday, December 12, 2006 4:17 PM To: W3C RIF WG Subject: [TED] Action-188, ISSUE: production rule systems have "difficulty" with recursive rules in RIF Core Production rule systems based on the rete algorithm (http://en.wikipedia.org/wiki/Rete_algorithm) have a procedural semantics characterized by forward chaining (http://en.wikipedia.org/wiki/Forward_chaining). The inference engine fires rules whose conditions match data ("facts") in working memory. The rules may add facts or otherwise modify working memory, which may cause additional rules to fire, etc. 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: Consider the 2 RIF Core rules below that define factorial (on non-negative integers). We assume a built in successor function "succ" and multiply function "mult". factorial(0 1) factorial(?in ?out) :- factorial(?x ?y) & And(?in = succ(?x) ?out = mult(?in ?y)) A naive translation from RIF Core to a "generic" production rule language might produce the following: assert(factorial(0, 1)) IF factorial(?x, ?y) THEN assert(factorial(?x + 1, (?x + 1) * ?y)) The problem with the naive translation is it will generate *all* factorial facts: factorial(1 1) factorial(2 2) factorial(3 6) factorial(4 24) factorial(5 120) ...etc.... until memory is exhausted. In other words, the naive translation using forward chaining is not "goal directed". In contrast, a backward chaining implementation would start with a query such as: :- factorial(4 ?out) and may terminate after generating subgoals factorial(3 ?), factorial(2 ?), and factorial(1 ?). One technique to make production rule systems more goal-directed is to explicitly represent subgoals as facts. Jess and Haley (and probably others) PR systems even have some special syntax to make this a bit easier, but it is by no means hidden from the rule author. To illustrate the technique, we could translate the factorial rules (and the query) from RIF Core to our "generic" PR language as follows: // translation of rules assert(factorial(0, 1)) IF need_factorial(?x) and not(factorial(?x, ?)) and not(factorial(?x - 1, ?)) THEN assert(need_factorial(?x -1)) IF need_factorial(?x) and factorial(?x - 1, ?y) THEN assert(factorial(?x, ?x * ?y)) // translation of query assert(need_factorial(4)) IF factorial(4, ?out) THEN print("factorial of 4 is " ?out) The above translation has some deficiencies, however. - The translation doesn't work for queries like :- factorial(?in, 24) - The need_factorial subgoals are never removed from working memory. - More complex rules involving mutual recursion, double recursion, etc. are, well, more complex... AFAIK, a complete solution is at least a research problem.Received on Tuesday, 12 December 2006 20:59:36 GMT

*
This archive was generated by hypermail 2.2.0+W3C-0.50
: Tuesday, 2 June 2009 18:33:34 GMT
*