Computing Circumscriptive Databases, Part I: Theory and Algorithms

this paper, we have adopted the view of model-theoretic circumscription (cf. Etherington [15], Horty [22]) which is quite well-known in the literature [40] and we restrict interest only to Herbrand pre-interpretations. Notwithstanding the computational complexity of circumscription, algorithms still need to be developed to compute circumscription. It is often true that algorithms that have poor worst-case complexities may work well in practice. For example, experimental results indicate that our prototype implementations for linear programming based computations of monotonic databases [6], are more efficient in practice than Prolog. Precise details of the experiments may be found in [6]. In a similar vein, the precise efficiency of our techniques for computing circumscription can only be judged after implementing a prototype system and carrying out detailed experimentation with the implementation. We are currently developing such a prototype implementation for computing circumscription. The details of the implementation and experimental results reporting on the precise efficiency of our optimizations will be reported in Part II of this series of papers[13]. Preliminary experimental results indicate that (1) in Algorithm 1 and the analogous algorithms for computing parallel and prioritized circumscription, most of the time is spent around the first iteration of the loop, and (2) the compaction methods yield significant savings in time, and (3) a concept called "locales" for splitting the database into manageable chunks based on dependency analysis yields significant savings in the time required for compilation. However, these experimental results are still in a very preliminary stage, and we expect that it will be a few months before more reliable statistics are obtained..