XSB as an efficient deductive database engine

TLDR

XSB originates from Prolog but addresses Prolog’s deficiencies as a database system. This paper presents XSB as an in‑memory deductive database engine. XSB employs tabling (a bottom‑up extension) and a meta‑interpreter for non‑stratified programs to serve as an efficient query engine. Tabling enables XSB to compute all modularly stratified Datalog programs finitely with polynomial data complexity, while its enhanced indexing and HiLog syntax provide improved performance and flexible data modelling.

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)[4], 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 [2], lends it flexibility for data modelling.