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