Re: completeness

On 22 Feb 2008, at 10:21, Michael Schneider wrote:
[snip]
> 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.

I suspect that there might be a change in the data complexity (or  
RDF's data complexity is worse than I feared). NP complete combined  
complexity isn't nearly as troublesome as NP complete data complexity  
(esp. for scalable query answering).

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

Why not? I point to the HTML5 design principles document (which  
contains, I think, useful advice):
	http://www.w3.org/TR/html-design-principles/#priority-of-constituencies
Fidelity to prior specs is *much* less important that actually  
describing what implementors will do.

Oh, "as an OWL-Full fragment". Well, it's still a fragment of OWL- 
Full in the sense of having "if" and not "iff" semantics in pretty  
much the way Pd* does for other constructs.

> But seeing bNodes as local names may of course become a typical
> non-standard restriction in reasoners for this language.

"Typical non-standard" seems like a "spec smell" to me. If it's  
typical, let's standardize it. In fact, this is more than typical:  
It's ubiquitous.

> And this might even
> be mentioned in an informative section of a spec. Just an idea.
[snip]

Though some people have tried to cast me otherwise, I'm really  
eminently pragmatic: I prefer whatever it takes to make specs clear  
and useful. I also prioritize clarity over general accessibility,  
since the people who make the effort to understand can explain it to  
others. But if the spec is unclear or ambiguous, then no one can  
settle disputes. Similarly, specing things which no one implements is  
a waste of time and can lower the perceived value of the spec (and  
thus implementor efforts to adhere to the spec).

So I would put it the other way around: If what implementations need  
and users want is bnodes as names, let's make *that* the specced  
version. One can always provide informative text telling people how  
it connects to OWL Full's semantics. However, I don't care, though I  
strongly recommend against, making that bit normative as well as long  
as implementations can clearly opt out of the part that they will opt  
out of anyway.

(Note, in the DAWG, many people, esp. the HP rep, strongly resisted  
any of my attempts to introduce a version of "DISTINCT" that would  
have involved treating BNodes as variables, i.e., leaning the result  
table. I personally think that without that, BNodes will never be  
variables in any widespread system and leaning will be just be seen  
as a special operation one can (with care) perform on graphs. The  
argument was purely implementational: The cost of leaning is high;  
leaning results interferes with streaming; no system implemented  
REALLYREALLYDISTINCT nor was likely to.)

Cheers,
Bijan.

Received on Friday, 22 February 2008 10:48:20 UTC