SPARQL 1.1 Query Language

18.2.1 Variable Scope

We define a variable to be in-scope if there is a way for a variable to be in the domain of a solution mapping at that point in the execution of the SPARQL algebra for the query. The definition below provides a way of determing this from the abstract syntax of a query.

Note that a subquery with a projection can hide variables; use of a variable in FILTER, or in MINUS does not cause a variable to be in-scope outside of those forms.

Let P, P1, P2 be graph patterns and E, E1,...En be expressions. A variable v is in-scope if:

The variable v must not be in-scope at the point of the (expr AS v) form. The scoping for (expr AS v) applies immediately in SELECT expressions.

In BIND (expr AS v) requires that the variable v is not in-scope from the preceeding elements in the group graph pattern in which it is used.

In SELECT, the variable v must not be in-scope in the graph pattern of the SELECT clause, nor used in another select expression earlier in the clause.

18.2.2 Converting Graph Patterns

This section describes the process for translating a SPARQL graph pattern into a SPARQL algebra expression. This process is applied to the group graph pattern (the unit between {...} delimiters) forming the WHERE clause of a query, and recursively to each syntactic element within the group graph pattern. The result of the translation is a SPARQL algebra expression.

In summary, the steps are applied as follows:

We write

translate(graph pattern)

for the algorthm described here to translate graph patterns.

OPTIONAL { { ... FILTER ( ... ?x ... ) } }..

Applying the simpification step after all the translation of graph patterns is the preferred reading.

Let FS := empty set

For each form FILTER(expr) in the group graph pattern:
    In expr, replace NOT EXISTS{P} with fn:not(exists(translate(P))) 
    In expr, replace EXISTS{P} with exists(translate(P))
    FS := FS ∪ {expr}
    End

Let A := undefined
          
For each element G in the GroupOrUnionGraphPattern
    If A is undefined
        A := Translate(G)
    Else
        A := Union(A, Translate(G))
    End

The result is A
            

If the form is GRAPH IRI GroupGraphPattern
    The result is Graph(IRI, Translate(GroupGraphPattern))

If the form is GRAPH Var GroupGraphPattern
    The result is Graph(Var, Translate(GroupGraphPattern))

Let FS := the empty set
Let G := the empty pattern, a basic graph pattern which is the empty set.

For each element E in the GroupGraphPattern

    If E is of the form OPTIONAL{P} 
        Let A := Translate(P)
        If A is of the form Filter(F, A2)
            G := LeftJoin(G, A2, F)
        Else 
            G := LeftJoin(G, A, true)
            End
        End

    If E is of the form MINUS{P}
        G := Minus(G, Translate(P))
        End

    If E is of the form BIND(expr AS var)
        G := Extend(G, var, expr)
        End

    If E is any other form 
        Let A := Translate(E)
        G := Join(G, A)
        End

   End
   
The result is G.
            

The result is a multiset of solution mappings 'data'.

The result is ToMultiset(Translate(SubSelect))

If FS is not empty
    Let G := output of preceding step
    Let X := Conjunction of expressions in FS
    G := Filter(X, G)
    End

Replace join(Z, A) by A
Replace join(A, Z) by A

18.2.3 Examples of Mapped Graph Patterns

The second form of a rewrite example is the first with empty group joins removed by the simplification step.

Example: group with a basic graph pattern consisting of a single triple pattern:

Example: group with a basic graph pattern consisting of two triple patterns:

Example: group consisting of a union of two basic graph patterns:

Example: group consisting of a union of a union and a basic graph pattern:

Example: group consisting of a basic graph pattern and an optional graph pattern:

Example: group consisting of a basic graph pattern and two optional graph patterns:

Example: group consisting of a basic graph pattern and an optional graph pattern with a filter:

Example: group consisting of a union graph pattern and an optional graph pattern:

Example: group consisting of a basic graph pattern, a filter and an optional graph pattern:

