The SPARQL Algebra

Background

• A relational algebra for SPARQL (Richard Cyganiak)
• Semantics and Complexity of SPARQL (Jorge Perez et al.)
• Follow up to the paper above: Semantics of SPARQL
• The paper "Semantics Preserving SPARQL-to-SQL Query Translation for Optional Graph Patterns" includes doing the difficult case of nested optionals. (Artem Chebotko et al.)

X SPARQL The SPARQL Algebra

The SPARQL Algebra defines the semantics of a SPARQL query execution. The algebraic expression is formed from the query string by first parsing, and then applying transformations as described below. The result of a query can then be calculated by the evaluation rules applied to the algebraic expression. This gives the correct results of  query -- it does not imply the actual execution of a query must be performed in this manner.

1. Mapping a query string to a SPARQL abstract query
2. SPARQL Algebra
3. Evaluation Semantics

X.1 Mapping a SPARQL Query to a SPARQL Abstract Query

X.1.1 Mapping Graph Patterns

Parsing a SPARQL query string produces an syntax tree comprised of:

• RDF terms and triple patterns
• Basic graph patterns
• Groups
• OPTIONAL
• UNION
• GRAPH
• FILTER(expression)

The result is a SPARQL abstract query that uses the symbols:

• BGP
• Join
• LeftJoin
• Filter
• Union
• Graph

This is not the grammar in rq24. Because of the explicit procedure to map groups to Join/LeftJoin expressions, this more direct form can be used and it more accurately relates the the conversion procedure.

Define "GraphPattern" as one of GroupGraphPattern, GroupOrUnionGraphPattern, GraphGraphPattern, OptionalGraphPattern and BasicGraphPattern.

Step 1 : BasicGraphPatterns

Replace all BasicGraphPattern elements by BGP(list of triple patterns)

Step 2 : GroupOrUnionGraphPattern

Replace any GroupOrUnionGraphPattern elements:

• If the element consists of a single GroupGraphPattern, replace with the GroupGraphPattern.
• If the element consists of multiple GroupGraphPatterns, connected with 'UNION' terminals,  then replace with a sequence of nested union operators:
  e.g. Union(Union(GroupGraphPattern, GroupGraphPattern), GroupGraphPattern).

Step 3 : GraphGraphPattern

Map GRAPH IRI GroupGraphPattern to Graph(IRI, GroupGraphPattern)

Map GRAPH Var GroupGraphPattern to Graph(var, GroupGraphPattern)

Step 4 : GroupGraphPattern

We introduce the following symbols:

• Join(Pattern, Pattern)
• LeftJoin(Pattern, Pattern, expression)
• Filter(expression, Pattern)

After parsing, a group pattern consists of a sequence of graph patterns and filters (Constraint).

A group pattern is mapped into the SPARQL algebra as follows:

This is the left-associative operator assignment, mapping optional to LeftJoin, adjacency to Join, and noting that LeftJoin can take a filter from its right (fixed) subelement.

Write: "A" for an algebra expression

Map all graph patterns contained in this group to give a list, SP, of algebra expressions
Let F := the conjunction of all filters appearing as elements of the GROUP expressions
Let G := the empty pattern, {}

for i := 0 ; i < length(SP); i++
   If SP[i] is an OPTIONAL,
      If SP[i] is of the form OPTIONAL(Filter(F, A))
           G := LeftJoin(G, A, F)
      else
           G := LeftJoin(G , A, true)
   Otherwise for expression SP[i], G := Join(G, SP[i])

