In logic programming it is often the case that one wants to compare the various solutions to a single goal with each other. For example, we may have an employee relation that stores employee names, their departments and salaries, and we want to find, say, the total salary of all the employees. This requires querying the employee relation to retrieve the salaries and then combining all the solutions to find their sum.
Prolog provides several general predicates, the so-called all-solutions predicates, to allow a programmer to do such things. The all-solution predicates accumulate all the solutions to a particular goal into a list. The programmer can then use normal recursive programs to compute the desired function over that list, for example, sum of the elements.
To be concrete, to find the total of the salaries, a prolog programmer could write:
:- bagof(Sal,(Name,Dept)^employee(Name,Dept,Sal),Salaries),
listsum(Salaries,MaxSal).
The predicate listsum/2 simply takes a list of numbers and
returns their sum. The all-solutions predicate bagof/2 takes a
template, a goal, and returns a list of instantiations of the
template, one for each solution to the goal. In this case, the
template is simply the variable Sal, so we will get back a list
of salaries. The goal is:
(Name,Dept)^employee(Name,Dept,Sal)
The variables in the term before the ^ symbol indicate the
existential variables in the goal. The values of Sal in
successful solutions to the goal are accumulated into a single list,
regardless of the values of the existential variables. In this case,
we want all salary values, regardless of the employee's name or
department. Another possibly interesting alternative query would be:
:- bagof(Sal,(Name)^employee(Name,Dept,Sal),Salaries),
maximum(Salaries,TotalSals).
This query, without the variable Dept being existentially
quantified, groups together solutions that have the same department,
and returns nondeterministically, for each department, the list of
salaries for employees in that department. So this is what one would
get using a ``group by'' query in the database language SQL.
The bagof/3 all-solutions predicate is used here because we
don't want to eliminate duplicate salaries. If two employees have the
same salary, we want to add both numbers; we want the sum of salaries,
not the sum of different salaries.
One computational disadvantage of Prolog's all-solutions predicates is that regardless of the function to be computed over the bag (or set) of solutions, that list must still be created. To accumulate the sum of a set of numbers, it certainly seems inefficient to first construct a list of them and then add them up. Clearly one could just accumulate their sum as they are produced. In XSB if the goal is tabled, the situation is exacerbated, in that the set of solutions is in the table already; building another list of them seems a bit redundant.
XSB, being an extension of Prolog, supports its all-solutions predicates, but it also uses tabling to support several other such predicates, which are described in this chapter.