HP Labs Technical Reports

Incremental, Bottom-Up, Well-Founded Deduction

Beach, Brian W.

HPL-91-20

Keyword(s):

Abstract: In this paper we describe an algorithm, called AFP, for the bottom-up execution of logic programs well suited to data-driven applications, where incremental updates to the base relations are propagated through the program to produce updated answers without completely re-executing the program. We show that AFP conforms to the well-founded semantics for general logic programs and that it terminates in polynomial time for DATALOG programs with negation. P/ AFP is based on a modified formulation of well-founded negation that does not rely on computing sets of false atoms, avoiding the instantiation of the entire Herbrand base. AFP solves the two major problems in incremental bottom-up computation, recursion through negation and self-supporting conclusions, by using a counting technique over a two-dimensional representation of time to detect and stop such loops. Its feasibility has been verified with an implementation in Prolog.

Back to Index