Definition of SPARQL

This section defines the correct behavior for evaluation of graph patterns and solution modifiers, given a query string and an RDF dataset. It does not imply a SPARQL implementation must use the process defined here.

The outcome of executing a SPARQL query is defined by a series of steps, starting from the SPARQL query as a string, turning that string into an abstract syntax form, then turning the abstract syntax into a SPARQL abstract query comprising operators from the SPARQL algebra. This abstract query is then evaluated on an RDF dataset.

Property Path Patterns

This section defines the evaluation of property path patterns. A property path pattern is a subject endpoint (an RDF term or a variable), a property path express and an object endpoint. The translation of property path expressions converts some forms to other SPARQL expressions, such as converting property paths of length one to triple patterns, which in turn are combined into basic graph patterns. This leaves property path operators ZeroOrOnePath, ZeroOrMorePath, OneOrMorePath and NegatedPropertySets and also path expressions contained within these operators.

All remaining property path expressions are present in the algebra in the form Path(X, path, Y) for endpoints X and Y. For example: syntax(:p/:q)* is a ZeroOrMorePath expression involving a sequence property path becoming the algebra expession ZeroOrMorePath(seq(link(:p), link(:q))).

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

1, x

2, ..., x

n) = { x

i | i in 1...n and x

i is a variable }

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

Write

x:term	when x is an RDF term
x:var	when x is a variable
x:path	when x is a path expression

All evaluation is carried out by matching the active graph at that point in the overall query evaluation. We omit explicitly including the active graph in each definition for clarity.

Definition: Evaluation of Predicate Property Path

Let Path(X, link(iri), Y) be an predicate inverse property path pattern, using some IRI iri.

eval(Path(X, link(iri), Y)) =

evaluation of basic graph pattern {X iri Y}

If both X and Y are variables, this is the same as:

eval(Path(X:var, link(iri), Y:var)) = { (X, xn) (Y, yn) | xn and yn are RDF terms and triple (xn iri yn) is in the active graph }

If X is a variable and Y an RDF term:

eval(Path(X:var, link(iri), Y:term)) = { (X, xn) | xn is an RDF term and triple (xn iri Y) is in the active graph }

If X is an RDF term and Y is a variable:

eval(Path(X:term, link(iri), Y:var)) = { (Y, yn) | yn is an RDF term and triple (X iri yn) is in the active graph }

If both X and Y are RDF terms:

eval(Path(X:term, link(iri), Y:term)) = { μ

0 } if triple (X iri Y) is in the active graph = { { } } = Ω

0 eval(Path(X:term, link(iri), Y:term)) = { } if triple (X iri Y) is not in the active graph

Informally, evaluating a Predicate Property Path is the same as executing a subquery SELECT * { X P Y } at that point in the query evaluation.

Definition: Evaluation of Inverse Property Path

Let P be a property path expression, then:

eval(Path(X, inv(P), Y)) = eval(Path(Y, P, X))

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

Informally, this is the same as:

SELECT * { X P _:a . _:a Q Y }

using the fact that a blank node _:a acts like a variable (under simple entailment) except it does not appear in the results from SELECT *.

Definition: Evaluation of Alternative Property Path

Let P and Q be property path expressions.

eval(Path(X, alt(P,Q), Y)) = Union(eval(Path(X, P, Y)), eval(Path(X, Q, Y)))

Informally, this is the same as:

SELECT * { { X P Y } UNION { X Q 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)) }

We define an auxillary function, ALP, used in the definitions of ZeroOrMorePath and OneOrMorePath. Note that the algorithm given here serves to specify the feature. An implementation is free to implement evaluation by any method that produces the same results for the query overall. The ZeroOrMorePath and OneOrMorePath forms return matches based on distinct nodes connected by the path.

The matching algorithm is based on following all paths, and detecting when a graph node (subject or object), has been already visited on the path.

Informally, this algorithm attempts to extend the multiset of results by one application of path at each step, noting which nodes it has visited for this particular path. If a node has been visited for the path under consideration, it is not a candidate for another step.

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 }

Evaluation Semantics

We define eval(D(G), algebra expression) as the evaluation of an algebra expression with respect to a dataset D having active graph G. The active graph is initially the default graph.

D : a dataset
D(G) : D a dataset with active graph G (the one patterns match against)
D[i] : The graph with IRI i in dataset D
P, P1, P2 : graph patterns
L : a solution sequence
F : an expression

Definition: Evaluation of a Basic Graph Pattern

eval(D(G), BGP) = multiset of solution mappings

See section Basic Graph Patterns

Definition: Evaluation of a Property Path Pattern

eval(D(G), Path(X, path, Y)) = multiset of solution mappings

See section Property Path Expresions

Definition: Evaluation of Filter

eval(D(G), Filter(F, P)) = Filter(F, eval(D(G),P), D(G))

'substitute' is a filter function in support of the evaluation of EXISTS and NOT EXISTS forms which were translated to exists.

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.

Definition: Evaluation of Join

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

Definition: Evaluation of LeftJoin

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

Definition: Evaluation of Union

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

Definition: Evaluation of Graph

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

The evaluation of graph uses the SPARQL algebra union operator. The cardinality of a solution mapping is the sum of the cardinalities of that solution mapping in each join operation.

Definition: Evaluation of Group

eval(D(G), Group(exprlist, P)) = Group(exprlist, eval(D(G), P))

Definition: Evaluation of Aggregation

eval(D(G), Aggregation(exprlist, func, scalarvals, P)) = Aggregation(exprlist, func, scalarvals, eval(D(G), P))

Definition: Evaluation of AggregateJoin

eval(D(G), AggregateJoin(A1, ..., An)) = AggregateJoin(eval(D(G), A1), ..., eval(D(G), An))

Note that if eval(D(G), Ai) is an error, it is ignored.

Definition: Evaluation of Extend

eval(D(G), Extend(P, var, expr)) = Extend(eval(D(G), P), var, expr)

Definition: Evaluation of ToList

eval(D(G), ToList(P)) = ToList(eval(D(G), P))

Definition: Evaluation of Distinct

eval(D(G), Distinct(L)) = Distinct(eval(D(G), L))

Definition: Evaluation of Reduced

eval(D(G), Reduced(L)) = Reduced(eval(D(G), L))

Definition: Evaluation of Project

eval(D(G), Project(L, vars)) = Project(eval(D(G), L), vars)

Definition: Evaluation of OrderBy

eval(D(G), OrderBy(L, condition)) = OrderBy(eval(D(G), L), condition)

Definition: Evaluation of ToMultiSet

eval(D(G), ToMultiSet(L)) = ToMultiSet(eval(D), M))

Definition: Evaluation of Slice

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