Tabling Aggregate Predicates

HiLog provides an elegant way to introduce aggregate operations into
XSB. HiLog allows a user to define named (and parameterized)
sets (or bags). For example, say we have a simple database-like predicate,
`employee(Name,Dept,Sal)`

, which contains a tuple for each
employee in our concern and contains the employee's name, department,
and salary. From this predicate we can construct a set, or bag
really, that contains all the salaries of employees in the relation:

:- hilog salaries. salaries(Sal) :- employee(_Name,_Dept,Sal).So

`salaries`

is the name of a unary predicate that is true of
all salaries, or rather is the name of a `bagSum`

which can be used to
sum up the elements in a named bag. So given the definition of the
HiLog predicate `salaries/1`

above, we can get the sum of all the
salaries with:
:- bagSum(salaries,TotalSals).The first argument to

`bagSum`

is the name of a bag, and the
second is bound to the sum of the elements in the bag.
We can also do a ``group by'' to get total salaries within departments
as follows. We define a parameterized predicate, `sals(Dept)`

,
to be the bag of salaries of employees in department `Dept`

, as
follows:

sals(Dept)(Sal) :- employee(_Name,Dept,Sal).This rule says that

`Sal`

is in the bag named `sals(Dept)`

if there is an employee with some name who works in department
`Dept`

and has salary `Sal`

.
Now with this definition, we can define a predicate,
`deptPayroll/2`

, that associates with each department the sum of
all the salaries of employees in that department:

deptPayroll(Dept,Payroll) :- bagSum(sals(Dept),Payroll).

XSB provides analogous aggregate operators, described below, to
compute the minimum, maximum, count, and average, of a bag,
respectively. These predicates are all defined using a more basic
predicate `bagReduce/4`

.

`bagReduce(?SetPred,?Arg,+Op,+Id)`-
*HiLog,Tabling* `filterReduce(?SetPred,?Arg,+Op,+Id)`-
*Tabling*

`SetPred`must be a HiLog set specification, i.e., a unary HiLog predicate.`Op`must be a Hilog operation, i.e., a 3-ary HiLog predicate that defines an associative operator. The predicate must define a binary function in which the first two arguments determine the third.`Id`must be the identity of the operator.`bagReduce`returns with`Arg`bound to the ``reduce'' of the elements of the bag determined by`SetPred`under the operation`Op`. I.e.,`Arg`becomes the result of applying the operator to all the elements in the bag that unify with`SetPred`. See the`bagSum`operator below to see an example of`bagReduce`'s use.`filterReduce/4`acts as`bagReduce/4`with two differences. First, it does not depend on HiLog, so that`filterReduce/4`will be more robust especially when XSB's module system is used. In addition,`filterReduce/4`aggregates solutions to`Pred`using a variance rather than unification. An example of the use of`filterReduce/4`is given in Chapter 5. `bagPO(?SetPred,?Arg,+Order)`-
*HiLog,Tabling* `filterPO(?SetPred,?Arg,+Order)`-
*Tabling*

`SetPred`must be a HiLog set specification, i.e., a unary HiLog predicate.`Order`must be a binary Hilog relation that defines a partial order.`bagPO`returns nondeterministically with`Arg`bound to the maximal elements, under`Order`, of the bag`SetPred`.`bagPO/3`can be used with`Order`being subsumption to reduce a set of answers and keep only the most general answers.See the

`bagMax`operator below to see an example of`bagPO`'s use.`filterPO/3`acts as`bagPO/3`with the single difference that it does not depend on HiLog, so that`filterPO/3`will be more robust especially when XSB's module system is used. `filterPO(#Pred,+Order)`-
*Tabling*

`filterPO(#Pred,+Order)`succeds only for a solution of`Pred`for which there is no solution to`Pred`such that`Order(,)`.Example:

For the following program

`:- table p/2.``b(1,2).``p(1,3).``b(1,1).``prefer(b(X,X),b(X,Y)):- X = Y.``?- filterPO(b(X,Y)`*X = 1,Y = 1*. `bagMax(?SetPred,?Arg)`-
*HiLog,Tabling*

