Aggregation operators

Aggregation operators evaluate a given function over a set of facts. They can be used in expressions that are the RHS of assignments; this means that, unlike single fact-operators, they cannot be used in conditions.

The supported aggregations are:

msum

monotonic increasing summation

mprod

monotonic decreasing product

munion

monotonic increasing set union

monotonic minimum

monotonic maximum

monotonic count

minimum

maximum

count

Note that aggregates are only implemented for floats.

A rule with an assignment using an aggregation operator has the general form:

q(K1, K2, Kn, J) :- body, J = maggr(x, <C1,…,Cm>)

Where:

K1, …, Kn are zero or more group by arguments.
body is the rule body.
maggr is a placeholder for an aggregation function (mmin, mmax, msum, mprod).
C1, …, Cm are zero or more variables of the body, called contributor arguments (with Ci ≠ Kj, 1 ≤ i ≤ m, 1 ≤ j ≤ n).
x is a constant, a body variable, or an expression containing only single-fact operators.

Contributors C1, …, Cm are not present in munion, mmax and mmin.

For each distinct n-tuple of K1, …, Kn, a monotonic decreasing (increasing) aggregate function maggr maps an input multi-set of vectors G, each of the form gi = (C1,…,Cm,xi) into a set D of values, such that xi is in D if xi is less (greater) than the previously observed value for the sub-vector of contributors (C1, …, Cm). Such aggregation functions are monotonic with respect to set containment and can be used in Vadalog together with recursive rules to calculate aggregates without resorting to stratification (separation of the program into ordered levels based on the dependencies between rules).

During the execution of a program:

The aggregation memorizes the current minimum (or maximum) value of x for each vector (C1, …, Cm).
For each activation of a rule with the monotonic aggregation, an updated value for the group selected by K1, …, Kn is calculated by combining all the values in D for the various vectors of contributors.
The combination depends on the semantics of maggr (e.g., minimum, maximum, sum, product, count) and is calculated by memorizing a current aggregate, updated with new contributions from the sequence of rule activations.

Assumption:

If a position pos in a head for predicate p is calculated with an aggregate function, whenever a head for p appears in any other rule, pos must be existentially quantified and calculated with the same aggregate function.

This assumption ensures the homogeneity of the facts with existentially aggregated functions.

`msum`

Monotonic increasing summation.

msum(X, <C1,...,Cm>)

Where:

X is the value to be summed.
<C1,…,Cm> are zero or more variables of the body, which are called contributor arguments.

Example

s(0.1, 2, "a").
s(0.2, 2, "a").
s(0.5, 3, "a").
s(0.6, 4, "b").
s(0.5, 5, "b").

f(J, Z) :- s(X, Y, Z), J = msum(X, <Y>).
@output("f").

Expected results

f(0.1, "a")
f(0.2, "a")
f(0.7, "a")
f(0.6, "b")
f(1.1, "b")

`mprod`

Monotonic decreasing product.

mprod(X, <C1,...,Cm>)

Where:

X is the value to be multiplied.
<C1,…,Cm> are zero or more variables of the body, which are called contributor arguments.

Example

s(0.1, 2, "a").
s(0.2, 2, "a").
s(0.5, 3, "a").
s(0.6, 4, "b").
s(0.5, 5, "b").

f(J, Z) :- s(X, Y, Z), J = mprod(X, <Y>).
@output("f").

Expected results

f(0.1, "a")
f(0.1, "a")
f(0.05, "a")
f(0.6, "b")
f(0.3, "b")

`munion`

Monotonic increasing set union.

munion(X)

Where:

X is the set to be united.

Example

s({1, 2}, 2, "a").
s({3, 4}, 2, "a").
s({5, 6}, 3, "a").
s({7, 8}, 4, "b").
s({9, 10}, 5, "b").

f(J, Z) :- s(X, Y, Z), J = munion(X).
@output("f").

Expected results

f({1, 2}, "a")
f({1, 2, 3, 4}, "a")
f({1, 2, 3, 4, 5, 6}, "a")
f({7, 8}, "b")
f({7, 8, 9, 10}, "b")

`mmin`

Monotonic minimum.

mmin(X)

Where:

X is the value to find the minimum of.

Example

s(0.1, 2, "a").
s(0.2, 2, "a").
s(0.5, 3, "a").
s(0.6, 4, "b").
s(0.5, 5, "b").

f(J, Z) :- s(X, Y, Z), J = mmin(X).
@output("f").

Expected results

f(0.1, "a")
f(0.1, "a")
f(0.1, "a")
f(0.6, "b")
f(0.5, "b")

`mmax`

Monotonic maximum.

mmax(X)

Where:

X is the value to find the maximum of.

Example

s(0.1, 2, "a").
s(0.2, 2, "a").
s(0.5, 3, "a").
s(0.6, 4, "b").
s(0.5, 5, "b").

f(J, Z) :- s(X, Y, Z), J = mmax(X).
@output("f").

Expected results

f(0.1, "a")
f(0.2, "a")
f(0.5, "a")
f(0.6, "b")
f(0.6, "b")

`mcount`

Monotonic count.

mcount(X, <C1,...,Cm>)

Where:

X is the value to count.
<C1,…,Cm> are zero or more variables of the body, which are called contributor arguments.

Example

s(0.1, 2, "a").
s(0.2, 2, "a").
s(0.5, 3, "a").
s(0.6, 4, "b").
s(0.5, 5, "b").

f(J, Z) :- s(X, Y, Z), J = mcount(X, <Y>).
@output("f").

Expected results

f(1, "a")
f(1, "a")
f(2, "a")
f(1, "b")
f(2, "b")

`min`

Minimum.

min(X)

Where:

X is the value to find the minimum of.

Example

b(1, 2).
b(1, 3).
b(2, 5).
b(2, 7).

h(X, Z) :- b(X, Y), Z = min(Y), X > 0.
@output("h").

Expected results

h(1, 2)
h(2, 5)

`max`

Maximum.

max(X)

Where:

X is the value to find the maximum of.

Example

b(1, 2).
b(1, 3).
b(2, 5).
b(2, 7).

h(X, Z) :- b(X, Y), Z = max(Y), X > 0.
@output("h").

Expected results

h(1, 3)
h(2, 7)

`count`

Count.

count(X)

Where:

X is the value to count.

Example

b(1, 2).
b(1, 3).
b(2, 5).
b(2, 7).
b(2, 9).

h(X, Z) :- b(X, Y), Z = count(Y), X > 0.
@output("h").
@relaxedSafety.

Expected results

h(1, 2)
h(2, 3)