W3C home > Mailing lists > Public > public-rule-workshop-discuss@w3.org > February 2006

Re: [RIF] backward vs forward chaining [was some other subject]

From: Adrian Walker <adrianw@snet.net>
Date: Thu, 02 Feb 2006 10:16:26 -0500
Message-Id: <5.0.2.1.2.20060202100031.02dfed90@pop.snet.net>
To: Francois Bry <bry@ifi.lmu.de>
Cc: public-rule-workshop-discuss@w3.org

Bonjour Francois and All --

Good to see that the backward and forward debate continues... (:-)

It's been known for quite a while that one can get the best of both worlds, 
_and_ a more declarative treatment of the rules, by combining both methods 
automatically in one engine.

Backchaining then keeps the focus on results (and in future, on web data 
items) that are actually needed, while forward chaining with asserted 
lemmas stops the engine from deriving the same sub-result more than once.

XSB takes a step in this direction, with 'tabling'.  Magic Sets, and 
Backchain Iteration [1],  exploit the approach more fully**.

                       Cheers,   -- Adrian


[1] Backchain Iteration: Towards a Practical Inference Method that is 
Simple Enough to be Proved Terminating, Sound and Complete. Journal of 
Automated Reasoning, 11:1-22.

** I'm guessing that Euler does this too. Right Jos ?



Internet Business Logic (R)
Executable open vocabulary English
Online at www.reengineeringllc.com
Shared use is free

Adrian Walker
Reengineering
PO Box 1412
Bristol
CT 06011-1412 USA

Phone: USA 860 583 9677
Cell:    USA  860 830 2085
Fax:    USA  860 314 1029



At 03:02 PM 2/2/2006 +0100, you wrote:

>Peter F. Patel-Schneider wrote:
>
>>From: Francois Bry <bry@ifi.lmu.de>
>>Date: Thu, 02 Feb 2006 08:51:58 +0100
>>
>>
>>
>>>Peter F. Patel-Schneider wrote:
>>>
>>>
>>>
>>>>From: Michael Kifer <kifer@cs.sunysb.edu>
>>>>Date: Wed, 01 Feb 2006 15:03:06 -0500
>>>>
>>>>
>>>>
>>>>>Francois Bry <bry@ifi.lmu.de> wrote:
>>>>>
>>>>>
>>>>>
>>>>>>I agree that RIF should have (1) a clear declarative semantics and 
>>>>>>(2) in addition support conveying *some* *limited* specifications of 
>>>>>>procedural semantics (eg backward chaining is intended because with 
>>>>>>forward chaining the considered rules would require to process 
>>>>>>all/too many nodes on the Web).
>>>>>>
>>>>>>
>>>>>I disagree with that, especially with the statement that "with forward
>>>>>chaining the considered rules would require to process all/too many nodes
>>>>>on the Web".
>>>>>
>>>>+[some very large number]
>>>>
>>>>What makes "forward chaining" a particularly bad method, even if you 
>>>>think of
>>>>forward chaining as a way to perform saturation?  Forward chaining 
>>>>(including
>>>>saturation, or not) works exceedingly well in some situations (and 
>>>>exceedingly
>>>>poorly in others).  Standard backward chaining has exactly the same
>>>>characteristics, by the way.  It all depends on the situation, and the
>>>>parameters used to control the chaining.
>>>>
>>>>
>>>My point was that forward chaining inherently requires to start 
>>>computing from all web sites that might be involved. Either those web 
>>>sites are known and limited in number -- and this is fine -- or not -- 
>>>and forward chaining is impracticable.
>>>
>>>-- Francois
>>>
>>
>>I don't follow this.  Why would anyone want to start with "all web sites that
>>might be involved"?  This seems to be a recipe for disaster no matter what
>>reasoning methodology is used.
>>
>>In any case, what is it about "forward chaining" that requires this universal
>>reach more than any other evaluation methodology?  Couldn't I just say 
>>the same
>>thing about "backward chaining"?  What makes
>>
>>         My point was that backward chaining inherently requires to start
>>         computing from all web sites that might be involved.
>>
>>any less true than what you said?
>>
>>Peter F. Patel-Schneider
>>
>Think of rule specifying interesting web pages as follows, with
>
>interesting(A) :- computer-science(A).
>interesting(A) :- link(A, B), interesting(B).
>
>meaning, a web page ist interesting if it has a Computer Science content 
>or a link to an "interesting" page.
>
>Assume one asks whether www.example.ex is interesting. With backward 
>chaining, the evaluation starts with the query 
>"interesting(www.example.ex)" and propagate backwards the binding,yielding 
>the intermediate queries:
>
>link(www.example.ex, B), interesting(B)
>interesting(www.mycom.com) if A has a link to www.mycom.com
>etc.
>
>With forwards chaining, the evaluation starts with the queries
>"computer-science(A)"  ie checking all web pages for Computer Science 
>content, then following the links from all web page with CS contents, etc.
>
>Thus, backward or forward chaining make a difference, as far as the number 
>of pages accessed is concerned.
>
>Francois
>
>
Received on Thursday, 2 February 2006 15:16:51 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Tuesday, 8 January 2008 14:16:23 GMT