We present a bottom-up algorithm for the computation of the well-founded model of non-disjunctive logic programs. Our method is based on the elementary program transformation studied by BRASS and DIX [BD95b]. However, their "residual program" can grow to exponential size, whereas for function-free programs our "program remainder" is always polynomial in the size, i.e. the number of tuples, of the extensional database (EDB). As in the SLG-resolution of CHEN and WARREN [CW93, CSW95, CW96], we do not only delay negative but also positive literals if they depend on delayed negative literals. When disregarding goal-directness, which needs additional concepts, our approach can be seen as a simplified bottom-up version of SLG-resolution applicable to rage-restricted Datalog programs. Since our approach is also closely related to the alternating fixpoint procedure [VG89, VG93], it can possibly serve as a basis for an integration of the resolution-based, fixpoint-based, and transformation-based evaluation methods.
Ulrike Peiker, Martin Griebl