Re: SPARQL transitive closure discussion

Hi,
  my understanding is, I think, similar to James', in that the 
discussion in the thread that Satya mentioned is about the notion of 
"logical" answer to a query, which I agree with Pat does not make sense 
as the notion of transitivity is not part of RDF.  Pat's perspective is 
that if you wanted to express properties such as transitivity, then you 
should use a language that allows you to do so, i.e., OWL. That's fine.  
One could perhaps argue that  adding the ability to express transitivity 
to RDF itself could be a good thing, although I don't grasp these 
semantic models well enough to fully understand the boundaries between 
RDF, RDFs, and the various OWL flavours.
   However, I think transitivity properties are not the point here. It 
seems to me that reachability queries can operate on RDF graphs without 
the need explicit transitivity properties on the edges (or any other 
properties), as I believe James points out. I rather wonder, wouldn't it 
make sense to have a closure operator "*" in SPARQL, so that for example 
the pattern
   ?x  p*  ?y
would match all pairs (?x,?y) such that ?x p ?y, or ?x p ?z, and ?z p* 
?y for some ?z.
If this reminds people of Datalog, it's no coincidence. In Datalog 
relations have no special semantics -- you can't say "p is transitive", 
but the language and the computational model support recursive queries.

In other words (and this may show the limits of my understanding of the 
design choices behind SPARQL):   currently SPARQL and SQL are 
essentially equivalent [1]. Whu couldn't SPARQL be similar to Datalog 
instead?

(and this requires no extension to RDF, BTW)

-Paolo

[1] J. Perez, M. Arenas, and C. Gutierrez, "Semantics and complexity of 
SPARQL," ACM Transactions on Database Systems, vol. 34, 2009, pp. 1-45.

James Cheney wrote:
> Hi,
>
> I'm having trouble understanding the issue under discussion in the 
> linked thread.
>
> I thought the point raised on Friday was that SPARQL lacks the ability 
> to say "follow an edge zero or more times", which is needed for 
> provenance queries.
>
> As I understand it (i.e., not very well), SPARQL allows queries based 
> on graph patterns, which are close to what database people call 
> conjunctive queries (with some extensions, such as optional steps). 
>  Such queries cannot perform transitive closure queries such as 
> reachability in a graph.
>
> Does it make sense to have a query language that can take a directed 
> graph and calculate the reachability relation on that graph?  This is 
> conceptually no problem, and this is what transitive closure in some 
> flavors of SQL allows you to do.  I see no reason why RDF would have 
> to be changed to allow this in a query language such as SPARQL.  And I 
> think this is what would be needed for querying provenance.
>
> However, the discussion in the thread you linked to seems to be about 
> something else:
>
> Does it make sense to have a query language that returns graphs whose 
> edges have (implicit) semantics "this edge is transitive", when the 
> underlying graph model does not have such edges?  I think this is what 
> Pat Hayes was arguing against in the thread; while I agree this is 
> potentially confusing, it doesn't seem relevant to the kind of 
> transitive queries needed for provenance.
>
> But this is based on < 15 minutes of thinking.  So maybe I'm missing 
> something.
>
> --James
>
>
> On Mar 19, 2010, at 4:11 PM, Satya Sahoo wrote:
>
>> Hi,
>> The link to discussion thread on SPARQL transitive closure: 
>> http://lists.w3.org/Archives/Public/public-swbp-wg/2005Dec/0036.html
>>  
>> Thanks.
>>  
>> Satya
>>  
>> Kno.e.sis Center
>> http://knoesis.wright.edu/researchers/satya
>