Journal article
Implementing deductive databases by mixed integer programming
ACM transactions on database systems, Vol.21(2), pp.238-269
06/01/1996
DOI: 10.1145/232616.232691
Abstract
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 offer an alternative inferencing procedure based on translating logic to mixed integer programming. This makes available for research and implementation in deductive databases, all the theorems, algorithms, and software packages developed by the operations research community over the past 50 years. 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, and 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. Furthermore, it is incremental in nature. The first half of this article translates disjunctive clauses, integrity constraints, and database facts into Boolean equations, and develops procedures to use mixed integer programming methods to compute equations, and develops procedures to use mixed integer programming methods to compute equations, and develops procedures to use mixed integer programming methods to compute equations, and develops procedures to use mixed integer programming methods to compute-least models of definite deductive databases, and-minimal models and the Generalized Closed World Assumption of disjunctive databases.
Details
- Title: Subtitle
- Implementing deductive databases by mixed integer programming
- Creators
- Colin Bell - University of IowaAnil Nerode - Cornell UniversityRaymond T. Ng - University of British ColumbiaV. S. Subrahmanian - University of Maryland, College Park
- Resource Type
- Journal article
- Publication Details
- ACM transactions on database systems, Vol.21(2), pp.238-269
- DOI
- 10.1145/232616.232691
- ISSN
- 0362-5915
- eISSN
- 1557-4644
- Publisher
- ACM
- Number of pages
- 32
- Language
- English
- Date published
- 06/01/1996
- Academic Unit
- Business Analytics
- Record Identifier
- 9984962894202771
Metrics
1 Record Views