Re: safety and external predicates

Dave Reynolds wrote:
> 
> 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?

Makes sense for me. A notion of safety would overestimate your 
criterion, indeed, i.e. be a sufficient  but not necessary condition for 
termination, which is statically checkable, so making the language 
statically checkable. That was why I am personally in favor of it, but I 
can live without it if someone tells me what the "exepected ansers" for 
ground entailments on possibly non-terminating rulesets should be, see 
my proposed integer conformance tests.

cheers,
Axel





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


-- 
Dr. Axel Polleres, Digital Enterprise Research Institute (DERI)
email: axel.polleres@deri.org  url: http://www.polleres.net/

Everything is possible:
rdfs:subClassOf rdfs:subPropertyOf rdfs:Resource.
rdfs:subClassOf rdfs:subPropertyOf rdfs:subPropertyOf.
rdf:type rdfs:subPropertyOf rdfs:subClassOf.
rdfs:subClassOf rdf:type owl:SymmetricProperty.

Received on Friday, 22 August 2008 16:22:25 UTC