W3C home > Mailing lists > Public > public-rif-wg@w3.org > August 2008

Re: safety and external predicates

From: Jos de Bruijn <debruijn@inf.unibz.it>
Date: Thu, 21 Aug 2008 18:25:50 +0200
Message-ID: <48AD970E.3010506@inf.unibz.it>
To: Dave Reynolds <der@hplb.hpl.hp.com>
CC: Chris Welty <cawelty@gmail.com>, "Public-Rif-Wg (E-mail)" <public-rif-wg@w3.org>

<snip/>

> From our point of view I see no reason to demand decidability. It is
> possible to write non-terminating rulesets in Jena through recursive
> calls to externs or through instance creation (c.f. Gary's thread on
> frame axioms). As Chris says, we would treat that as the rule-author's
> problem :-) A static checker that detected problematic rulesets might be
> a useful development aid but in practice I haven't seen many people have
> problems detecting such problems and fixing them in their rules.

Checking whether a rule set is "problematic" is often undecidable :-)

> One way of looking at this is as a conformance issue.
> 
> My inclination would be to define conformance with CORE just in terms of
> ground entailments over rulesets for which those are finite. That way
> both simple production rule implementations and simple LP rule
> implementations can be conformant.

I'm not sure whether I understand the criterion you are proposing.
Which things are "finite"?
if you're thinking of a criterion like "requires a finite number of
steps in the computation", I'm afraid this is not going to work.
Checking whether you need a finite number of steps is in general
undecidable (boils down to the halting problem).

> For a ruleset with unbounded ground entailments a conformant
> implementation would be free to reject it as a result of static safety
> checking, raise a run time error, compute some finite subset or loop
> indefinitely.

So, you propose conformance with respect to a syntactical restriction?

Best, Jos

> 
> We could describe a notion of rule safety in an appendix, e.g. based on
> [2] as Jos and Axel propose. My preference would be to make that
> informative rather than some sort of normative CORE-safe subdialect.
> 
> Dave
> 
> [*] As it stands Jena could not implement all of Core because we only
> operate over RDF (i.e. the Frame syntax) not n-ary predicates.
> 
> Chris Welty wrote:
>>
>>
>> I still am not convinced that safeness is anything more than an
>> academic requirement for CORE.  I would like to hear from someone who
>> is a) interested in CORE and b) has some idea what an implementation
>> is and c) has some idea what users of CORE would need, to let us know
>> if these requirements matter:
>>
>> 1) Decidability: is is important that RIF-Core have decidable
>> reasoning? That is, any compliant RIF-Core reasoner (implementation)
>> will be guaranteed to terminate on any rule-set?
>>
>> 2) If decidability is a requirement, is tractability?  That is, any
>> implementation will terminate in worst-case polynomial time (or better?)
>>
>> My general impression from talking to some potential RIF implementors
>> is that they treat rule-bases like programs - if your programs don't
>> work its your fault, go fix them.  However one important difference
>> between rule/logic "programs" and procedural programs is the amount of
>> control you have over the search strategy.  I think this is (a
>> practical reason) why decidability is considered by some to be
>> important for these languages and not for e.g. Java.
>>
>> -Chris
>>
>> Axel Polleres wrote:
>>>
>>> Two pointers here... the notion of strong safety in hex-programs
>>> [1,2] and Topor's considerations on  safe database queries with
>>> arithmetics [3] (cudos jos for the latter one)
>>>
>>>
>>> 1. R. Schindlauer. Answer-Set Programming for the Semantic Web. PhD
>>> thesis, Vienna University of Technology, Dec. 2006.
>>> http://www.kr.tuwien.ac.at/staff/roman/papers/thesis.pdf
>>>
>>> 2.  Thomas Eiter, Giovambattista Ianni, Roman Schindlauer, and Hans
>>> Tompits. Effective Integration of Declarative Rules with External
>>> Evaluations for Semantic Web Reasoning. In York Sure and John
>>> Domingue, editors, Proceedings of the 3rd European Conference on
>>> Semantic Web (ESWC 2006), Budva, Montenegro, number 4011 in Lecture
>>> Notes in Computer Science (LNCS), pages 273-287. Springer, June 2006.
>>> http://www.springerlink.com/content/f0x23wx142141v44/
>>>
>>> 3. R. Topor. Safe database queries with arithmetic relations (1991)
>>> Proc. 14th Australian Computer Science Conf
>>> http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.4845
>>>
>>>
>>
> 
> 

-- 
Jos de Bruijn            debruijn@inf.unibz.it
+390471016224         http://www.debruijn.net/
----------------------------------------------
No one who cannot rejoice in the discovery of
his own mistakes deserves to be called a
scholar.
  - Donald Foster


Received on Thursday, 21 August 2008 16:25:38 GMT

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