If F is not empty:
  If G = empty pattern then G := Filter(F, empty pattern)
  If G = LeftJoin(A1, A2, true) then G := LeftJoin(A1, A2, F)
  If G = Join(A1, A2) then G := Filter(F, Join(A1, A2)
  If G = Union(A1, A2) then G := Filter(F, Union(A1, A2))
  If G = Graph(x, A) then G := Filter(F, Graph(x, A)) where x is a variable or IRI.
The result is G

Step 5 : Simplification

Groups of one graph pattern (not a filter) become join({}, A) and can be replaced by A

Replace join({}, A) by A

@@Join(A, {}) can also be removed.

X.1.2 Examples

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

X.1.3 Solution Modifiers

Symbols after parsing:

• DISTINCT
• PROJECT
• ORDER BY
• LIMIT/OFFSET

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.

Slice is the combination of Offset and Limit

• ToList(Pattern)
• OrderBy(Mod, condition)
• Project(Mod, vars)
• Distinct(Mod)
• Slice(List, start, length)

where Mod is any of the modifiers above.

• Order modifier
• Projection modifier
• Distinct modifier
• Offset modifier
• Limit modifier

Step 1 : ToList

Set M = ToList(Pattern)

Step 2 : ORDER BY

If the query string has any ORDER BY clauses

M =  OrderBy(M, list of of order conditions)

Step 3 : Projection

M = Project(M, vars)

where vars is the set of variables mentioned in the SELECT clause or all named variables in the query if SELECT * used.

Step 4 : Distinct

If the query contains DISTINCT,

M = Distinct(M)

Step 5 : OFFSET and LIMIT

If the query mentions "OFFSET start" or "LIMIT length"

M = Slice(M, start, length)

start defaults to 0

length defaults to the (size(M)-start)

The overall abstract query is M.

X.2 SPARQL Algebra Operators

@@A note about multisets: set and a cardinality function

X.2.1 Algebra operators

• BGP match (see section 2.5)
• Graph
• Filter
• Join
• Diff - only used for LeftJoin
• LeftJoin
• Union
• ToList
• OrderBy
• Project
• Distinct
• Slice

   

These operators are not those of the SPARQL abstract query form. The SPARQL algebra operators of the same name are used to evaluate SPARQL abstract query nodes as described in the section "Evaluation Semantics"

Solution is a mapping.

Write μ₀ for the mapping such that dom(μ₀) is the empty set.

Write Ω₀ for the multiset consisting of exactly the empty mapping μ_0, with cardinality 1.

Write μ(?x->t) for the substitution function mapping variable x to RDF term t : { (x, t) }

Write Ω(?x->t) for multiset consisting of exactly μ(?x->t), that is, { { (x, t) } } with cardinality 1.

Write merge(μ₁, μ₂) for μ₁ set-union μ₂

Write card[Ω](μ) for the cardinality of μ in a multiset of mappings Ω.

@@Cardinality function is not defined for μ not in Ω.

@@ Define expr(μ)

Written in full that is:

LeftJoin(Ω₁, Ω₂, expr) =
        { merge(μ_1, μ₂) | μ₁ in Ω₁and μ₂ in Ω₂, and μ₁ and μ₂ are compatible and expr(merge(μ₁, μ₂)) is true }
            set-union
        { μ₁ | μ₁ in Ω₁and μ₂ in Ω₂, and μ₁ and μ₂ are not compatible }
            set-union
        { μ₁ | μ₁ in Ω₁and μ₂ in Ω₂, and μ₁ and μ₂ are compatible and expr(merge(μ₁, μ₂)) is false }

As these are distinct, the cardinality of LeftJoin is cardinality of these individual components of the definition.

Write [x | C] for a sequence of elements satisfying some condition C

Write card[L](x) to be the cardinality of x in L

X.3 Evaluation Semantics

We define eval(D(G), graph pattern) as the evaluation of a graph pattern with respect to a dataset D having active graph G. The active graph is initially the default graph. The active graph is used to match the pattern unless otherwise stated.

@@Note the change from Join(pattern, pattern) (introduced parse symbols) to Join(mapping multiset, mapping multiset) etc.

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
D[DFT] : the default graph of D

eval(D(G), Join(P1, P2)) = Join(eval(D(G), P1), eval(D(G), P2))
eval(D(G), Join(P1, P2), F) = Filter(F, 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))

eval(D(G), Graph(IRI,P)) = eval(D(D[i]), P)
eval(D(G), Graph(var,P)) =
    multiset-union over IRI i in D : join( eval(D(D[i]), P) , Ω(?v->i) )

eval(List(P), Graph(IRI,P)) = ToList(eval(D[DFT], Graph(IRI,P))

eval(Distict(L)) = Distinct(eval(L))

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

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

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

$Log: rq24-algebra.html,v $
Revision 1.15  2007/01/03 15:14:36  aseaborne
Corrected from Fred Zemke (28 Dec 2006)

Revision 1.14  2006/12/15 18:09:07  aseaborne
Changes in response to

2006OctDec/0206
as noted in
2006OctDec/0208