Tabled Aggregation

The following shortest path predicate is a modification of the path/2 predicate of Section 5.2:

Exercise 5.4.1 path/3 has a simple declarative meaning: it computes the path between two vertices of a graph along with the cost of the path. Since path/3 is tabled would you expect it to terminate? Try the query ?- path(1,5,X) over the graph provided in the file table_examples.P.

If we could use tabling to compute the path with least cost, or the shortest path, the program would not only omit extraneous information, but it would also terminate. Recall that for simple horn programs, variant-based tabling ensures termination by only returning a given answer A once, and failing on subsequent derivations of A. If this strategy could be extended so that the engine only returned a new answer if it was minimal, termination could be ensured. The XSB predicate, filterReduce(?Pred,+Binary_operator,+Identity,Value), does just this.

Exercise 5.4.2 The use of filterReduce/4 can be seen most easily through an example such as the following, (which uses a closely related predicate filterReduce1/4).

shorter_path(X,Y,C) :- filterReduce1(sp(X,Y),min,infinity,C).

sp(X,Y,C) :- shorter_path(X,Z,C1),
             edge(Z,Y,C2),C is C1 + C2.
sp(X,Y,C) :- edge(X,Y,C).

min(X,Y,Y):- \+ number(X),!.
min(X,Y,X):- \+ number(Y),!.
min(One,Two,Min):- One > Two -> Min = Two ; Min = One.

Note that the library predicate filterReduce1/4 is tabled, so that neither sp/3 nor shorter_path/3 need be tabled. Now try the query shorter_path(1,5,C).

filterReduce1((?Pred,+Binary_operator,+Identity,Value), forms a new predicate out of Pred and Value to get a new predicate to call. Binary_Operator must define a binary function in which the first two arguments determine the third. Id must be the identity of Binary_operator. Value becomes the result of applying Op to all the elements in the table that are variants of Pred. In our case, when a new answer sp(X,Y,C) is derived within filterReduce1/4, the later predicate returns only when C is a shorter path for X and Y than any so far derived.

While shorter_path/4 terminates, it returns non-optimal solutions, and these solutions can in principle be costly -- [22] cites a case in which the shorter path program, which should be less than cubic in the number of vertices in a graph, has exponential complexity because of the non-optimal solutions that are returned. Fortunately, this has an easy solution.

Exercise 5.4.3 The actual shortest_path program has the following definition.

filterReduce(Call,Op,Id,Res) :- filterReduce1(Call,Op,Id,Res), fail.
filterReduce(Call,Op,Id,Res) :- filterReduce1(Call,Op,Id,Res).

shortest_path(X,Y,C) :- filterReduce(sp(X,Y),min,infinity,C).

sp(X,Y,C) :- shortest_path(X,Z,C1),
             edge(Z,Y,C2),C is C1 + C2.
sp(X,Y,C) :- edge(X,Y,C).

min(X,Y,Y):- \+ number(X),!.
min(X,Y,X):- \+ number(Y),!.
min(One,Two,Min):- One > Two -> Min = Two ; Min = One.

Once again try the query shortest_path(1,5,C).

By simply failing out of filterReduce1/4 and then rereading the maximal value from the table, an efficient shortest_path algorithm is derived, whose complexity is roughly cubic in the number or vertices of the graph. This solution is not general for all predicates, but does work for deriving the shortest path. A more general solution is provided in Section 5.4.1.

filterReduce/4 is an extremely useful predicate. It can write database aggregation functions, such as min, max, count, sum, and average. However, it can also be used to implement paraconsistent and quantitative reasoning through Generalized Annotated Programs [29], as detailed in the section on GAPs in Volume 2 of this manual.

Several predicates perform tabled aggregation besides filterReduce/4. One of these is the predicate filterPO1(?Pred,?Preference_structure,+Partial_order). Analogously to filterReduce1/4 if Pred is an n-ary predicate, filterPO/4 forms a (n+1)-ary predicate Pred1 whose last argument is Preference_structure and whose functor and all other arguments are determined by Pred. filterPO(?Pred,?Preference_structure,+Partial_order), then calls Pred1 and for each return of Pred1 fails if there is some answer already in the table for filterPO1/4 such that the first n arguments of Pred in the tabled answer unify with the first n arguments of Pred in the return and whose preference structure (last argument) is preferred to that of the return. A case study in the use of filterPO/4 to construct preference logic grammars can be found in [14].