next up previous contents index
Next: Cuts and Tabling Up: Tabling in Definite Programs Previous: Tabling in Definite Programs   Contents   Index

Variant and Subsumptive Tabling

The above description gives the general idea of how tabling affects definite programs but is imprecise on certain points. In XSB, a subgoal subgoals $S_2$ can use a table from $S_1$ if $S_1$ is a variant of $S_2$, that is, if $S_1$ and $S_2$ are the same up to variable renaming. Other tabling strategies may allow $S_2$ to use the table of $S_1$ if $S_2$ not more general than $S_1$, or $S_2$ is subsumed by $S_1$:

Example 5.2.1   The terms p(f(Y),X,1) and p(f(Z),U,1) are variants, but p(f(Y),X,1) and p(f(Z),Z,1) are not. In fact, the former subsumes the latter.

Just as a subsumption or variance relation can be used to decide when one subgoal can use the table of another, the two relations can be used to determine when an answer should be returned. In XSB's engine, a derived answer $A$ will be considered new and returned to a subgoal $S$ only if $A$ is not a variant of some other previously derived answer for $S$. In Version 2.2 of XSB, subgoal subsumption is not supported: although work on an engine that includes subgoal subsumption is nearing completion. Answer subsumption, however, can be flexibly programmed as discussed in Section 5.4 5.1.


next up previous contents index
Next: Cuts and Tabling Up: Tabling in Definite Programs Previous: Tabling in Definite Programs   Contents   Index
Baoqiu Cui
2000-04-23