Final text for Basic Graph Patterns

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

Received on Saturday, 14 January 2006 15:11:23 UTC