Definition: Substitution Function
A substitution function is a mapping from a subset of V, the set of variables, to the set of RDF terms, RDF-T.
The result of replacing every variable v in a graph pattern P by S(v) is written S(P).
Definition: Scoping graph
Given a query Q = (GP, DS, SM, R), the scoping graph DSScope is an RDF graph which is graph-equivalent to DS and shares no blank nodes with GP.
Answers to the query are defined relative to the scoping graph, which is required to be constant for all answers to any query, <<and therefore to share no blank nodes with any graph pattern which is part of the graph pattern of the query>> <<is there any need to say that?>>. The purpose of the scoping graph is to define a common scope for all blank node identifiers in answers, to ensure that all answer bindings in the table of query answers use blank nodes consistently with one another and with the patttern of blank node useage in the dataset. It is not required to generate the scoping graph explictly, only that blank node IDs in the document which records answer bindings are appropriately arranged.
Definition: Pattern Solution
<<I'm not sure how to define this now, since we have to wait until the next section to get to the scoping stuff.>>
Definition: Query Solution
Given query Q = (GP, DS, SM, R) then S is a query solution of Q if S is a pattern solution for GP matching dataset DS.
A pattern is matched against the target graph. In this section, all matching is described for a single graph and basic patterns.
<<And Im not sure what the above means. Why do we need to talk about the target graph at this stage? It all seems to be getting very complicated. Do we need this many distinctions?>>
How exactly a particular graph pattern matches a dataset is described for each kind of graph pattern in the sections below.
For example, the query:
PREFIX dc: <http://purl.org/dc/elements/1.1/>
SELECT ?book ?title
WHERE { ?book dc:title ?title }
has a single triple pattern as the query pattern. It matches
<<Wait: we havnt defined "match" yet, right?>>
a graph of a single triple:
<http://example.org/book/book1> <http://purl.org/dc/elements/1.1/title> "SPARQL" .
with solution:
| ?book | ?title |
|---|---|
| <http://example.org/book/book1> | "SPARQL" |
Basic graph patterns are to RDF graphs as triple patterns are to RDF triples. Basic graph patterns form the basis of SPARQL query matching.
SPARQL query matching on basic graph patterns is defined using simple entailment, the simplest and most basic form of entailment between RDF graphs. Simple entailment by a graph can be checked by matching directly against the structure of the graph itself; nothing that is not already in the graph needs to be inferred or constructed, even implicitly. Extensions to SPARQL may modify this definition by using other forms of entailment and imposing extra restrictions on answer sets, while retaining the essential form of the definition and the rest of the SPARQL constructions: see <<either later section reference or other document>> for details. Such extensions will typically require more elaborate mechanisms in the query engine. Some SPARQL extensions may be identified with SPARQL applied to RDF graphs derived from the dataset graph, such as the RDF or RDFS closures, but not all entailments will be adequately modelled in this way; in particular, OWL entailment from an OWL/RDF graph does not correspond to simple entailment from any natural definable RDF graph. Moreover, although for SPARQL query matching a blank node in a pattern acts just like a 'blank' (un-named) query variable, this may not be true for more elaborate forms of entailment.
<<Ive tried to summarize all the main awkward topics here so that we don't mislead anyone, without getting into too much detail.>>
All basic graph pattern matching in a single SPARQL query request is defined relative to a single scoping graph, referred to as the query scoping graph.
A Basic Graph Pattern is a set of Triple Patterns.
Definition: Pattern Solution
A pattern solution to a query Q = (GP, DS, SM, R) where GP is a basic graph pattern and DSScope is the query scoping graph, is a substitution mapping S such that
1. DS simply entails (DSScope union S(GP))
2. Every blank node in the range of S occurs in the scoping graph DSScope
A pattern solution can be defined alternatively as follows: to match a basic graph pattern, find a mapping from blank nodes and variables in the basic graph pattern to terms in the scoping graph being matched; a pattern solution is then such a mapping restricted to just the variables. It is necessary to use the scoping graph to avoid accidental coincidences between blank node IDs in the scopes of the pattern and the graph.
Given a graph and a basic graph pattern, the set of all the pattern solutions for that graph as dataset is unique up to a re-naming of blank nodes.
As an example of a Basic Graph Pattern:
Data:
@prefix foaf: <http://xmlns.com/foaf/0.1/> . _:a foaf:name "Johnny Lee Outlaw" . _:a foaf:mbox <mailto:outlaw@example.com> . _:b foaf:name "A. N. Other" . _:b foaf:mbox <mailto:other@example.com> .
There is a blank node [CONCEPTS] in this dataset, identified by _:a. The label is only used within the file for encoding purposes, and is considered to be local to the dataset.
Query:
PREFIX foaf: <http://xmlns.com/foaf/0.1/>
SELECT ?mbox
WHERE
{ ?x foaf:name "Johnny Lee Outlaw" .
?x foaf:mbox ?mbox }
Query Result:
| mbox |
|---|
| <mailto:outlaw@example.com> |
This query contains a basic graph pattern of two triple patterns, each of which must match with the same solution for the graph pattern to match. The pattern solution matching the basic graph pattern maps the variable 'x' to blank node _:a and variable 'mbox' to the IRI mailto:outlaw@example.com. The query only returns the variable'mbox'.
Basic Graph Patterns are delimited by {} in the SPARQL syntax and are not separated by value constraints. The two query fragments below each contain the same basic graph pattern of { _:x :p ?v . _:x :q ?w . } defining the scope of the blank node label.
{ _:x :p ?v .
FILTER (?v < 3) .
_:x :q ?w .
}
{ _:x :p ?v .
_:x :q ?w .
FILTER (?v < 3) .
}