Tabled Aggregation

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

:- table path/3. path(X,Y,C) :- path(X,Z,C1), edge(Z,Y,C2), C is C1 + C2. path(X,Y,C) :- edge(X,Y,C). |

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 once, and failing on subsequent derivations of . 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.

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. |

` 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 --
[18] 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.

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. |

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
[23], 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)`. Analoguosly
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 [10].