Click on the title to obtain a gzip-ed PostScript version of the paper (70K).
Abstract:
This paper describes the XSB system, and its use as an in-memory deductive
database engine. XSB began from a Prolog foundation, and traditional
Prolog systems are known to have serious deficiencies when
used as database systems. Accordingly, XSB has a fundamental
bottom-up extension, introduced through tabling (or memoing),
which makes it appropriate as an underlying query engine
for deductive database systems. Because it eliminates redundant
computation, the tabling extension makes XSB able to compute all
modularly stratified datalog programs finitely and with polynomial
data complexity. For non-stratified programs, a meta-interpreter with the
same properties is provided. In addition XSB significantly extends and
improves the indexing capabilities over those of standard Prolog.
Finally, its syntactic basis in HiLog, lends it flexibility for data modelling.
The implementation of XSB derives from the WAM, the most common
Prolog engine. XSB inherits the WAM's efficiency and can
take advantage of extensive compiler technology developed for Prolog.
As a result, performance comparisons indicate that XSB is
significantly faster than other deductive database systems for a wide
range of queries and stratified rule sets. XSB is under continuous
development, and version 1.3 is available through anonymous ftp.