Translation to the SPARQL Algebra

This section defines the process of converting graph patterns and solution modifiers in a SPARQL query string into a SPARQL algebra expression. The process described converts one level of query nesting, as formed by subqueries using the nested SELECT syntax and is applied recursively on subqueries. Each level consists of graph pattern matching and filtering, followed by the application of solution modifiers.

The SPARQL query string is parsed and the abbreviations for IRIs and triple patterns given in section 4 are applied. At this point the abstract syntax tree is composed of:

Patterns	Modifiers	Query Forms	Other
RDF terms	DISTINCT	SELECT	VALUES
Property path expression	REDUCED	CONSTRUCT	SERVICE
Property path patterns	Projection	DESCRIBE
Groups	ORDER BY	ASK
OPTIONAL	LIMIT
UNION	OFFSET
GRAPH	Select expressions
BIND
GROUP BY
HAVING
MINUS
FILTER

The result of converting such an abstract syntax tree is a SPARQL query that uses the following symbols in the SPARQL algebra:

Graph Pattern	Solution Modifiers	Property Path
BGP	ToList	PredicatePath
Join	OrderBy	InversePath
LeftJoin	Project	SequencePath
Filter	Distinct	AlernativePath
Union	Reduced	ZeroOrMorePath
Graph	Slice	OneOrMorePath
Extend	ToMultiSet	ZeroOrOnePath
Minus		NegatedPropertySet
Group
Aggregation
AggregateJoin

Slice is the combination of OFFSET and LIMIT.

ToList is used where conversion from the results of graph pattern matching to sequences occurs.

ToMultiSet is used where conversion from a solution sequence to a multiset occurs.

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:

Syntax Form	In-scope variables
Basic Graph Pattern (BGP)	`v` occurs in the BGP
Path	`v` occurs in the path
Group `{ P1 P2 ... }`	`v` is in-scope if it is in-scope in one or more of P1, P2, ...
`GRAPH term { P }`	`v` is `term` or `v` is in-scope in P
`{ P1 } UNION { P2 }`	`v` is in-scope in P1 or in-scope in P2
`OPTIONAL {P}`	`v` is in-scope in P
`SERVICE term {P}`	`v` is `term` or `v` is in-scope in P
`BIND (expr AS v)`	`v` is in-scope
`SELECT .. v .. { P }`	`v` is in-scope
`SELECT ... (expr AS v)`	`v` is in-scope
`GROUP BY (expr AS v)`	`v` is in-scope
`SELECT * { P }`	`v` is in-scope in `P`
`VALUES v { values }`	`v` is in-scope
`VALUES varlist { values }`	`v` is in-scope if `v` is in `varlist`

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.

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:

{ ?s ?p ?o }

Join(Z, BGP(?s ?p ?o) )

BGP(?s ?p ?o)

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

{ ?s :p1 ?v1 ; :p2 ?v2 }

BGP( ?s :p1 ?v1 . ?s :p2 ?v2 )

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

{ { ?s :p1 ?v1 } UNION {?s :p2 ?v2 } }

Union(Join(Z, BGP(?s :p1 ?v1)),

Join(Z, BGP(?s :p2 ?v2)) )

Union( BGP(?s :p1 ?v1) , BGP(?s :p2 ?v2) )

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

{ { ?s :p1 ?v1 } UNION {?s :p2 ?v2 } UNION {?s :p3 ?v3 } }

Union(

Union( Join(Z, BGP(?s :p1 ?v1)),

Join(Z, BGP(?s :p2 ?v2))) ,

Join(Z, BGP(?s :p3 ?v3)) )

Union(

Union( BGP(?s :p1 ?v1) ,

BGP(?s :p2 ?v2),

BGP(?s :p3 ?v3))

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

{ ?s :p1 ?v1 OPTIONAL {?s :p2 ?v2 } }

LeftJoin(

Join(Z, BGP(?s :p1 ?v1)),

Join(Z, BGP(?s :p2 ?v2)),

true)

LeftJoin(BGP(?s :p1 ?v1), BGP(?s :p2 ?v2), true)

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

{ ?s :p1 ?v1 OPTIONAL {?s :p2 ?v2 } OPTIONAL { ?s :p3 ?v3 } }

LeftJoin(

BGP(?s :p1 ?v1),

BGP(?s :p2 ?v2),

true) ,

BGP(?s :p3 ?v3),

true)

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

{ ?s :p1 ?v1 OPTIONAL {?s :p2 ?v2 FILTER(?v1<3) } }

LeftJoin(

Join(Z, BGP(?s :p1 ?v1)),

Join(Z, BGP(?s :p2 ?v2)),

(?v1<3) )

LeftJoin(

BGP(?s :p1 ?v1) ,

BGP(?s :p2 ?v2) ,

(?v1<3) )

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

{ {?s :p1 ?v1} UNION {?s :p2 ?v2} OPTIONAL {?s :p3 ?v3} }

LeftJoin(

Union(BGP(?s :p1 ?v1),

BGP(?s :p2 ?v2)) ,

BGP(?s :p3 ?v3) ,

true )

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

{ ?s :p1 ?v1 FILTER (?v1 < 3 ) OPTIONAL {?s :p2 ?v2} }

Filter( ?v1 < 3 ,

LeftJoin( BGP(?s :p1 ?v1), BGP(?s :p2 ?v2), true) ,

)

Example: Pattern involving BIND:

{ ?s :p ?v . BIND (2*?v AS ?v2) ?s :p1 ?v2 }

Join(

Extend( BGP(?s :p ?v), ?v2, 2*?v) ,

BGP(?s :p1 ?v2) )

Example: Pattern involving BIND:

{ ?s :p ?v . {} BIND (2*?v AS ?v2) }

Join(

BGP(?s :p ?v), ?v2, 2*?v) ,

Extend({}, ?v2, 2*?v)

)

Example: Pattern involving MINUS:

{ ?s :p ?v . MINUS {?s :p1 ?v2 } }

Minus(

BGP(?s :p ?v)

BGP(?s :p1 ?v2))

Example: Pattern involving a subquery:

{ ?s :p ?o . {SELECT DISTINCT ?o {?o ?p ?z} } }

Join(

BGP(?s :p ?o) ,

ToMultiSet(

Distinct(Project(BGP(?o ?p ?z), {?o})) )

)