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

Re: safety and external predicates

From: Axel Polleres <axel.polleres@deri.org>
Date: Thu, 14 Aug 2008 21:06:23 +0100
Message-ID: <48A4903F.5090303@deri.org>
To: kifer@cs.sunysb.edu
CC: Chris Welty <cawelty@gmail.com>, "Public-Rif-Wg (E-mail)" <public-rif-wg@w3.org>

Michael Kifer wrote:
> 
> On Thu, 14 Aug 2008 16:28:54 +0100
> Axel Polleres <axel.polleres@deri.org> wrote:
> 
>> Chris Welty wrote:
>>> I still am not convinced that safeness is anything more than an academic 
>>> requirement for CORE.   
>> Even if my background is academic, let me try to roll up my previous 
>> arguments made so far from what I'd consider an implementation-oriented 
>> viewpoint of CORE.
> 
> <skipping a very informative survey :-)>
> 
> 
> Axel,
> 
> As far as I understand from the overall message, Chris' question was whether
> decidability is an academic issue. Whether it is PR or LP, people do not care.
> 
> Safety is an important issue for implementing special cases, but this was not
> the question.

Micheal,

There was one overall concern in Chris' mail before the two questions:

 >> I still am not convinced that safeness is anything more than an
 >> academic requirement for CORE.

I replied to that one, and hope to have made clear that safeness is not 
an academic issue, since termination or implementability of CORE on 
existing systems certainly are non-academic systems.


As for decidability, let me repeat/refine the question which was also in 
my first reply:

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

Decidability of WHAT exact problem are we after?

- Decidability/Termination of ground entailment of RIF conditions?

    my personal answer: yes, should IMO both be required for CORE.

- Decidability/Termination of non-ground queries of RIF conditions?

    my personal answer: yes, should IMO both be required for CORE.

 > 2) If decidability is a requirement, is tractability?  That is, any
 > implementation will terminate in worst-case polynomial time
 > (or better?)

Depends again: Tractability of what? Plain Datalog has already EXPTIME 
program complexity... you probably don't want to restrict to 
propositional Horn?

best,
Axel


-- 
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 Thursday, 14 August 2008 20:07:09 GMT

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