Click on the title to obtain a gzip-ed PostScript version
of a paper almost identical to the journal version (146K).
Abstract:
SLG resolution uses tabling to evaluate non-floundering normal logic
programs according to the well-founded semantics.
The SLG-WAM, which forms the engine of the XSB system, can compute
in-memory recursive queries an order of magnitude faster than
current deductive databases. At the same time, the SLG-WAM tightly
integrates Prolog code with tabled SLG code, and can execute Prolog
code with minimal overhead compared to the WAM. As a result, the
SLG-WAM brings to logic programming important termination and
complexity properties of deductive databases.
This article describes the architecture of the SLG-WAM for a powerful
class of programs, the class of fixed-order dynamically
stratified programs.
We offer a detailed description of the algorithms, data structures,
and instructions that the SLG-WAM adds to the WAM, and a performance
analysis of engine overhead due to the extensions.