5.2.1.0.2 Determining Call Similarity via Subsumption

Call similarity can also be based on subsumption. A term $T_1$ subsumes a term $T_2$ if $T_2$ is more specific than $T_1$ ^5.3. Furthermore, we say that $T_1$ properly subsumes $T_2$ if $T_2$ is not a variant of $T_1$. Under subsumption-based tabling, when a tabled call $C$ is issued, a search is performed for a table entry containing a subsuming subgoal $S$. Notice that, if such an entry exists, then its answer set ${\cal A}$ logically contains all the solutions to satisfy $C$. The subset of answers ${\cal A}' \subseteq {\cal A}$ which unify with $C$ are said to be relevant to $C$. Likewise, upon the derivation of an answer $A$ for a producing subgoal $S$, $A$ is inserted into the answer set ${\cal A}$ of $S$ if and only if $A$ is not subsumed by some answer $A'$ already present in ${\cal A}$.

Notice that subsumption-based tabling permits greater reuse of computed results, thus avoiding even more program resolution, and thereby can lead to time and space performances superior to variant-based tabling. However, there is a downside to this paradigm. First of all, subsumptively tabled predicates do not interact well with certain Prolog constructs with which variant-tabled predicates can (see Example 5.2.4 below). Further, in the current implementation of subsumption-based tabling, subsumptive predicates may not take part in negative computations which result in the delay of a literal containing a subsumptive subgoal (see Section 12.1). This requires subcomputations in which subsumptive predicates take part to be LRD-stratified (see Section 5.3.2).

Example 5.2.1   The terms $T_1$: p(f(Y),X,1) and $T_2$: p(f(Z),U,1) are variants as one can be made to look like the other by a renaming of the variables. Therefore, each subsumes the other.
The term $t_3$: p(f(Y),X,1) subsumes the term $t_4$: p(f(Z),Z,1). However, they are not variants. Hence $t_3$ properly subsumes $t_4$.$\Box$

The above examples show how a variant-based tabled evaluation can reduce certain redundant subcomputations over SLD. However, even more redundancy can be eliminated, as the following example shows.

Exercise 5.2.5   Begin by abolishing all tables in XSB, and then type the following query

	 ?- abolish_all_tables.
         ?- path(X,Y), fail.

Notice that only a single table entry is created during the evaluation of this query. You can check that this is the case by invoking the following query

         ?- get_calls_for_table(path/2,Call).

Now evaluate the query

         ?- path(1,5), fail.

and again check the subgoals in the table. Notice that two more have been added. Further notice that these new subgoals are subsumed by that of the original entry. Correspondingly, the answers derived for these newer subgoals are already present in the original entry. You can check the answers contained in a table entry by invoking get_returns_for_call/2 on a tabled subgoal. For example:

         ?- get_returns_for_call(p(1,_),Answer).

Compare these answers to those of p(X,Y) and p(1,5). Notice that the same answer can, and in this case does, appear in multiple table entries.

Now, let's again abolish all the tables and change the evaluation strategy of path/2 to use subsumption.

	 ?- abolish_all_tables.
         ?- use_subsumptive_tabling path/2.

And re-perform the first few queries:

         ?- path(X,Y),fail.
	 ?- get_calls_for_table(path/2,Call).
	 ?- path(1,5).
	 ?- get_calls_for_table(path/2,Call).

Notice that this time the table has not changed! Only a single entry is present, that for the original query p(X,Y).

When using subsumption-based tabling, XSB is able to recognize a greater range of ``redundant'' queries and thereby make greater use of previously computed answers. The result is that less program resolution is performed and less redundancy is present in the table. However, subsumption is not a panacea. The elimination of redundant answers depends upon the presence of a subsuming subgoal in the table when the call to p(1,5) is made. If the order of these queries were reversed, one would find that the same entries would be present in this table as the one constructed under variant-based evaluation.