IMPLEMENTING DEDUCTIVE DATABASES BY MIXED-INTEGER PROGRAMMING

Existing and past generations of Prolog compilers have left deduction to run-time and this may account for the poor run-time performance of existing Prolog systems. Our work tries to minimize run-time deduction by shifting the deductive process to compile-time. In addition, we of fer an alternative inferencing procedure based on translating logic to mixed integer programming. This makes available for research and impl ementation in deductive databases, all the theorems, algorithms, and s oftware packages developed by the operations research community over t he past 50 years. The method keeps the same query language as for disj unctive deductive databases, only the inferencing procedure changes. T he language is purely declarative, independent of the order of rules i n the program, and independent of the order in which literals occur in clause bodies, The technique avoids Prolog's problem of infinite loop ing. It saves run-time by doing primary inferencing at compile-time. F urthermore, it is incremental in nature. The first half of this articl e translates disjunctive clauses, integrity constraints, and database facts into Boolean equations, and develops procedures to use mixed int eger programming methods to compute least models of definite deductive databases, and minimal models and the Generalized Closed World Assump tion of disjunctive deductive databases. These procedures are sound an d complete. The second half of the article proposes a query processing system based on mixed integer programming compilation, and describes our (implemented) prototype compiler. Experimental results using this compiler are reported. These results suggest that our compilation-base d mixed integer programming paradigm is a promising approach to practi cal implementation of query systems for definition and disjunctive dat abases.