This definition allows the solution mapping to bind a variable in a basic graph pattern, BGP, to a blank node in G. Since SPARQL treats blank node identifiers in a results format document (SPARQL Query Results XML Format, SPARQL 1.1 Query Results JSON Format and SPARQL 1.1 Query Results CSV and TSV Formats) as scoped to the document, they cannot be understood as identifying nodes in the active graph of the dataset. If DS is the dataset of a query, pattern solutions are therefore understood to be not from the active graph of DS itself, but from an RDF graph, called the scoping graph, which is graph-equivalent to the active graph of DS but shares no blank nodes with DS or with BGP. The same scoping graph is used for all solutions to a single query. The scoping graph is purely a theoretical construct; in practice, the effect is obtained simply by the document scope conventions for blank node identifiers.
\nSince RDF blank nodes allow infinitely many redundant solutions for many patterns, there can be infinitely many pattern solutions (obtained by replacing blank nodes by different blank nodes). It is necessary, therefore, to somehow delimit the solutions for a basic graph pattern. SPARQL uses the subgraph match criterion to determine the solutions of a basic graph pattern. There is one solution for each distinct pattern instance mapping from the basic graph pattern to a subset of the active graph.
\nThis is optimized for ease of computation rather than redundancy elimination. It allows query results to contain redundancies even when the active graph of the dataset is lean, and it allows logically equivalent datasets to yield different query results.
A basic graph pattern is matched against the active graph for that part of the query. Basic graph patterns can be instantiated by replacing both variables and blank nodes by terms, giving two notions of instance. Blank nodes are replaced using an RDF instance mapping, σ, from blank nodes to RDF terms; variables are replaced by a solution mapping from query variables to RDF terms.
\nDefinition: Pattern Instance MappingA Pattern Instance Mapping, P, is the combination of an RDF instance mapping, σ, and solution mapping, μ. P(x) = μ(σ(x))
\nFor a BGP 'x', P(x) denotes the result of replacing blank nodes b in x for which σ is defined with σ(b) and all variables v in x for which μ is defined with μ(v).
\nAny pattern instance mapping defines a unique solution mapping and a unique RDF instance mapping obtained by restricting it to query variables and blank nodes respectively.
\nDefinition: Basic Graph Pattern MatchingLet BGP be a basic graph pattern and let G be an RDF graph.
\nμ is a solution for BGP from G when there is a pattern instance mapping P such that P(BGP) is a subgraph of G and μ is the restriction of P to the query variables in BGP.
\n\nIf a basic graph pattern is the empty set, then the solution is Ω0.
When matching graph patterns, the possible solutions form a multiset [ Multiset], also known as a bag. A multiset is an unordered collection of elements in which each element may appear more than once. It is described by a set of elements and a cardinality function giving the number of occurrences of each element from the set in the multiset.
\nWrite μ for solution mappings.
\nWrite μ0 for the mapping such that dom(μ0) is the empty set.
\nWrite Ω0 for the multiset consisting of exactly the empty mapping μ0, with cardinality 1. This is the join identity.
\nWrite μ(x) for the solution mapping variable x to RDF term t : { (x, t) }
\nWrite Ω(x) for the multiset consisting of exactly μ(?x->t), that is, { { (x, t) } } with cardinality 1.
\nDefinition: Compatible MappingsTwo solution mappings μ1 and μ2 are compatible if, for every variable v in dom(μ1) and in dom(μ2), μ1(v) = μ2(v).
\nHere, μ1(v) = μ2(v) means that μ1(v) and μ2(v) are the same RDF term.
\nIf μ1 and μ2 are compatible then μ1 ∪ μ2 is also a mapping. Write merge(μ1, μ2) for μ1 ∪ μ2
\nWrite cardΩ for the cardinality of solution mapping μ in a multiset of mappings Ω.