RE: completeness

Bijan Parsia wrote:

>BTW, I suspect the most common form of RDFS incompleteness is in  
>BNode handling. Full variables semantics is expensive even in RDF and  
>Pd* (non-ground entailment is NP-complete). When I was working with  
>some folks trying to do RDFS on a rules system, the first ignored  
>thing is the BNode entailment rules ;)

Yes, even the "Full", i.e. the "least incomplete" implementation of Jena's
RDFS reasoner avoids these rules. :) See [10].

>(I would think that ground graphs on the rhs would be sufficient to  
>avoid NP completeness. OTOH, if you treat BNodes as names instead of  
>variables, then all graphs are effectively ground.)

And the pD* paper [20] confirms your assumption: The paper's introduction
explains (and it is later proven) that NP-completeness can already be shown
for Simple Entailment, the smallest semantics which treats bNodes as
existentials. The amazing thing is: It doesn't get worse for RDFS and even
for pD*! It is shown in the paper (though I haven't checked yet) that
entailment checking is NP-complete for pD* in general, but polynomial, if
there are no (existentially interpreted) bNodes in the regarded graphs. 

So, as you say, when bNodes are alternatively seen as (local) names instead
of existentials, then a polytime decision algorithm exists for pD*
entailment. Then, of course, pD* isn't a real RDFS extention anymore. So I
wouldn't spec this, if pD* or a sublanguage is going to be an OWL-Full
fragment. But seeing bNodes as local names may of course become a typical
non-standard restriction in reasoners for this language. And this might even
be mentioned in an informative section of a spec. Just an idea.

>For an excellent paper on RDFS reasoning in the ground setting see:
>	
>http://www2.ing.puc.cl/~jperez/papers/minimal-rdf-camera-ready-ext.pdf

Thanks for the link!

Cheers,
Michael

[10] <http://jena.sourceforge.net/inference/index.html#RDFSconfiguration>
[20] <http://linkinghub.elsevier.com/retrieve/pii/S1570826805000144>

--
Dipl.-Inform. Michael Schneider
FZI Forschungszentrum Informatik Karlsruhe
Abtl. Information Process Engineering (IPE)
Tel  : +49-721-9654-726
Fax  : +49-721-9654-727
Email: Michael.Schneider@fzi.de
Web  : http://www.fzi.de/ipe/eng/mitarbeiter.php?id=555

FZI Forschungszentrum Informatik an der Universität Karlsruhe
Haid-und-Neu-Str. 10-14, D-76131 Karlsruhe
Tel.: +49-721-9654-0, Fax: +49-721-9654-959
Stiftung des bürgerlichen Rechts
Az: 14-0563.1 Regierungspräsidium Karlsruhe
Vorstand: Rüdiger Dillmann, Michael Flor, Jivka Ovtcharova, Rudi Studer
Vorsitzender des Kuratoriums: Ministerialdirigent Günther Leßnerkraus