Incremental Tabling for Knowledge Representation and Reasoning

ABSTRACT. Resolution-based Knowledge Representation and Reasoning (KRR) systems, such as Flora-2, Silk or Ergo, can scale to tens or hundreds of millions of facts, while supporting reasoning that includes Hilog, inheritance, defeasibility theories, and equality theories. These systems handle the termination and complexity issues that arise from the use of these features by a heavy use of tabling. In fact, such systems table by default all rules defined by users, unless they are simple facts.

Performing dynamic updates within such systems is nearly impossible unless the tables themselves can be made to react to changes. Incremental tabling as implemented in XSB~\cite{Saha06} partially addressed this problem, but the implementation was limited in scope and not always easy to use. In this paper, we describe {\em automatic incremental tabling} which at the semantic level supports updates in the 3-valued well-founded semantics, while guaranteeing full consistency of all tabled queries. Automatic Incremental Tabling also has significant performance improvements over previous implementations, including lazy incremental tabling, and control over the dependency structures used to determine how tables are updated. %Benchmarks indicate that \automatic incremental tabling has major %performance improvements over previous versions of incremental %tabling.