Relational Storage Mechanisms for Tabled Logic Programs

Pedro Costa

July 2007

---

Abstract

Logic programming languages, such as Prolog, provide a high-level, declarative approach to programming. Derived from the Horn Clause Logic, this paradigm is based on a simple theorem prover that given a set of assumptions and rules, searches for alternative ways to satisfy queries.
Although a powerful, flexible and well performing tool, a major effort has been made in the past years to increase Prolog's declarativeness and expressiveness. The potential of logic programming has been limited since Prolog's standard evaluation strategy - SLD resolution - is prone to infinite loops and redundant subcomputations. Of all the several proposals that have come forth to overcome this situation, one in particular, known as tabling or memoing, proved to be particularly effective, albeit when are used for applications that deal with huge answer sets, the risk of memory exhaustion is very real. In general, in order to recover some space, programmers have no choice but to arbitrarily select some of the tables for deletion.
With this research, we intend to demonstrate that an alternative approach is possible. Rather than deleting predicate tables, we propose the storage of tabled data in an external relational database system, from where answer subsets may be swiftly recovered whenever subsequent table calls occur, hence avoiding re-computation. To validate our approach, we propose DBTab, an extension of the YapTab tabling system providing engine support for data transactions between the YAP logical engine and the MySQL relational database management system.
The attained results show that DBTab may become an interesting approach when the cost of recalculating tabling tries exceeds the amount of time required to fetch the entire answer-set from the database. The results reinforced our belief that tabling can contribute to expand the range of applications for Logic Programming.

Bibtex

@MastersThesis{costa-msc,
  author =  {P. Costa},
  title =   {{Relational Storage Mechanisms for Tabled Logic Programs}},
  school =  {University of Porto},
  address = {Portugal},
  month =   {July},
  year =    {2007},
  type =    {{MSc Thesis}},
}

Download Thesis

PDF file