`SetPred`must be a HiLog set specification, i.e., a unary HiLog predicate.`bagMax`returns with`Arg`bound to the maximum element (under the Prolog term ordering) of the set`SetPred`. To use this predicate, it must be imported from aggregs, and you must give the following definitions in the main module`usermod`::- hilog maximum. maximum(X,Y,Z) :- X @< Y -> Z=Y ; Z=X.

(These decarations are necessary because of a current limitation in how HiLog predicates can be used. This requirement will be lifted in a future release.) With this definition,`bagMax/2`can be (and is) defined as follows:bagMax(Call,Var) :- bagReduce(Call,Var,maximum,_).

(Where variables are minimal in the term ordering.)Another possible definition of

`bagMax/2`would be::- hilog lt. lt(X,Y) :- X @< Y. bagMax(Call,Var) :- bagPO(Call,Var,lt).

This definition would work, but it is slightly less efficient than the previous definition since it is known that`bagMax`is deterministic. `bagMin(?SetPred,?Arg)`-
*HiLog,Tabling*

`SetPred`must be a HiLog set specification, i.e., a unary HiLog predicate.`bagMin`returns with`Arg`bound to the minimum element (under the Prolog term ordering) of the set`SetPred`. To use this predicate, it must be imported from aggregs, and you must give the following definitions in the main module`usermod`::- hilog minimum. minimum(X,Y,Z) :- X @< Y -> Z=X ; Z=Y.

(These decarations are necessary because of a current limitation in how HiLog predicates can be used. This requirement will be lifted in a future release.) With this definition,`bagMin/2`can be (and is) defined as:bagMin(Call,Var) :- bagReduce(Call,Var,minimum,zz(zz)).

(where structures are the largest elements in the term ordering.) `bagSum(?SetPred,?Arg)`-
*HiLog,Tabling*

`SetPred`must be a HiLog set specification, i.e., a unary HiLog predicate.`bagSum`returns with`Arg`bound to the sum of the elements of the set`SetPred`. To use this predicate, it must be imported from aggregs, and you must give the following definitions in the main module`usermod`::- hilog sum. sum(X,Y,Z) :- Z is X+Y.

(These decarations are necessary because of a current limitation in how HiLog predicates can be used. This requirement will be lifted in a future release.) With this definition,`bagSum/2`can be (and is) defined as:bagSum(Call,Var) :- bagReduce(Call,Var,sum,0).

`bagCount(?SetPred,?Arg)`-

HiLog,Tabling`SetPred`must be a HiLog set specification, i.e., a unary HiLog predicate.`bagCount`returns with`Arg`bound to the count (i.e., number) of elements of the set`SetPred`. To use this predicate, it must be imported from aggregs, and you must give the following definitions in the main module`usermod`::- hilog successor. successor(X,_Y,Z) :- Z is X+1.

(These decarations are necessary because of a current limitation in how HiLog predicates can be used. This requirement will be lifted in a future release.) With this definition,`bagCount/2`can be (and is) defined as:bagCount(Call,Var) :- bagReduce(Call,Var,successor,0).

`bagAvg(?SetPred,?Arg)`-
*HiLog,Tabling*

`SetPred`must be a HiLog set specification, i.e., a unary HiLog predicate.`bagAvg`returns with`Arg`bound to the average (i.e., mean) of elements of the set`SetPred`. To use this predicate, it must be imported from aggregs, and you must give the following definitions in the main module`usermod`::- hilog sumcount. sumcount([S|C],X,[S1|C1]) :- S1 is S+X, C1 is C+1.

(These decarations are necessary because of a current limitation in how HiLog predicates can be used. This requirement will be lifted in a future release.) With this definition,`bagAvg/2`can be (and is) defined as:bagAvg(Call,Avg) :- bagReduce(Call,[Sum|Count],sumcount,[0|0]), Avg is Sum/Count.