Incremental Algorithms for Optimizing Model

Computation Based on Partial Instantiation?

Raymond T. Ngy and Xiaomei Tian

Department of Computer Science

University of British Columbia

Vancouver, B.C., V6T 1Z4,

Canada.

Abstract

It has been shown that mixed integer programming methods can effectively support minimal model, stable model and well-founded model semantics for ground deductive databases. Recently, a novel approach called partial instantiation has been developed which, when integrated with mixed integer programming methods, can handle non-ground logic programs. The goal of this paper is to explore how this integrated framework based on partial instantiation can be optimized. In particular, we develop an incremental algorithm that minimizes repetitive computations. We also develop several optimization techniques to further enhance the efficiency of our incremental algorithm. Experimental results indicate that our algorithm and optimization techniques can bring about very significant improvement in run-time performance.

keywords: incremental computation, mixed integer programming, logic programs

1 Introduction

Very active research in the past decade has led to the development of numerous methods for evaluating deductive databases and logic programs. Algorithms, such as magic sets and counting methods, have proven to be very successful for definite and stratified deductive databases [1, 2]. During the past few years, however, several new semantics for disjunctive programs and programs with negations, such as minimal models, stable models and wellfounded models [18, 12, 22], have been proposed and widely studied. Recently, it has been shown that mixed integer programming methods can be used to provide a general and rather effective computational paradigm for those semantics [3, 4, 20].

?Research partially sponsored by NSERC Grants OGP0138055 and STR0134419.
yPerson handling correspondence. Email: [email protected]