May 02, 2015 .. currentmodule:: rdfextras.sparql.algebra

algebra - SPARQL Algebra

An implementation of the W3C SPARQL Algebra on top of sparql-p’s expansion trees

See: http://www.w3.org/TR/rdf-sparql-query/#sparqlAlgebra

For each symbol in a SPARQL abstract query, we define an operator for evaluation. The SPARQL algebra operators of the same name are used to evaluate SPARQL abstract query nodes as described in the section “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.

class rdfextras.sparql.algebra.AlgebraExpression[source]

For each symbol in a SPARQL abstract query, we define an operator for evaluation. The SPARQL algebra operators of the same name are used to evaluate SPARQL abstract query nodes as described in the section “Evaluation Semantics”.

evaluate(tripleStore, initialBindings, prolog)[source]

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

class rdfextras.sparql.algebra.EmptyGraphPatternExpression[source]

A placeholder for evaluating empty graph patterns - which should result in an empty multiset of solution bindings

class rdfextras.sparql.algebra.NonSymmetricBinaryOperator[source]
class rdfextras.sparql.algebra.Join(BGP1, BGP2)[source]
[[(P1 AND P2)]](D,G) = [[P1]](D,G) compat [[P2]](D,G)

Join(Ω1, Ω2) = { merge(μ1, μ2) | μ1 in Ω1 and μ2 in Ω2, and μ1 and μ2 are                          compatible }

Pseudocode implementation:

Evaluate BGP1 Traverse to leaves (expand and expandOption leaves) of BGP1, set ‘rest’ to triple patterns in BGP2 (filling out bindings). Trigger another round of expand / expandOptions (from the leaves)

class rdfextras.sparql.algebra.LeftJoin(BGP1, BGP2, expr=None)[source]
Let Ω1 and Ω2 be multisets of solution mappings and F a filter. We define:
LeftJoin(Ω1, Ω2, expr) =
    Filter(expr, Join(Ω1, Ω2)) set-union Diff(Ω1, Ω2, expr)

LeftJoin(Ω1, Ω2, expr) =
{ merge(μ1, μ2) | μ1 in Ω1 and μ2 in Ω2, and
                  μ1 and μ2 are compatible, and
                  expr(merge(μ1, μ2)) is true }
set-union
{ μ1 | μ1 in Ω1 and μ2 in Ω2, and
       μ1 and μ2 are not compatible }
set-union
{ μ1 | μ1 in Ω1and μ2 in Ω2, and μ1 and μ2 are compatible and
       expr(merge(μ1, μ2)) is false }
class rdfextras.sparql.algebra.Union(BGP1, BGP2)[source]
  1. [[(P1 UNION P2)]](D,G) = [[P1]](D,G) OR [[P2]](D,G)

Union(Ω1, Ω2) = { μ | μ in Ω1 or μ in Ω2 }

class rdfextras.sparql.algebra.GraphExpression(iriOrVar, GGP)[source]
[24] GraphGraphPattern ::=  'GRAPH'  VarOrIRIref  GroupGraphPattern
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) , Omega(?v->i) )
evaluate(tripleStore, initialBindings, prolog)[source]

The GRAPH keyword is used to make the active graph one of all of the named graphs in the dataset for part of the query.

rdfextras.sparql.algebra.ReduceGraphPattern(graphPattern, prolog)[source]

Takes parsed graph pattern and converts it into a BGP operator

Replace all basic graph patterns by BGP(list of triple patterns)

rdfextras.sparql.algebra.ReduceToAlgebra(left, right)[source]

Converts a parsed Group Graph Pattern into an expression in the algebra by recursive folding / reduction (via functional programming) of the GGP as a list of Basic Triple Patterns or “Graph Pattern Blocks”

12.2.1 Converting Graph Patterns

[20] GroupGraphPattern ::= '{' TriplesBlock? ( ( GraphPatternNotTriples | Filter )
     '.'? TriplesBlock? )* '}'
[22] GraphPatternNotTriples ::= OptionalGraphPattern | GroupOrUnionGraphPattern |
     GraphGraphPattern
[26] Filter ::= 'FILTER' Constraint
[27] Constraint ::= BrackettedExpression | BuiltInCall | FunctionCall
[56] BrackettedExpression  ::= '(' ConditionalOrExpression ')'


( GraphPatternNotTriples | Filter ) '.'? TriplesBlock?
   nonTripleGraphPattern     filter         triples
rdfextras.sparql.algebra.RenderSPARQLAlgebra(parsedSPARQL, nsMappings=None)[source]
rdfextras.sparql.algebra.LoadGraph(dtSet, dataSetBase, graph)[source]
rdfextras.sparql.algebra.TopEvaluate(query, dataset, passedBindings=None, DEBUG=False, exportTree=False, dataSetBase=None, extensionFunctions={}, dSCompliance=False, loadContexts=False)[source]

The outcome of executing a SPARQL 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.

rdfextras.sparql.algebra.fetchUnionBranchesRoots(node)[source]
rdfextras.sparql.algebra.fetchChildren(node)[source]
rdfextras.sparql.algebra.walktree(top, depthfirst=True, leavesOnly=True, optProxies=False)[source]
rdfextras.sparql.algebra.print_tree(node, padding=' ')[source]

Previous topic

sparql - SPARQL main API

Next topic

components - SPARQL components