Re: [Fwd: Comments on SPARQL] (entailment, soundness, completeness)

On Sep 20, 2005, at 9:31 AM, Seaborne, Andy wrote:

> Bijan Parsia wrote:
>> On Sep 20, 2005, at 7:04 AM, Dan Connolly wrote:
>> [snip]
>>> Enrico, elsewhere in your message about "Adoption of entailment in  
>>> SPARQL"
>>> of September 19, 2005 11:55:09 PM GMT+01:00, you wrote "here we don't
>>> argue whether this is useful and how this is going to be used." Note  
>>> that I
>>> pretty much stopped reading at that point.
>> I think you were mislead by Enrico's words there. There are plenty of  
>> places in that note that he appeals to existing, documented SPARQL  
>> use cases to motivate his technical points, e.g.,
>> """ON REDUNDANCY OF TOLD BNODES IN ANSWERS
>> [issue <http://www.w3.org/2001/sw/DataAccess/issues#rdfSemantics>]
>> """
>> Should queries of non-lean and lean graphs that entail each other
>> give the same answers?
>> """
>> The answer to this question should be *yes*. See use case 1,
>> "Publishing on the Web", in
>> <http://lists.w3.org/Archives/Public/public-rdf-dawg/2005JulSep/ 
>> 0430>).
>> This is also relevant, as noted by PFPS, to enable interoperability
>> between different interoperating implementations of RDF."""
>
> The quoted email has two use cases - the same query is used on the  
> same data in two separate situations.

Yes.

>  The desired results are then different.

Yes.

> I can't tell if the proposed formulation reflects this or not

Do you mean the underlying semantics proposed in part A?

I'm going to presume so. If you look at the definition:

"""Definition: Entailment Matching
	A basic graph pattern GP matches on graph G with solution S if
	S(GP) is an RDF graph and is entailed by G."""

The idea (conceptually) is that you *test* substitutions by seeing if  
substituting into the GP results in an entailed graph. If you want  
non-redundant answers, i.e., that RDF graphs which rdf entail each  
other return isomorphic answers, then just replace RDF-entailed for  
entailed (and then worry about minimality of answers).

Of course this *does not* reflect most current implementations, afaict,  
*and* misses some important use cases we've discussed. What's wanted is  
that answers based on redundant *asserted* information show up in the  
result set. The trick is to keep the above definition (with minimality)  
*but* to skolemize the original graph:

""" We can show that the only bnodes that will appear in
the answer will be the ones coming through the skolemisation
process. Therefore, the definition of Pattern Solution
<http://www.w3.org/TR/rdf-sparql-query/#PatternSolutions> should be
changed to disallow the use of bnodes in the substitution:

         A pattern solution is a substitution function from a subset of
         the set of variables to the set of the IRIs and RDF Literals.

In other words, we say that a solution S is a substitution of the
variables in a query with only IRIs and literals, and it is in the
solution set of a query GP to a graph G iff there exists a S' such
that
SK(G)  entails  S'(GP),       and       S = UNSK(S'(GP)),
where SK is a skolemisation operation of the bnodes, and UNSK is its
inverse (giving back the bnode names to the skolem constants)."""

In an implemention with not entailment, the skolem constants can just  
be the gensyms or whatever the implementations are using to represent  
BNodes in the first place.

>  - at the moment, I don't see any place where this is acknowledged.   
> Could someone kindly point such a place out to me, please?

Does this help?

Cheers,
Bijan.

Received on Tuesday, 20 September 2005 13:56:33 UTC