5.2.2 Table Scheduling Strategies

¶ Recall that SLD resolution works by selecting a goal from a list of goals to be proved, and selecting a program clause $C$ to resolve against that goal. During resolution of a top level goal $G$, if the list of unresolved goals becomes empty, $G$ succeeds, while if there is no program clause to resolve against the selected goal from the list resolution against $G$ fails. In Prolog clauses are selected in the order they are asserted, while literals are selected in a left-to-right selection strategy. Other strategies are possible for SLD, and in fact completeness of SLD for definite programs depends on a non-fixed literal selection strategy. This is why Prolog, which has a fixed literal selection strategy is not complete for definite programs, even when they have bounded term-depth.

Because tabling uses program clause resolution, the two parameters of clause selection and literal selection also apply to tabling. Tabling makes use of a dynamic literal selection strategy for certain non-stratified programs (via the delaying mechanism described in Section 5.3.2), but uses the same left-to-right literal selection strategy as Prolog for definite programs. However, in tabling there is also a choice of when to return derived answers to subgoals that consume these answers. While full discussion of scheduling strategies for tabling is not covered here (see [26]) we discuss two scheduling strategies that have been implemented for XSB Version 3.0 ^5.4.

• Local Scheduling Local Scheduling depends on the notion of a subgoal dependency graph. For the state of a tabled evaluation, a non-completed tabled subgoal $S_1$ directly depends on a non-completed subgoal $S_2$ when $S_2$ is in the SLG tree for $S_1$ - that is when $S_2$ is called by $S_1$ without any intervening tabled predicate. The edges of the subgoal dependency graph are then these direct dependency relations, so that the subgoal dependency graph is directed. As mentioned, the subgoal dependency graph reflects a given state of a tabled evaluation and so may changed as the evaluation proceeds, as new tabled subgoals are encountered, or encountered in different contexts, as tables complete, and so on. As with any directed graph, the subgoal dependency graph can be divided up into strongly connected components, consisting of tabled subgoals that depend on one another. Local scheduling then fully evaluates each maximal SCC (a SCC that does not depend on another SCC) before returning answers to any subgoal outside of the SCC ^5.5.

• Batched Scheduling Unlike Local Scheduling, Batched Scheduling allows answers to be returned outside of a maximal SCC as they are derived, and thus resembles Prolog's tuple at a time scheduling.

Both Local and Batched Scheduling have their advantages, and we list points of comparison.

• Time for left recursion Batched Scheduling is somewhat faster than Local Scheduling for left recursion as Local Scheduling imposes overhead to prevent answers from being returned outside of a maximal SCC.

• Time to first answer Because Batched Scheduling returns answers out of an SCC eagerly, it is faster to derive the first answer to a tabled predicate.

• Stack space Local evaluation generally requires less space than batched evaluation as it fully explores a maximal SCC, completes the SCC's subgoals, reclaims space, and then moves on to a new SCC.

• Integration with cuts As discussed in Exercise 5.2.6 and throughout Section 5.2.3, Local Scheduling integrates better with cuts, although this is partly because tabled subgoals may be fully evaluated before the cut takes effect.

• Efficiency for call subsumption Because Local Evaluation completes tables earlier than Batched Evaluation it may be faster for some uses of call subsumption, as subsumed calls can make use of completed subsuming tables.

• Negation and tabled aggregation As will be shown below, Local Scheduling is superior for tabled aggregation as only optimal answers are returned out of a maximal SCC. Local Scheduling also can be more efficient for non-stratified negation as it may allow delayed answers that are later simplified away to avoid being propagated.

On the whole, advantages of Local Scheduling outweigh the advantages of Batched Scheduling, and for this reason Local Scheduling is the default scheduling strategy for Version 3.0 of XSB. XSB can be configured to use batched scheduling via the configuration option -enable-batched-scheduling and remaking XSB. This will not affect the default version of XSB, which will also remain available.