Ongoing Research Seminar
Friday October 13, 1995

Terrance Swift
Tabling, Search, and Negation

Tabled evaluation can serve as a means to extend logic programming beyond its traditional role as a programming language, so that it can incorporate capabilities of databases and non-monotonic reasoning. This talk describes in broad detail how such an incorporation is done in the context of the XSB system. In the first case, tabling adds bottom-up evaluation to logic programming, and with it the complexity and termination properties expected by databases. In addition, by controlling the search strategy of a tabled evaluation, evaluations can be executed in a set-at-a-time manner that is suitable for disk-resident data. In terms of negation, tabling can evaluate programs according to the Well-Founded Semantics, which has been widely used to model the semantics of negation in logic programming. This semantics is important because the Well-Founded (partial) model of a program is skeptical in the sense that it is the intersection of all consistent models of a program. This skepticism makes the well-founded model a natural starting point for systems which seek to evaluate according to other negation semantics. An overview of SLG, a resolution-based method for evaluating the Well-Founded Semantics is given, along with preliminary results on XSB engine efficiency for set-at-a-time evaluation and for programs with negation.