Example: Pattern involving BIND:

Example: Pattern involving BIND:

Example: Pattern involving MINUS:

Example: Pattern involving a subquery:

18.2.4 Converting Groups, Aggregates, HAVING, final VALUES clause and SELECT Expressions

In this step, we process clauses on the query level in the following order:

• Grouping
• Aggregates
• HAVING
• VALUES
• Select expressions

Let A := the empty sequence
Let Q := the query level being evaluated
Let P := the algebra translation of the GroupGraphPattern of the query level
Let E := [], a list of pairs of the form (variable, expression)

If Q contains GROUP BY exprlist
   Let G := Group(exprlist, P)
Else If Q contains an aggregate in SELECT, HAVING, ORDER BY
   Let G := Group((1), P)
Else
   skip the rest of the aggregate step
   End

Global i := 1   # Initially 1 for each query processed

For each (X AS Var) in SELECT, each HAVING(X), and each ORDER BY X in Q
  For each unaggregated variable V in X
      Replace V with Sample(V)
      End
  For each aggregate R(args ; scalarvals) now in X
      # note scalarvals may be omitted, then it's equivalent to the empty set
      Ai := Aggregation(args, R, scalarvals, G)
      Replace R(...) with aggi in Q
      i := i + 1
      End
  End

For each variable V appearing outside of an aggregate
   Ai := Aggregation(V, Sample, {}, G)
   E := E append (V, aggi)
   i := i + 1
   End

A := Ai, ..., Ai-1
P := AggregateJoin(A)

PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>
SELECT (SUM(?val) AS ?sum) (COUNT(?a) AS ?count)
WHERE {
  ?a rdf:value ?val .
} GROUP BY ?a

Let G := Group((?a), BGP(?a rdf:value ?val))
A1 = Aggregation((?val), Sum, {}, G)
A2 = Aggregation((?a), Count, {}, G)
A := (A1, A2)
Let P := AggregateJoin(A)

Let Q := the query level being evaluated
Let P := the algebra translation of the query level so far

For each HAVING(E) in Q
    P := Filter(E, P)
    End

Let P := the algebra translation of the query level so far
P := Join(P, ToMultiSet(data))
  where data is a solution sequence formed from the VALUES clause

SELECT selItem ... { pattern }
SELECT * { pattern }

Let X := algebra from earlier steps
Let VS := list of all variables visible in the pattern,
           so restricted by sub-SELECT projected variables and GROUP BY variables.
           Not visible: only in filter, exists/not exists, masked by a subselect, 
                        non-projected GROUP variables, only in the right hand side of MINUS

Let PV := {}, a set of variable names
Note, E is a list of pairs of the form (variable, expression), defined in section 18.2.4
  
If "SELECT *"
    PV := VS

If  "SELECT selItem ...:"  
    For each selItem:
        If selItem is a variable
            PV := PV ∪ { variable }
        End
        If selItem is (expr AS variable)
            variable must not appear in VS nor in PV; if it does then generate a syntax error and stop
            PV := PV ∪ { variable }
            E := E append (variable, expr) 
        End
    End

For each pair (var, expr) in E
    X := Extend(X, var, expr)
    End
  
Result is X  
The set PV is used later for projection.
            

18.2.5 Converting Solution Modifiers

Solutions modifiers apply to the processing of a SPARQL query after pattern matching. The solution modifiers are applied to a query in the following order:

• Order by
• Projection
• Distinct
• Reduced
• Offset
• Limit

Step: ToList

ToList turns a multiset into a sequence with the same elements and cardinality. There is no implied ordering to the sequence; duplicates need not be adjacent.

Let M := ToList(Pattern)

Two solution mappings μ₁ and μ₂ are compatible if, for every variable v in dom(μ₁) and in dom(μ₂), μ₁(v) = μ₂(v).

18.3.1 SPARQL Basic Graph Pattern Matching

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.

For 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).

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

