Re: safety and external predicates

Jos de Bruijn wrote:
> <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 :-)

Quite.

>> 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.

It's not a proposal yet, just exploring a direction.

> Which things are "finite"?

The set of ground entailments.

> 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).

Agreed.

>> 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?

I'm suggesting that Document Conformance should be unrestricted. That 
Core be undecideable and that rulesets which might not terminate under 
some execution strategies would be legal Core rulesets.  That a 
Conformant Producer should be free to emit such rulesets (so long as the 
semantics of the original ruleset is preserved, as normal).

But that we allow a Consumer to be conformant even if it only preserves 
semantics of some subset of legal rulesets so that it is possible for a 
range of existing PR and LP engines to be conformant consumers even 
though some legal RIF Core rulesets would, for example, lead to 
non-termination with a forward execution strategy. If preferred we could 
call this "minimally conformant", a term used in other W3C specs.

The question is how to define that subset.

It was thinking (perhaps incorrectly) that the notion of a Core rule set 
having a finite set of ground entailments is a well defined(definable) 
one, even though there can be no algorithm for detecting that. So that 
could be the basis for a conformance statement.

Alternatively we could pick a syntactic safety constraint as you and 
Axel have proposed. However, under this scheme we would be using that 
safety constraint only to limit conformance, not to constrain the 
language - there would be no requirement for a translator (producer or 
consumer) to implement that safety check and explicitly detect unsafe 
rulesets.

Does that make sense at least?

Dave

> 
> 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
>>>>
>>>>
>>
>

Received on Friday, 22 August 2008 14:10:13 UTC