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

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

From: Francois Bry <bry@ifi.lmu.de>
Date: Thu, 02 Feb 2006 15:02:49 +0100
Message-ID: <43E21109.5050708@ifi.lmu.de>
To: public-rule-workshop-discuss@w3.org

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 14:02:54 GMT

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