SPARQL Algebra

For each remaining 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". Evaluation of basic graph patterns and property path patterns has been described above.

Definition: Filter

Let Ω be a multiset of solution mappings and expr be an expression. We define:

Filter(expr, Ω, D(G)) = { μ | μ in Ω and expr(μ) is an expression that has an effective boolean value of true }

cardFilter(expr, Ω, D(G)) = cardΩ

Note that evaluating an exists(pattern) expression uses the dataset and active graph, D(G). See the evaluation of filter.

Definition: Join

Let Ω1 and Ω2 be multisets of solution mappings. We define:

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

cardJoin(Ω1, Ω2) =
    for each merge(μ1, μ2), μ1 in Ω1and μ2 in Ω2 such that μ = merge(μ1, μ2),
        sum over (μ1, μ2), cardΩ1*cardΩ2

It is possible that a solution mapping μ in a Join can arise in different solution mappings, μ1and μ2 in the multisets being joined. The cardinality of  μ is the sum of the cardinalities from all possibilities.

Definition: Diff

Let Ω1 and Ω2 be multisets of solution mappings and expr be an expression. We define:

Diff(Ω1, Ω2, expr) = { μ | μ in Ω1 such that ∀ μ′ in Ω2, either μ and μ′ are not compatible or μ and μ' are compatible and expr(merge(μ, μ')) has an effective boolean value of false }

cardDiff(Ω1, Ω2, expr) = cardΩ1

Diff is used internally for the definition of LeftJoin.

Definition: LeftJoin

Let Ω1 and Ω2 be multisets of solution mappings and expr be an expression. We define:

LeftJoin(Ω1, Ω2, expr) = Filter(expr, Join(Ω1, Ω2)) ∪ Diff(Ω1, Ω2, expr)

cardLeftJoin(Ω1, Ω2, expr) = cardFilter(expr, Join(Ω1, Ω2)) + cardDiff(Ω1, Ω2, expr)

Written in full that is:

LeftJoin(Ω1, Ω2, expr) =
    { merge(μ1, μ2) | μ1 in Ω1 and μ2 in Ω2, μ1 and μ2 are compatible and expr(merge(μ1, μ2)) is true }
∪
    { μ1 | μ1 in Ω1, ∀ μ2 in Ω2, μ1 and μ2 are not compatible, or Ω2 is empty }
∪
    { μ1 | μ1 in Ω1, ∃ μ2 in Ω2, μ1 and μ2 are compatible and expr(merge(μ1, μ2)) is false. }

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

Definition: Union

Let Ω1 and Ω2 be multisets of solution mappings. We define:

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

cardUnion(Ω1, Ω2) = cardΩ1 + cardΩ2

Definition: Minus

Let Ω1 and Ω2 be multisets of solution mappings. We define:

Minus(Ω1, Ω2) = { μ | μ in Ω1 . ∀ μ' in Ω2, either μ and μ' are not compatible or dom(μ) and dom(μ') are disjoint }

cardMinus(Ω1, Ω2) = cardΩ1

The additional restriction on dom(μ) and dom(μ') is added because otherwise if there is a solution mapping in Ω2 that has no variables in common with the solution mappings of Ω1, then Minus(Ω1, Ω2) would be empty, regardless of the rest of Ω2. The empty solution mapping is compatible with every other solution mapping so P MINUS {} would otherwise be empty for any pattern P.

Definition: ExtendLet μ be a solution mapping, Ω a multiset of solution mappings, var a variable and expr be an expression, then we define:

Extend(μ, var, expr) = μ ∪ { (var,value) | var not in dom(μ) and value = expr(μ) }

Extend(μ, var, expr) = μ if var not in dom(μ) and expr(μ) is an error

Extend is undefined when var in dom(μ).

Extend(Ω, var, expr) = { Extend(μ, var, expr) | μ in Ω }

Write [ x | C ] for a sequence of elements where C is a condition on x.

Write cardL to be the cardinality of x in L.

Definition: ToListLet Ω be a multiset of solution mappings. We define:

ToList(Ω) = a sequence of mappings μ in Ω in any order, with cardΩ occurrences of μ

cardToList(Ω) = cardΩ

Definition: OrderByLet Ψ be a sequence of solution mappings. We define:

OrderBy(Ψ, condition) = [ μ | μ in Ψ and the sequence satisfies the ordering condition]

cardOrderBy(Ψ, condition) = cardΨ

Definition: ProjectLet Ψ be a sequence of solution mappings and PV a set of variables.

For mapping μ, write Proj(μ, PV) to be the restriction of μ to variables in PV.

Project(Ψ, PV) = [ Proj(Ψ[μ], PV) | μ in Ψ ]

cardProject(Ψ, PV) = cardΨ

The order of Project(Ψ, PV) must preserve any ordering given by OrderBy.

Definition: DistinctLet Ψ be a sequence of solution mappings. We define:

Distinct(Ψ) = [ μ | μ in Ψ ]

cardDistinct(Ψ) = 1

The order of Distinct(Ψ) must preserve any ordering given by OrderBy.

Definition: ReducedLet Ψ be a sequence of solution mappings. We define:

Reduced(Ψ) = [ μ | μ in Ψ ]

cardReduced(Ψ) is between 1 and cardΨ

The order of Reduced(Ψ) must preserve any ordering given by OrderBy.

The Reduced solution sequence modifier does not guarantee a defined cardinality.

Definition: SliceLet Ψ be a sequence of solution mappings. We define:

Slice(Ψ, start, length)[i] = Ψ[start+i] for i = 0 to (length-1)

Definition: ToMultiSetLet Ψ be a solution sequence. We define:

ToMultiSet(Ψ) = { μ | μ in Ψ }

cardToMultiSet(Ψ) = cardΨ

ListEval is a function which is used to evaluate a list of expressions against a solution and return a list of the resulting values.

Definition: ToMultiset

ToMultiset turns a sequence into a multiset with the same elements and cardinality as the sequence. The order of the sequence has no effect on the resulting multiset, and duplicates are preserved.

Definition: Exists

exists(pattern) is a function that returns true if the pattern evaluates to a non-empty solution sequence, given the current solution mapping and active graph at the time of evaluation; otherwise it returns false.