Deductive databases incorporate Logic Programming inference (forms of SLD resolution) as the
basis for implementing query languages. 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, not run-time. Additionally, we offer an alternative
inferencing procedure based on translating logic to linear programming. This makes
available for research and implementation in deductive databases all the theorems,
algorithms, and software packages that it took the Operations Research community 50 years
to develop. The method keeps the same query language as for disjunctive deductive databases,
only the inferencing procedure changes. The language is purely declarative, independent of
the order of rules in the program,independent of the order in which literals occur in clause
bodies. The technique avoids Prolog's problem of infinite looping. It saves run time by
doing primary inferencing at compile time. It is incremental; processing some rules and
some facts from the database and saving the results puts one in a position to start with
this "save" to process any additional rules and facts added later, losing no true answers
to the queries. Linear programming methods for pure logic problems were already tried out by
Boole. In modern times they were developed by the late R. Jeroslow and, following him, by
J. Hooker and others, as an alternative to Robinson resolution automatic theorem proving in
pure logic. Ours is the first paper on, and implementation of, linear programming inferencing
for queries in deductive databases. All disjunctive clauses, integrity constraints, and
database facts are translated into boolean equations, relaxed to real valued inequations,
then solved by real (or integer) linear programming, the boolean logic answers then being
extracted by "cutting-plane" or some similar process. We give, for the first time, an
implementation which computes models of deductive databases. The first half of this paper
translates logic programming/deductive database problems to linear programming problems for
computing: least models of definite deductive databases, minimal models, and the Generalized
Closed World Assumption of disjunctive deductive databases. Our procedures are sound and
complete. The second half of the paper proposes a query processing system based on linear
programming compilation. We discuss how such a system can be supported efficiently at
run-time by relational database systems. Then we describe our (implemented) prototype
compiler. Finally, we report experimental results using this compiler. These results suggest
that our compilation based linear programming paradigm is a promising approach to practical
implementation of query systems for definite and disjunctive deductive databases.