Variant-Based Tabled Evaluation

The first measure determines whether two terms are variants -- that is, if they can be made identical through variable renaming. This is the default tabling method employed by XSB. It was used in the original formulation of SLG resolution [12] for the evaluation of normal logic programs according to the well-founded semantics and interacts well with many of Prolog's extra-logical constructs.

Under variant-based tabling, when a tabled call C is made, a search for a table entry containing a variant subgoal S is performed. Notice that if such an S should exist, then all of its answers are also answers to C, and therefore will be resolved against it. Likewise, when an answer A is derived for a producing subgoal S, A is inserted into the answer set $\cal {A}$ of S if and only if A does not already exist in $\cal {A}$ -- that is, if there is no variant of A already present in $\cal {A}$. The insertion of A, therefore, leads to the return of A to consumers of S. However, the return of only the most general answers to a consumer, referred to as answer subsumption, can be flexibly programmed as discussed in Section 5.4^5.2.