If a basic graph pattern is the empty set, then the solution is Ω₀.

18.3.2 Treatment of Blank Nodes

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.

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

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

Notation

Write

eval(Path(X, PP, Y))

for the evaluation of the property path patterns. This produces a multiset of solution mappings μ, each solution mapping having a binding for variables used (each of X and Y can be a variable). Some operators only produce a set of solution mappings.

Write

Var(x₁, x₂, ..., x_n) = { x_i | i in 1...n and x_i is a variable }

for the variables in x1, x2, ..., xn.

Write

Definition: Evaluation of Sequence Property Path

Let P and Q be property path expressions. Let V be a fresh variable.

A = Join( eval(Path(X, P, V)), eval(Path(V, Q, Y)) )

eval(Path(X, seq(P,Q), Y)) = Project(A, Var(X,Y))

Definition: Node set of a graph

The node set of a graph G, nodes(G), is:

nodes(G) = { n | n is an RDF term that is used as a subject or object of a triple of G}

Definition: Evaluation of ZeroOrOnePath

eval(Path(X:term, ZeroOrOnePath(P), Y:var)) = { (Y, yn) | yn = X or {(Y, yn)} in eval(Path(X,P,Y)) }

eval(Path(X:var, ZeroOrOnePath(P), Y:term)) = { (X, xn) | xn = Y or {(X, xn)} in eval(Path(X,P,Y)) }

eval(Path(X:term, ZeroOrOnePath(P), Y:term)) = 
    { {} } if X = Y or eval(Path(X,P,Y)) is not empty
    { } othewise

eval(Path(X:var, ZeroOrOnePath(P), Y:var)) = 
    { (X, xn) (Y, yn) | either (yn in nodes(G) and xn = yn) or {(X,xn), (Y,yn)} in eval(Path(X,P,Y)) }

Definition: Function ALP

Let eval(x:term, path) be the evaluation of 'path', starting at RDF term x, 
                       and returning a multiset of RDF terms reached 
                       by repeated matches of path.

ALP(x:term, path) = 
    Let V = empty multiset
    ALP(x:term, path, V)
    return is V

# V is the set of nodes visited

ALP(x:term, path, V:set of RDF terms) =
    if ( x in V ) return 
    add x to V
    X = eval(x,path) 
    For n:term in X
        ALP(n, path, V)
        End

Definition: Evaluation of ZeroOrMorePath

eval(Path(X:term, ZeroOrMorePath(path), vy:var)) =
    { { (vy, n) } | n in ALP(X, path) }

eval(Path(vx:var, ZeroOrMorePath(path), vy:var)) =
    { { (vx, t), (vy, n) } |  t in nodes(G), (vy, n) in eval(Path(t, ZeroOrMorePath(path), vy)) }

eval(Path(vx:var, ZeroOrMorePath(path), y:term)) = 
    eval(Path(y:term, ZeroOrMorePath(inv(path)), vx:var))

