On the optimality of scheduling strategies in subsumption based tabled resolution
Prasad Rao, C. R. Ramakrishnan, I. V. Ramakrishnan · 1998
Subsumption-based tabled logic programming promotes more aggressive reuse of answer tables over variant-based tabling. However resolving subgoals against answers in tabled logic programming may require accessing incomplete answer tables (i.e., more answers remain to be added). In subsumption-based tabling it is far more efficient to retrieve from completed tables. Scheduling strategies promote more frequent usage of such tables by exercising control over access to incomplete tables. Different choices in the control can lead to different sets of proof trees in the search forest produced by tabled resolution. The net effect is that depending on the scheduling strategy used, tabled logic programs under subsumption can exhibit substantial variations in performance. In this paper we establish that for subsumption-basedtabled logic programming an optimal scheduling strategy does not exist -- i.e., they are all incomparable in terms of time and space performance. Subsumption-based tabled reso...