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 $P1$ to a non-completed tabled predicate $P2$ if $P2$ (or $tnot(P2))$ is called by $P1$. 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 $S$ must be returned within the SCC of $S$, 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.