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 bag of all salaries. It is a bag since it may contain the same salary multiple times. XSB provides a predicate 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 $Pred\theta$ of Pred for which there is no solution $Pred\eta$ to Pred such that Order($Pred\eta$,$Pred\theta$).

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.

the query

?- filterPO(b(X,Y)

will succeed only with the binding 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.