- From: Enrico Franconi <franconi@inf.unibz.it>
- Date: Thu, 5 Jan 2006 18:24:45 +0100
- To: RDF Data Access Working Group <public-rdf-dawg@w3.org>

""" 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 G. By default, entailment here is intended in this document as "simple entailment" (as defined in [RDF-MT]). SPARQL may be extended to provide a way to override the default with "RDF entailment", "RDFS entailment" (as defined in [RDF-MT]), and "OWL entailment" (as defined in [OWL-Semantics]). 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. Implementational hint: Simple Entailment as Subgraph Matching. In the case of simple entailment, a pattern solution can be equivalently (proof in appendix) 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. Moreover, the uniqueness property of pattern solutions (proof in appendix) 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 Thursday, 5 January 2006 17:25:04 UTC