eval(Path(x:term, ZeroOrMorePath(path), y:term)) = 
    { { } } if { (vy:var,y) } in eval(Path(x, ZeroOrMorePath(path) vy)
    { } otherwise
	

Definition: Evaluation of OneOrMorePath

eval(Path(X, OneOrMorePath(path), Y))

# For OneOrMorePath, we take one step of the path then start
# recording nodes for results.

eval(Path(x:term, OneOrMorePath(path), vy:var)) =
    Let X = eval(x, path)
    Let V = the empty multiset
    For n in X
        ALP(n, path, V)
        End
    result is V

eval(Path(vx:var, OneOrMorePath(path), vy:var)) =
   { { (vx, t), (vy, n) } |  t in nodes(G), (vy, n) in eval(Path(t, OneOrMorePath(path), vy)) }

eval(Path(vx:var, OneOrMorePath(path), y:term)) =
   eval(Path(y:term, OneOrMorePath(inv(path)), vx))

eval(Path(x:term, OneOrMorePath(path), y:term)) =
    { { } } if { (vy:var, y) } in eval(Path(x, OneOrMorePath(path), vy))
    { } otherwise
	

Definition: Evaluation of NegatedPropertySet

Write μ' as the extension of a solution mapping:
μ'(μ,x) = μ(x)   if x is a variable
μ'(μ,t) = t   if t is a RDF term
	

Let x and y be variables or RDF terms, and S a set of IRIs:

eval(Path(x, NPS(S), y)) = { μ | ∃ triple(μ'(μ,x), p, μ'(μ,y)) in G, such that the IRI of p ∉ S }
	

Definition: Filter

Let Ω be a multiset of solution mappings and expr be an expression. We define:

Filter(expr, Ω, D(G)) = { μ | μ in Ω and expr(μ) is an expression that has an effective boolean value of true }

card[Filter(expr, Ω, D(G))](μ) = card[Ω](μ)

Note that evaluating an exists(pattern) expression uses the dataset and active graph, D(G). See the evaluation of filter.

Definition: Join

Let Ω₁ and Ω₂ be multisets of solution mappings. We define:

Join(Ω₁, Ω₂) = { merge(μ₁, μ₂) | μ₁ in Ω₁and μ₂ in Ω₂, and μ₁ and μ₂ are compatible }

card[Join(Ω₁, Ω₂)](μ) =
    for each merge(μ₁, μ₂), μ₁ in Ω₁and μ₂ in Ω₂ such that μ = merge(μ₁, μ₂),
        sum over (μ₁, μ₂), card[Ω₁](μ₁)*card[Ω₂](μ₂)

Definition: Diff

Let Ω₁ and Ω₂ be multisets of solution mappings and expr be an expression. We define:

Diff(Ω₁, Ω₂, expr) = { μ | μ in Ω₁ such that ∀ μ′ in Ω₂, either μ and μ′ are not compatible or μ and μ' are compatible and expr(merge(μ, μ')) has an effective boolean value of false }

card[Diff(Ω₁, Ω₂, expr)](μ) = card[Ω₁](μ)

Definition: LeftJoin

Let Ω₁ and Ω₂ be multisets of solution mappings and expr be an expression. We define:

LeftJoin(Ω₁, Ω₂, expr) = Filter(expr, Join(Ω₁, Ω₂)) ∪ Diff(Ω₁, Ω₂, expr)

card[LeftJoin(Ω₁, Ω₂, expr)](μ) = card[Filter(expr, Join(Ω₁, Ω₂))](μ) + card[Diff(Ω₁, Ω₂, expr)](μ)

Definition: Union

Let Ω₁ and Ω₂ be multisets of solution mappings. We define:

Union(Ω₁, Ω₂) = { μ | μ in Ω₁ or μ in Ω₂ }

card[Union(Ω₁, Ω₂)](μ) = card[Ω₁](μ) + card[Ω₂](μ)

Definition: Minus

Let Ω₁ and Ω₂ be multisets of solution mappings. We define:

