INCREMENTAL ALGORITHMS FOR OPTIMIZING MODEL COMPUTATION BASED ON PARTIAL INSTANTIATION

It has been shown that mixed integer programming methods can effective ly support minimal model, stable model and well-founded model semantic s for ground deductive databases. Recently, a novel approach called pa rtial instantiation has been developed which, when integrated with mix ed integer programming methods, can handle non-ground logic programs. The goal of this paper is to explore how this integrated framework bas ed on partial instantiation can be optimized. In particular, we develo p an incremental algorithm that minimizes repetitive computations. We also develop several optimization techniques to further enhance the ef ficiency of our incremental algorithm. Experimental results indicate t hat our algorithm and optimization techniques can bring about very sig nificant improvement in run-time performance. (C) Elsevier Science Inc ., 1997.