Implementing deductive databases by mixed integer programming

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.

References

1. BANCILHON, F., MAIER, D., SAtHV, Y., AND ULLMAN, J. 1986. Magic sets and other strange ways to implement logic programs. In ProceedinGs ofACM-PODS, 1 15.
2. BAN('II,HON, F. AND RAMAKRISIINAN, R. 1986. An amateur's introduction to recursive query processing strategies. In ProceedinGs of ACM-SIGMOD, 16-52.
3. BEERI, C. ^NI) RAMAKRISHNAN, R. 1987. On the Power of Magic. In ProceedinGs of the Sixth Symposium on Principles of Database Systems, 269-283.
4. B~:LI,, C., NEROt)E, A., Nt;, R., AND SUBRAHMANIAN, V. S. 1994. Mixed integer programming methods for computing nonmouotonic deductive databases. J. ACM 41, 6 (Nov.) 1178-1215.
5. BLAIR, C., JEROSLOW, R. G., AND LOWE, J.K. 1988. Some results and experiments in programming techniques for propositional logic. Comput. Oper. Res. 13, 633 645.
6. BLAKELEY, J., LARSON, P., AND TOWPA, F. 1986. Efficiently updating materialized views. In Proceedings of ACM-SIGMOD, 61 71.
7. BLt;M, I,., SHUB, M., ANI) SMALE, S. 1989. On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bull. Am. Math. Soc. 21, 1 -46.
8. BRY, R. 1989. Query evaluation in deductive databases: Bottom-up and top-down reconciled. In Proceedings of the First International Conference on Deductive and Object-Oriented Databases, 25-44.
9. CAI)OLI, M. AND LENZER{NI, M, 1990. The complexity of closed world reasoning and circumscription. In Proceedings of AAAI-90, 550-555.
10. (?~t^N~mAS~:KAP~t~, R. 1984. Integer programming problems for which a simple rounding type of algorithm works. In Progress in Combinatorial Optimization, W. Pulleyblank, Ed, Academic Press, San Diego, CA, 101 106.
11. CHANDRU, V. AND HOOKFR, ,J. 1991. Extended Horn sets in propositional logic. J. ACM 38, 1, 205 221.
12. CHARNIAK, E., RIESBECK, C., ANI) McDERMOTT, D. 1980. Artificial Intelltgence Programming, L. Erlbaum Associates, New York.
13. DIETRICH, S.W. 1987. Extension tables: Memo relations in logic programming. In ProceedinGs of the Fourth IEEE Symposium on Logic Programming, 264-272.
14. D()WLIN(}, W. AND GALLIER, J. 1984. Linear-time algorithms for testing the satisfiability of propositional Horn theories, d. Logic Program. 3, 267 284.
15. F~;RN~'~I~V:Z, J. A. AND MINKER, J. 1991. Bottom-up evaluation of hierarchical disjunctive deductive databases. In Proceedings of the International Conference on Logic Programming, (Paris, France, June) 661 675.
16. GII,I,E'PT, B.E. 1976. Introduction to Operations Research: A Computer-Oriented Algorithmic Approach. McGraw Hill, New York.
17. GOMORV, R E. 1965. On the relation between integer and non-integer solutions to linear programs. Proc. Nat. Acad. Sci. 53, 260 265.
18. (_~)TTI,OB, G., MARCUS, S., NEROI)E, A., SALZER, O., AND SUBRAHMANIAN, V.S. 1993. A non-ground realization of stable and well-founded semantics. Accepted for publication: Theoretical Computer Science.
19. Guv'r^, A., MUMI(:K, I., ANt) SUBm~HMANrAN, V. S. 1993. Maintaining views incrementally. In Prt~ceedings of the 1993 ACM SIGMOD Conference on Management of Data (Washington, D.C., MayL 157 166.
20. HAILPERIN, T. 1976. Boole's Logic and Probability: A Critical Exposition from the Standpoint of Contemporary Algebra, Logic and Probability Theory. North Holland, Amsterdam.
21. HILLIER, F. AND LIEBERMAN, G. 1990. Operations Research. McGraw-Hill, New York.
22. HOOKER, J. 1988. A quantitative approach to logical inferences. Decis. Support Syst. 4, 45-69.
23. HOOKER, J. AND FEDJKI, C. 1990. Branch-and-cut solution of inference problems in propositional logic. Ann. Math. Artif. Intell. 123-139.
24. JAFFAR, J. AND LASSEZ, J. L. 1987. Constraint logic programming. In Proceedings of ACM Principles of Programming Languages, 111 119.
25. JEROSLOW, R. E. 1989. Logic-Based Decision Support: Mixed Integer Model Formulation. North Holland, Amsterdam.
26. JEROSLOW, R. E. 1988. Computation-oriented reductions of predicate to propositional logic. Decis. Support Syst. 4, 183-187.
27. JEROSLOW, R. AND WANG, J. 1990. Solving propositional satisfiability problems. Ann. Math. Artif. Intell. 167-187.
28. KAGAN, V., NERODE, A., AND SUBRAHMAN~tN, V.S. 1994a. Computing definite logic programs by partial instantiation. Ann. Pure Appl. Logic, 67, 161-182.
29. KA6AN, V., NERODE, A., AND SUBRAHMAN1AN, V. S. 1994b. Computing minimal models by partial instantiation. Accepted for publication: Theoretical Computer Science.
30. KARMARKAR, N. 1988. Methods and apparatus for efficient resource allocation. Patent Number 4744028, US Patent Office.
31. KOHN, W. 1991. Declarative control architecture. CACM 34, 8, 64-79.
32. KOHN, W. AND NERODE, A. 1993. Autonomous control theory of hybrid systems: The implementation. IEEE-CDC 93 (to appear).
33. LI, Z. AND YES, P. 1990. Some results on exact data dependence analysis. In Languages and Compilers for Parallel Computing, D. Gelernter, A. Nicolau, and D. Padua, Eds. MIT Press, Cambridge, MA.
34. LIU, K. AND SUNDERRAMAN, a. 1990. Indefinite and maybe information in relational databases. ACM Trans. Database Syst. 15, 1, 1-39.
35. LLOYD, J. W. 1987. Foundations of Logic Programming. Springer-Verlag, Heidelberg, C-ermany.
36. Leo, J. AND REIJNS, G. 1992. Parallel implementation of two algorithms to solve linear programming problems. In Transputing in Numerical and Neural Network Applications, IOS Press, Amsterdam, 48-65.
37. MAHER, M. 1991. Personal electronic mail message, July 29, 1991.
38. MINKER, J. 1982. On indefinite databases and the closed world assumption. In Proceedings of the Sixth Conference on Automated Deduction (New York), D. Loveland, Ed., Lecture Notes in Computer Science, Vol. 138, Springer-Verlag, 292-308.
39. MORRIS, K., ULLMAN, J., AND VAN GELDER, A. 1986. Design overview of the NAIL system. In Proceedings of the Third International Conference on Logic Programming (London, UK), E. Shapiro, Ed., Springer LNCS 225, Springer-Verlag, 554-568.
40. NAQVl, S. AND TSUR, S. 1989. A Logical Language for Data and Knowledge Bases. Computer Science Press, New York.
41. NERODE, A., NO, R., AND SUS~MA~, V. S. 1995. Computing circumscription by linear programming. Inf. Comput., 116, 58-80.
42. RAMAKmSHNAN, R., SRIVASTAVA, D., AND SUD~d~SHAN, S. 1992. CORAL--control, relations and logic. In Proceedings of the Eighteenth VLDB, 238-250.
43. RoussoPOULOS, N. 1991. The incremental access method of view cache: Concept and cost analysis. ACM Trans. Database Syst. 16, 3, 535-563.
44. SELLIS, T., ROUSSOPOULOS, N., AND NG, R. 1990. Efficient compilation of large rule bases using logical access paths. Inf. Syst. 15, 1, 73-84.
45. SHMUELI, O., TSUR, S., AND Za~IOLO, C. 1988. Rewriting of rules containing set terms in a logic data language. In Proceedings of the Seventh Symposium on Principles of Database Systems, 15-28.
46. ULLMAN, J. D. 1989. Bottom-up beats top-down for Datalog. In Proceedings of the 1989 Symposium on Principles of Database Systems (Philadelphia, PA, May), 140-149.
47. ULLMAN, J. D. 1988. Principles of Database and Knowledge-Base System, Vol. 1. Computer Science Press, New York.
48. vAN EMDE~, M. H. AND KOWALSrd, R.A. 1976. The semantics of predicate logic as a programming language. J. ACM 23, 4, 733-742.
49. VAN GELDER, A. 1989. The alternating fixpoint of logic programs with negation. In Proceedings of the Eighth ACM Symposium on Principles of Database Systems, 1-10.
50. WARR~:N, D.S. 1992. Memoing for logic programs. Commun. ACM 35. 3, 94 111.
51. YAHYA, A. AND HENSCHEN, L.J. 1985. Deduction in non-Horn databases. J. Autom. Reasoning 1, 2. 141 160.
52. ZANIOI,O, C. 1988. Design and implementation of a logic-based language for data-intensive applications. In Proceedings of the International Conference on Logic Programming, K. Bowen and R. Kowalski, Eds. MIT Press, Cambridge, MA, 1666- 1687.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Knowledge representation and reasoning

• Information systems

  • Data management systems

    • Query languages

• Theory of computation

  • Logic

  • Models of computation

    • Computability

  • Theory and algorithms for application domains

    • Database theory

      • Database query languages (principles)