March 16, 2016 .. 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”.
-
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.
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]¶ - [[(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) )
-
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.
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.