Efficient Support for Incomplete and Complete Tables in the YapTab Tabling System

Ricardo Rocha

August 2006

---

Abstract

Most of the recent proposals in tabling technology were designed as a means to improve some practical deficiencies of current tabling execution models. The discussion we address in this paper was also motivated by practical deficiencies we encountered, in particular, when dealing with incomplete and complete tables. Incomplete tables became a problem when, as a result of a pruning operation, the computational state of a tabled subgoal is removed from the execution stacks before being completed. On the other hand, complete tables became a problem when the system runs out of memory. To handle incomplete tables, we propose an approach that avoids re-computation when the already stored answers are enough to evaluate a repeated call. To handle complete tables, we propose a memory management strategy that automatically recovers space from the tables when the system runs out of memory. To validate our proposals, we have implemented them in the YapTab tabling system as an elegant extension of the original design.

Bibtex

@InProceedings{rocha-ciclops06,
  author =    {R. Rocha},
  title =     {{Efficient Support for Incomplete and Complete Tables in the YapTab Tabling System}},
  booktitle = {Proceedings of the 6th Colloquium on Implementation of Constraint and LOgic Programming
               Systems (CICLOPS 2006)},
  pages =     {2--17},
  editor =    {E. Pontelli and Hai-Feng Guo},
  month =     {August},
  year =      {2006},
  address =   {Seattle, Washington, USA},
}

Download Paper

PDF file

Download Slides

PDF file