W3C home > Mailing lists > Public > public-rdf-dawg@w3.org > January to March 2006

Re: Final text for Basic Graph Patterns

From: Dan Connolly <connolly@w3.org>
Date: Sat, 14 Jan 2006 19:51:40 -0600
To: Enrico Franconi <franconi@inf.unibz.it>
Cc: RDF Data Access Working Group <public-rdf-dawg@w3.org>
Message-Id: <1137289900.4991.93.camel@dirk.w3.org>

On Sat, 2006-01-14 at 16:11 +0100, Enrico Franconi wrote:
> Hi,
> we ask to finalise the text of Section 2.5.
> 
> The new proposal of Pat <http://lists.w3.org/Archives/Public/public- 
> rdf-dawg/2006JanMar/0061.html> does not work for any approach where  
> bnodes are implicit, and this happens not only for OWL-Lite  
> entailment, as we already pointed out in <http://lists.w3.org/ 
> Archives/Public/public-rdf-dawg/2006JanMar/0064.html>, but also for  
> RDF entailment. For example, given the graph
>      :john :age "25"^^xsd:decimal .
> the query
>      ASK { _:b rdf:type rdf:XMLLiteral }
> should clearly return YES if RDF entailment is considered. However,  
> according to the latest proposal from Pat the answer to the query  
> would be NO regardless of the type of entailment considered.

I thought we were approaching consensus on having just one
kind of entailment in this first version of SPARQL. Did something
change?

>  The  
> reason is that Pat considers bnodes in the query restricted to be  
> bound only to URIs and bnodes explicitly appearing in the graph.
> 
> At this point it is becoming too late. We ask that either our text is  
> used (with possible editorial changes to discuss), or that the DAWG  
> does not conclude the work on the 31st of January and we'll have a  
> F2F during the W3C tech plenary in France at the end of February.
> We recall that our text provides the use of entailment, the  
> correspondence with the subgraph matching based implementations, and  
> uniqueness of solutions for interoperability; its core definitions  
> are stable since its appearance on the 2nd of November 2005 <http:// 
> www.inf.unibz.it/krdb/w3c/sparql/>.
> 
> So, the latest version of our proposed text for Section 2.5 (having  
> minor changes wrt our previous proposal <http://lists.w3.org/Archives/ 
> Public/public-rdf-dawg/2006JanMar/0018>) is below.
> 
> 
> """
> 2.5  Basic Graph Patterns
> 
> Definition 4 (OrderedMerge)
> The OrderedMerge of a sequence of graphs is the ordered merge-union  
> of the graphs, where repeated bnodes are substituted with fresh ones,  
> by keeping the names of the bnodes coming first in the sequence  
> order. Note that, w.r.t. the standard definition of RDF merge [RDF- 
> MT], if any of the graphs contains variables, then those are not  
> renamed (i.e., variables are treated as URIs).
> 
> The above OrderedMerge definition is totally compatible with the RDF  
> merge definition given in [RDF-MT]. In particular, if the graphs do  
> not contain any variable or they are considered simply as IRIs, then  
> OrderedMerge is a RDF merge. The other way around is not true in  
> general, since the original definition does not specify which bnodes  
> are renamed. From the semantic point of view OrderedMerge is  
> equivalent to RDF merge; moreover, if the graphs do not share any  
> bnode name, then the two results are ´syntactically¡ identical, in  
> the sense that they contain the same triples.
> 
> Definition: Basic Graph Pattern matching.
> A Basic Graph Pattern is a set of Triple Patterns.
> A basic graph pattern, BGP, matches on graph G with pattern solution  
> S if:
>      - G  simply entails  S( G OrderedMerge BGP )
>      - the graph S( G OrderedMerge BGP ) is an RDF graph
>      - the bnodes involved in S are among the bnodes appearing in G.
> 
> Simple entailment (as defined in [RDF-MT]) is the default choice of  
> entailment in SPARQL, since it allows for the basic operation of  
> querying the "syntax" of RDF graphs, completely neglecting its  
> semantics. In this way, the basic option for SPARQL is to manipulate  
> graphs, rather than involving reasoning on knowledge bases; the  
> latter may be possible by choosing another form of entailment, among  
> the current standards of W3C. In fact, with the proviso that bnodes  
> are not allowed to appear in pattern solutions, SPARQL may be  
> extended to provide a way to override the default "simple entailment"  
> with "RDF entailment", "RDFS entailment" (as defined in [RDF-MT]),  
> and "OWL entailment" (as defined in [OWL-Semantics], where the  
> syntactic restrictions in OWL-DL or OWL-Lite should be reflected in  
> suitable syntactic restrictions on the form of basic graph patterns).
> 
> In the default case of simple entailment, Basic Graph Pattern  
> matching corresponds really to the expected operation of subgraph  
> matching from the basic graph pattern (the query) to the graph (the  
> dataset). So, querying a dataset with a basic graph pattern  
> corresponds to find all the assignments for variables and bnodes in  
> the query pattern such that the resulting graph is a subgraph of the  
> dataset. This provides a connection for the formal definition of  
> basic graph pattern matching to the practices adopted in SPARQL  
> implementations.
> 
> Implementational hint: Simple Entailment as Subgraph Matching.
> In the case of simple entailment, a pattern solution can be  
> equivalently defined as follows: for each subgraph matching between  
> BGP and G, where bnodes and variables in BGP are mapped to any node  
> in G, a pattern solution is the mapping of variables in BGP to nodes  
> in G.
> 
> Moreover, the uniqueness property of pattern solutions guarantees the  
> interoperability between SPARQL systems: given a graph G and a basic  
> graph pattern query BGP, the set of all the pattern solutions is unique.
> """
-- 
Dan Connolly, W3C http://www.w3.org/People/Connolly/
D3C2 887B 0F92 6005 C541  0875 0F91 96DE 6E52 C29E
Received on Sunday, 15 January 2006 01:51:45 GMT

This archive was generated by hypermail 2.3.1 : Tuesday, 26 March 2013 16:15:25 GMT