AN ABSTRACT MACHINE FOR TABLED EXECUTION OF FIXED-ORDER STRATIFIED LOGIC PROGRAMS

SLG resolution uses tabling to evaluate nonfloundering normal logic pr ograms according to the well-founded semantics. The SLG-WAM, which for ms the engine of the XSB system, can compute in-memory recursive queri es an order of magnitude faster than current deductive databases. At t he same time, the SLG-WAM tightly integrates Prolog code with tabled S LG code, and executes Prolog code with minimal overhead compared to th e WAM. As a result, the SLG-WAM brings to logic programming important termination and complexity properties of deductive databases. This art icle describes the architecture of the SLG-WAM for a powerful class of programs, the class of Fixed-order dynamically stratified programs. W e offer a detailed description of the algorithms, data structures, and instructions that the SLG-WAM adds to the WAM, and a performance anal ysis of engine overhead due to the extensions.