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

Proposed changes by FUB

From: Enrico Franconi <franconi@inf.unibz.it>
Date: Thu, 5 Jan 2006 09:09:00 +0100
Message-Id: <7EE47711-FC7C-4FDC-B18E-376871D653CC@inf.unibz.it>
To: RDF Data Access Working Group <public-rdf-dawg@w3.org>

[I have added an (important) explanatory part at the end]

2.5  Basic Graph Patterns

Definition 4 (RDFMerge)
The RDFmerge 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, if any of the  
graphs contains variables, then those are not renamed (i.e.,  
variables are treated as URIs).

The above RDFmerge definition is totally compatible with the merge  
definition given in [RDF-MT], hereby indicated as simple RDF merge.  
In particular, if the graphs do not contain any variable or they are  
considered simply as IRIs, then RDFmerge is a simple 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 RDFmerge is equivalent to simple 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 entails S(G RDFmerge BGP)
In addition, the bnodes involved in a pattern solution S can only be  
among the bnodes appearing in BGP.
By default, entailment here is intended in this document as "simple  
entailment" (as defined in [RDF-MT]). SPARQL provides a way to  
override the default with "RDF entailment", "RDFS entailment" (as  
defined in [RDF-MT]), and "OWL entailment" (as defined in [OWL- 
The SPARQL syntax uses the keyword WHERE to introduce the Query Pattern.

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 is of course possible by choosing another form of entailment,  
among the current standards of W3C: "RDF entailment", "RDFS  
entailment" (as defined in [RDF-MT]), and "OWL entailment" (as  
defined in [OWL-Semantics]).

We show now that, 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.

Theorem: 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 may be mapped to any node in G, a pattern solution  
is the substitution of variables in BGP to nodes in G.

Moreove, the uniqueness theorem guarantees that the interoperability  
between SPARQL systems.

Theorem. Uniqueness of pattern solutions.
Given a graph G and a basic graph pattern query BGP, the set of all  
the pattern solutions is unique.
Received on Thursday, 5 January 2006 08:09:27 UTC

This archive was generated by hypermail 2.3.1 : Wednesday, 7 January 2015 15:00:50 UTC