W3C home > Mailing lists > Public > public-rif-wg@w3.org > February 2009

Example not-necessarily-terminating rules

From: Dave Reynolds <der@hplb.hpl.hp.com>
Date: Tue, 03 Feb 2009 23:50:55 +0000
Message-ID: <4988D85F.9060004@hplb.hpl.hp.com>
To: RIF WG <public-rif-wg@w3.org>

As Jos pointed out, without a specific definition of 
guaranteed-terminating safeness it is hard to construct a clear cut example.

However, here's a simple example which I believe would fail for any such 
definition.

Length of an RDF list:

    length(rdf:nil, 0).
    length(?list, ?len) :- ?list[rdf:rest->?next],
                           length(?next, ?l), ?len = ?l + 1 .

For well-formed RDF data then lists are linear and finite and this will 
terminate with either a forward or backward chaining proof strategy. RDF 
does not preclude circular lists so it would be possible to construct a 
RIF+RDF combination which would not terminate with this rule set, hence 
no reasonable definition of terminating-safeness would admit this rule 
set. Yet I assert that counting of finite things (e.g. the number of 
items in an invoice, or number of authors on a paper) is a reasonable 
thing to want to do within Core.

Note that the original proposal [1] did not allow for assignment and had 
no distinction between recursive and non-recursive rule sets so in fact 
a simple "business" rule like:

    finalPrice(?x, ?p) :-  price(?x, ?r), discount(?x ?d), ?p = ?r * ?d.

would, I believe, have been unsafe.

Does this help?

Dave

[1] http://lists.w3.org/Archives/Public/public-rif-wg/2008Sep/0178.html
Received on Tuesday, 3 February 2009 23:51:40 GMT

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