Minus(Ω₁, Ω₂) = { μ | μ in Ω₁ . ∀ μ' in Ω₂, either μ and μ' are not compatible or dom(μ) and dom(μ') are disjoint }

card[Minus(Ω₁, Ω₂)](μ) = card[Ω₁](μ)

Let μ be a solution mapping, Ω a multiset of solution mappings, var a variable and expr be an expression, then we define:

Extend(μ, var, expr) = μ ∪ { (var,value) | var not in dom(μ) and value = expr(μ) }

Extend(μ, var, expr) = μ if var not in dom(μ) and expr(μ) is an error

Extend is undefined when var in dom(μ).

Extend(Ω, var, expr) = { Extend(μ, var, expr) | μ in Ω }

Let Ω be a multiset of solution mappings. We define:

ToList(Ω) = a sequence of mappings μ in Ω in any order, with card[Ω](μ) occurrences of μ

card[ToList(Ω)](μ) = card[Ω](μ)

Let Ψ be a sequence of solution mappings. We define:

OrderBy(Ψ, condition) = [ μ | μ in Ψ and the sequence satisfies the ordering condition]

card[OrderBy(Ψ, condition)](μ) = card[Ψ](μ)

Let Ψ be a sequence of solution mappings and PV a set of variables.

For mapping μ, write Proj(μ, PV) to be the restriction of μ to variables in PV.

Project(Ψ, PV) = [ Proj(Ψ[μ], PV) | μ in Ψ ]

card[Project(Ψ, PV)](μ) = card[Ψ](μ)

The order of Project(Ψ, PV) must preserve any ordering given by OrderBy.

Let Ψ be a sequence of solution mappings. We define:

Distinct(Ψ) = [ μ | μ in Ψ ]

card[Distinct(Ψ)](μ) = 1

The order of Distinct(Ψ) must preserve any ordering given by OrderBy.

Let Ψ be a sequence of solution mappings. We define:

Reduced(Ψ) = [ μ | μ in Ψ ]

card[Reduced(Ψ)](μ) is between 1 and card[Ψ](μ)

The order of Reduced(Ψ) must preserve any ordering given by OrderBy.

Let Ψ be a sequence of solution mappings. We define:

Slice(Ψ, start, length)[i] = Ψ[start+i] for i = 0 to (length-1)

Let Ψ be a solution sequence. We define:

ToMultiSet(Ψ) = { μ | μ in Ψ }

card[ToMultiSet(Ψ)](μ) = card[Ψ](μ)

Definition: ToMultiset

ToMultiset turns a sequence into a multiset with the same elements and cardinality as the sequence. The order of the sequence has no effect on the resulting multiset, and duplicates are preserved.

Definition: Exists

exists(pattern) is a function that returns true if the pattern evaluates to a non-empty solution sequence, given the current solution mapping and active graph at the time of evaluation; otherwise it returns false.

18.5.1 Aggregate Algebra

Group is a function which groups a solution sequence into multiple solutions, based on some attribute of the solutions.

Note that, although the result of a ListEval can be an error, and errors may be used to group, solutions containing error values are removed at projection time.

ListEval((unbound), μ) = (error), as the evaluation of an unbound expression is an error.

Aggregation, a function which calculates a scalar value as an output of the aggregate expression. It is used in the SELECT clause, the HAVING evaluation process, and in ORDER BY (where required). Aggregation calculates aggregated values over groups of solutions, using set functions.

scalarvals are used to pass values to the underlying set function, bypassing the mechanics of the grouping. For example, the aggregate expression GROUP_CONCAT(?x ; separator="|") has a scalarvals argument of { "separator" → "|" }.

All aggregates may have the DISTINCT keyword as the first token in their argument list. If this keyword is present then first argument to func is Distinct(M).

Example

Given a solution multiset (Ω) with the following values:

And the query expression SELECT (ex:agg(?y, ?z) AS ?agg) WHERE { ?x ?y ?z } GROUP BY ?x.

We produce G = Group((?x), Ω) = { ( (1), { μ₁, μ₂ } ), ( (2), { μ₃ } ) }

And so Aggregation((?y, ?z), ex:agg, {}, G) =
{ ((1), eg:agg({(2, 3), (3, 4)}, {})), ((2), eg:agg({(5, 6)}, {})) }.

Flatten is a function which is used to collapse multisets of lists into a multiset, so for example { (1, 2), (3, 4) } becomes { 1, 2, 3, 4 }.

Definition: Substitute

Let μ be a solution mapping.

substitute(pattern, μ) = the pattern formed by replacing every occurrence of a variable v in pattern by μ(v) for each v in dom(μ)

Definition: Evaluation of Exists

Let μ be the current solution mapping for a filter and P a graph pattern:

The value exists(P), given D(G) is true if and only if eval(D(G), substitute(P, μ)) is a non-empty sequence.

eval(D(G), Join(P1, P2)) = Join(eval(D(G), P1), eval(D(G), P2))

eval(D(G), LeftJoin(P1, P2, F)) = LeftJoin(eval(D(G), P1), eval(D(G), P2), F)

eval(D(G), Union(P1,P2)) = Union(eval(D(G), P1), eval(D(G), P2))

if IRI is a graph name in D
eval(D(G), Graph(IRI,P)) = eval(D(D[IRI]), P)

if IRI is not a graph name in D
eval(D(G), Graph(IRI,P)) = the empty multiset

eval(D(G), Graph(var,P)) =
     Let R be the empty multiset
     foreach IRI i in D
        R := Union(R, Join( eval(D(D[i]), P) , Ω(?var->i) )
     the result is R
          

eval(D(G), Slice(L, start, length)) = Slice(eval(D(G), L), start, length)

18.7.1 Notes

(a) SG will often be graph equivalent to AG, but restricting this to E-equivalence allows some forms of normalization, for example elimination of semantic redundancies, to be applied to the source documents before querying.

(b) The construction in condition 3 ensures that any blank nodes introduced by the solution mapping are used in a way which is internally consistent with the way that blank nodes occur in SG. This ensures that blank node identifiers occur in more than one answer in an answer set only when the blank nodes so identified are indeed identical in SG. If the extension does not allow bindings to blank nodes, then this condition can be simplified to the condition:

SG E-entails μ(BGP) for each solution mapping μ.

(c) These conditions do not impose the SPARQL requirement that SG shares no blank nodes with AG or BGP. In particular, it allows SG to actually be AG. This allows query protocols in which blank node identifiers retain their meaning between the query and the source document, or across multiple queries. Such protocols are not supported by the current SPARQL protocol specification, however.

(d) Since conditions 1 to 3 are only necessary conditions on answers, condition 4 allows cases where the set of legal answers can be restricted in various ways.

(e) None of these conditions refer explicitly to instance mappings on blank nodes in BGP. For some entailment regimes, the existential interpretation of blank nodes cannot be fully captured by the existence of a single instance mapping. These conditions allow such regimes to give blank nodes in query patterns a 'fully existential' reading.

It is straightforward to show that SPARQL satisfies these conditions for the case where E is simple entailment, given that the SPARQL condition on SG is that it is graph-equivalent to AG but shares no blank nodes with AG or BGP (which satisfies the first condition). The only condition which is nontrivial is (3).

For every solution mapping μ_i, there is, by definition of basic graph pattern matching, an RDF instance mapping σ_i such that P_i(BGP_i) is a subgraph of SG where P_i is the pattern instance mapping composed of μ_i and σ_i. Since BGP_i and SG have no blank nodes in common, the ranges of σ_i and μ_i contain no blank nodes from BGP_i; therefore, the solution mapping μ_i and the RDF instance mapping σ_i of P_i commute, so P_i(BGP_i) = σ_i(μ_i(BGP_i)). So

P₁(BGP₁) union ... union P_n(BGP_n)
= σ₁(μ₁(BGP₁)) union ... union σ_n(μ_n(BGP_n))
= [ σ₁ + ... + σ_n]( μ₁(BGP₁) union ... union μ_n(BGP_n) )

since the domains of the σ_i RDF instance mappings are all mutually exclusive. Since they are also exclusive from SG,

SG union [ σ₁ + ... + σ_n]( μ₁(BGP₁) union ... union μ_n(BGP_n) )
= [ σ₁ + ... + σ_n](SG union μ₁(BGP₁) union ... union μ_n(BGP_n) )

i.e.

SG union μ₁(BGP₁) union ... union μ_n(BGP_n)

has an instance which is a subgraph of SG, so is simply entailed by SG by the RDF interpolation lemma [RDF-MT].