Aggregates apply expressions over groups of solutions. By default
a solution set consists of a single group, containing all solutions.
This example demonstrates two features of aggregates: GROUP BY, which
groups query solutions according to one or more expressions (in this case
?org), and HAVING, which is analogous to a FILTER expression, but operates over
groups, rather than individual solutions.
In aggregate queries and sub-queries variables that appear in the query
pattern, but are not grouped by cannot be projected nor used in project
expressions. In order to project arbitrary expressions the SAMPLE
aggregate may be used.
10.2 Algebra Operators
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: ListEval
ListEval(ExprList, μ) returns a list E, where Ei =
μ(ExprListi).
A variant, ListEvalE, is the same except that all elements of E which are errors are removed.
Group, a function which groups a solution sequence into multiple solutions, based on some attribute of the solutions.
Definition: Group
Group evaluates a list of expressions against a solution sequence, producing a set of partial functions from keys to solution sequences.
The behaviour of Group is different when ExprList is empty. Note that the use of the number 1 here, is simply to distinguish from groups where the ExprList is non-empty.
Group((), Ω) = { 1 -> Ω }
Group(ExprList, Ω) = { ListEval(ExprList, μ) -> { μ' | μ' in Ω, ListEval(ExprList, μ) = ListEval(ExprList, μ') } | μ in Ω }
For example, given a solution sequence S, ( {?x→2, ?y→3}, {?x→2, ?y→5}, {?x→6, ?y→7} ),
Group((?x), S) = {
(2) → ( {?x→2, ?y→3}, {?x→2, ?y→5} ),
(6) → ( {?x→6, ?y→7} )
}
Aggregation, a function which calculates a scalar value as an output of the aggregate expression in the SELECT clause.
Definition: Aggregation
Aggregation applies a set function “func” to a multiset of lists of
expressions and a grouped solution sequence, G as produced by the Group
function. It produces a single value for each key and partition for that key
(key, X).
Aggregation(ExprList, func, scalar, G) = { dom(g) → F | g in G }
Where
M = ListEvalE(ExprList, range(g))
F = func(M, card[range(g)] - card[M], scalar), for non-DISTINCT
F = func(Distinct(M), card[range(g)] - card[M], scalar), for DISTINCT
Special Case: when COUNT is used with the expression
* the value of F will be cardinality of the group solution
sequence, card[range(g)], or card[Distinct(range(g))] if the
DISTINCT keyword is present.
"scalar" is a set of partial functions passed from the aggregate in the query. These are used to pass values to the underlying set function, bypassing the mechanics of the grouping. For example the aggregate expression GROUP_BY(?x ; separator="|") has a scalar argument of { "separator" → "|" }.
All aggregates may have the DISTINCT keyword as
the first token in their argument list. If this keyword is present then first
argument to func is Distinct(M).
Example
Given a solution multiset (Ω) with the following values:
And the query expression SELECT (ex:agg(?y, ?z) AS ?agg) WHERE { ?x ?y ?z } GROUP BY ?x.
We produce G = Group((?x), Ω) = { (1) → {?y=2, ?z=3}, {?y=3, ?z=4}), (2) → {?y=5, ?z=6} }
And so Aggregation((?y, ?z), ex:agg, {}, G) =
{ (1) → eg:agg({(2, 3), (3, 4)}, {})), (2) → eg:agg({(5, 6)}, {}) }.
HAVING operates over grouped solution sets, in the same way that FILTER operates over un-grouped ones.
HAVING expressions have the same evaluation rules as projections from
grouped queries, see the section on aggregate
projection.
Definition: Having
Let X be the algebra expression from the select expression, and expr to be an expression. We define:
Having(expr, X) = Filter(expr, X)
@@ possibly unintended consequence of the ordering in 17.1.7 is that HAVING can only operate on projected variables.
10.2.2 Set Functions
The set functions which underlie SPARQL aggregates all have a common
signature: SetFunc(M, err), or SetFunc(M, err, scalar, ...) where M is a
multiset
of lists, err is a value indicating whether the evaluation of any of the
expressions evaluated with respect to Ω returned an error, and scalar
is one or more scalar values that are passed to the set function indirectly via
the ( ... ; key=value ) syntax for aggregates in the SPARQL grammar.
Flatten is a function which is used to collapse multisets of lists into a multiset, so for example { (1, 2), (3, 4) } becomes { 1, 2, 3, 4 }.
Definition: Flatten
The Flatten(M) function takes a multiset of lists, M {(L1, L2, ...), ...}, and returns the multiset given by the multiset union of { Li | L in M } for all i in L.
Count is a SPARQL set function which counts the number of times a given expression has a bound, and non-error value with the aggregate group.
Definition: Count
Count(M, err) = card[Flatten(M)]
Sum is a SPARQL set function that will return the numeric value obtained
by summing the values within the aggregate group. Type promotion happens as per
the op:numeric-add function, applied transitively,(see definition below) so the
value of SUM(?x), in an aggregate group where ?x has values 1 (integer), 2.0e0
(float), and 3.0 (decimal) will be 6.0 (float).
Definition: Sum
The Sum set function is used by the SUM aggregate in the syntax.
Sum(M, err) = Sum(ToList(Flatten(M))).
Sum(S) = op:numeric-add(S0, Sum(S1..n)) when |S| > 1
Sum(S) = op:numeric-add(S0, 0) when |S| = 1
Sum(S) = 0 when |S| = 0
In this way, Sum({1, 2, 3}) = op:numeric-add(op:numeric-add(1, 0), op:numeric-add(2, 3)).
The Avg set function calculates the average value for an expression over
a group. It is defined in terms of Sum and Count.
Definition: Avg
Avg(M, err) = 0, where Count(M, err) = 0
Avg(M, err) = Sum(M, err) / Count(M, err), where Count(M, err) > 0
For example, Avg({1, 2, 3}) = Sum({1, 2, 3})/Count({1, 2, 3}) = 6/3 = 2.
Min and Max are SPARQL set functions that return the minimum and maximum value from a group respectively.
This makes use of the SPARQL ORDER BY ordering definition, to allow ordering over arbitrarily typed expressions.
Definition: Min
Min(M, err) = Min(ToList(Flatten(M))).
The flattened multiset of values passed as an argument is converted to a sequence S, this sequence is ordered as per the ORDER BY ASC clause.
Min(S) = S0
Definition: Max
Max(M, err) = Max(ToList(Flatten(M))).
The multiset of values passed as an argument is converted to a sequence S, this sequence is ordered as per the ORDER BY DESC clause.
Max(S) = S0
GroupConcat is a set function which performs a string concatenation
across the values of an expression with a group. The order of the strings is
not specified. The separator character used in the concatenation may be given
with the scalar argument SEPARATOR.
Definition: GroupConcat
If the "separator" scalar argument is absent from GROUP_CONCAT then it is taken to be the “space” character, unicode codepoint U+0020.
The multiset of values passed as an argument is converted to a sequence S.
GroupConcat(M, err, scalar) = GroupConcat(ToList(Flatten(M), scalar)
GroupConcat(S, scalar) = fn:string-join(S, scalar("separator"))
Note that fn:string-join denotes the XPath function string-join
For example, GroupConcat({"a", "b", "c"}, {"separator" → "."}) = "a.b.c".
Sample is a set function which returns an arbitrary value from the
multiset passed to it.
Definition: Sample
Sample(M, err) = Sample(Flatten(M))
Sample(M) = v, where v in M
For example, given Sample({"a", "b", "c"}), "a", "b", and "c" are all valid return values. Note that Sample() is not required to be deterministic for a given input, the only restriction is that the output value must be present in the input multiset.
10.2.3 Mapping from Abstract Syntax to Algebra
Example:
SELECT (SUM(?val) AS ?sum)
PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>
WHERE {
?a rdf:value ?val .
} GROUP BY ?aThe SUM expression becomes Aggregation((?val), Sum, (), BGP(?a
rdf:value ?val)).
In general the aggregate expression
AGG(exprlist ; scalarvals) ... GROUP BY grouplist
becomes Aggregation(exprlist, Agg, scalarvals, BGP).
Joining Aggregate Values
In order to project values from (sub-)queries using aggregate values, a Solution Multiset is constructed where each solution comprises the result of the Aggregate functions which share a key.
Definition: AggregateJoin
Given a list of aggregations, A = (A1, A2, ...) we produce a solution sequence using the AggregateJoin function:
AggregateJoin(A) = { { aggi → range(Ai) } | dom(Ai) = k, k in set-union(dom(A)) }
For example, if we have two aggregations:
A1 = { (1,3) → 5, (7,9) → 11 }
A2 = { (1,3) → 6, (7,9) → 12 }
AggregateJoin(A) = {
{ agg1 → 5, agg2 → 6 },
{ agg1 → 11, agg2 → 12 }
}