** Next:** Standard Predicates
** Up:** Tabled Aggregation
** Previous:** Tabled Aggregation
** Contents**
** Index**

##

Local Evaluation

For the shortest path example, simply failing until a minimal answer
was derived and then returning that solution was an effective
technique for computing the shortest path. However, this approach
will not always work. As we have seen in Exercise 5.2.6,
programs can consist of sets of mutually recursive predicates and in
principle these sets can be arbitrarily large. If these computations
are to use tabled aggregation, the approach taken by `
filterReduce/4` will not suffice. To see this, we make the notion of
mutual recursion more precise. A tabled computation can be viewed as
a directed graph, in which there is a link from one non-completed
tabled predicate to a non-completed tabled predicate if
(or is called by . Of course, this graph constantly
changes through an evaluation as resolution proceeds, subgoals are
completed, and so on. Any directed graph can be uniquely partitioned
into a set of maximal * strongly connected components* or SCCs, and
these sets correspond to sets of mutually recursive predicates. The
SCCs then, are reminiscent of the LRD-stratifiedstratification discussed in
Section 5.3.1, except that both positive and negative links
are counted as dependencies. From this view, to optimally compute
tabled aggregation, non-optimal answers from a given subgoal must
be returned within the SCC of , but not outside the SCC. This
action is performed by * Local Scheduling*.

It is illustrative to compare local scheduling to * Batched
Scheduling* the default scheduling of XSB. Batched scheduling returns
answers as they are derived, and resembles Prolog's tuple at a time
scheduling. Local scheduling was shown to be quite efficient in terms
of time and space in [18], and is the fastest
scheduling strategy that we know of for computing a sequence of
answers. The same paper also introduced Local Scheduling, which
computes all answers for each SCC and return only the best answer (or
answers) out of the SCC, when the SCC is completely evaluated --
exactly the thing for tabled aggregation.

XSB can be configured to use local scheduling via the configuration
option ` -enable-local-scheduling` and remaking XSB. This will
not affect the default version of XSB, which will also remain
available.

** Next:** Standard Predicates
** Up:** Tabled Aggregation
** Previous:** Tabled Aggregation
** Contents**
** Index**
*Baoqiu Cui*

*2000-04-23*