Implementing Deductive Databases by Mixed Integer Programming.

Colin Bell, Anil Nerode, Raymond T. Ng, V. S. Subrahmanian: Implementing Deductive Databases by Mixed Integer Programming. ACM Trans. Database Syst. 21(2): 238-269(1996)

@article{DBLP:journals/tods/BellNNS96,
  author    = {Colin Bell and
               Anil Nerode and
               Raymond T. Ng and
               V. S. Subrahmanian},
  title     = {Implementing Deductive Databases by Mixed Integer Programming},
  journal   = {ACM Trans. Database Syst.},
  volume    = {21},
  number    = {2},
  year      = {1996},
  pages     = {238-269},
  ee        = {http://doi.acm.org/10.1145/232616.232691, db/journals/tods/BellNNS96.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

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

least models of definite deductive databases, and
minimal models and the Generalized Closed World Assumption of disjunctive databases.

These procedures are sound and 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-based mixed integer programming paradigm is a promising approach to practical implementation of query systems for definition and disjunctive databases.

Copyright © 1996 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 4 Issue 1, Books, VLDB-j, TODS, ..." and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/An4-1 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 2" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD2 or /dvd

BibTeX

Online Edition: ACM Digital Library

[Abstract, Index Terms and Review]
[Full Text in PDF Format, 2042 KB]

References

[Bancilhon et al. 1986]: François Bancilhon, David Maier, Yehoshua Sagiv, Jeffrey D. Ullman: Magic Sets and Other Strange Ways to Implement Logic Programs. PODS 1986: 1-15 BibTeX
[Bancilhon and Ramakrishnan 1986]: François Bancilhon, Raghu Ramakrishnan: An Amateur's Introduction to Recursive Query Processing Strategies. SIGMOD Conference 1986: 16-52 BibTeX
[Beeri and Ramakrishnan 1987]: Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. PODS 1987: 269-284 BibTeX
[Bell et al. 1994]: Colin Bell, Anil Nerode, Raymond T. Ng, V. S. Subrahmanian: Mixed Integer Programming Methods for Computing Nonmonotonic Deductive Databases. J. ACM 41(6): 1178-1215(1994) BibTeX
[Blair et al. 1988]: ...
[Blakeley et al. 1986]: José A. Blakeley, Per-Åke Larson, Frank Wm. Tompa: Efficiently Updating Materialized Views. SIGMOD Conference 1986: 61-71 BibTeX
[Blem et al. 1989]: ...
[Bry 1989]: François Bry: Query Evaluation in Recursive Databases: Bottom-up and Top-down Reconciled. DOOD 1989: 25-44 BibTeX
[Cadoli and Lenzerini 1990]: Marco Cadoli, Maurizio Lenzerini: The Complexity of Closed World Reasoning and Circumscription. AAAI 1990: 550-555 BibTeX
[Chandrasekaran 1984]: ...
[Chandru and Hooker 1991]: V. Chandru, John N. Hooker: Extended Horn Sets In Propositional Logic. J. ACM 38(1): 205-221(1991) BibTeX
[Charniak et al. 1980]: ...
[Dietrich 1987]: Suzanne W. Dietrich: Extension Tables: Memo Relations in Logic Programming. SLP 1987: 264-272 BibTeX
[Dowling and Gallier 1984]: William F. Dowling, Jean H. Gallier: Linear-Time Algorithms for Testing the Satisfiability of Propositional Horn Formulae. J. Log. Program. 1(3): 267-284(1984) BibTeX
[Fernández and Minker 1991]: José Alberto Fernández, Jack Minker: Bottom-Up Evaluation of Hierarchical Disjunctive Deductive Databases. ICLP 1991: 660-675 BibTeX
[Gillett 1976]: ...
[Gomory 1965]: ...
[Gottlob et al. 1993]: Georg Gottlob, Sherry Marcus, Anil Nerode, Gernot Salzer, V. S. Subrahmanian: A Non-Ground Realization of the Stable and Well-Founded Semantics. Theor. Comput. Sci. 166(1&2): 221-262(1996) BibTeX
[Gupta et al. 1993]: Ashish Gupta, Inderpal Singh Mumick, V. S. Subrahmanian: Maintaining Views Incrementally. SIGMOD Conference 1993: 157-166 BibTeX
[Hailerin 1976]: ...
[Hillier and Lieberman 1990]: ...
[Hooker 1988]: ...
[Hooker and Fedjki 1990]: ...
[Jaffar and Lassez 1987]: Joxan Jaffar, Jean-Louis Lassez: Constraint Logic Programming. POPL 1987: 111-119 BibTeX
[Jeroslow 1989]: ...
[Jeroslow 1988]: ...
[Jeroslow and Wang 1990]: ...
[Kagan et al. 1994a]: ...
[Kagan et al. 1994b]: Vadam Kagan, Anil Nerode, V. S. Subrahmanian: Computing Minimal Models by Partial Instantiation. Theor. Comput. Sci. 155(1): 157-177(1996) BibTeX
[Karmarkar 1988]: ...
[Kohn 1991]: Wolf Kohn: Declarative Control Architecture. Commun. ACM 34(8): 64-79(1991) BibTeX
[Kohn and Nerode 1993]: ...
[Li and Yes 1990]: ...
[Liu and Sunderraman 1990]: Ken-Chih Liu, Rajshekhar Sunderraman: Indefinite and Maybe Information in Relational Databases. ACM Trans. Database Syst. 15(1): 1-39(1990) BibTeX
[Lloyd 1987]: John W. Lloyd: Foundations of Logic Programming, 2nd Edition. Springer 1987, ISBN 3-540-18199-7
BibTeX
[Luo and Reijns 1992]: ...
[Maher 1991]: ...
[Minker 1982]: Jack Minker: On Indefinite Databases and the Closed World Assumption. CADE 1982: 292-308 BibTeX
[Morris et al. 1986]: Katherine A. Morris, Jeffrey D. Ullman, Allen Van Gelder: Design Overview of the NAIL! System. ICLP 1986: 554-568 BibTeX
[Naqvi and Tsur 1989]: Shamim A. Naqvi, Shalom Tsur: A Logical Language for Data and Knowledge Bases. Computer Science Press 1989, ISBN 0-7167-8200-6
BibTeX
[Nerode et al. 1995]: Anil Nerode, Raymond T. Ng, V. S. Subrahmanian: Computing Circumscriptive Databases: I. Theory and Algorithms. Inf. Comput. 116(1): 58-80(1995) BibTeX
[Ramakrishnan et al. 1992]: Raghu Ramakrishnan, Divesh Srivastava, S. Sudarshan: CORAL - Control, Relations and Logic. VLDB 1992: 238-250 BibTeX
[Roussopoulos 1991]: Nick Roussopoulos: An Incremental Access Method for ViewCache: Concept, Algorithms, and Cost Analysis. ACM Trans. Database Syst. 16(3): 535-563(1991) BibTeX
[Sellis et al. 1990]: Timos K. Sellis, Nick Roussopoulos, Raymond T. Ng: Efficient compilation of large rule bases using logical access paths. Inf. Syst. 15(1): 73-84(1990) BibTeX
[Shmueli et al. 1988]: Oded Shmueli, Shalom Tsur, Carlo Zaniolo: Rewriting of Rules Containing Set Terms in a Logic Data Model (LDL). PODS 1988: 15-28 BibTeX
[Ullman 1989]: Jeffrey D. Ullman: Bottom-Up Beats Top-Down for Datalog. PODS 1989: 140-149 BibTeX
[Ullman 1988]: Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX
[van Emden and Kowalski 1976]: Maarten H. van Emden, Robert A. Kowalski: The Semantics of Predicate Logic as a Programming Language. J. ACM 23(4): 733-742(1976) BibTeX
[van Gelder 1989]: Allen Van Gelder: The Alternating Fixpoint of Logic Programs with Negation. PODS 1989: 1-10 BibTeX
[Warren 1992]: David Scott Warren: Memoing for Logic Programs. Commun. ACM 35(3): 93-111(1992) BibTeX
[Yahya and Henschen 1985]: Adnan H. Yahya, Lawrence J. Henschen: Deduction in Non-Horn Databases. J. Autom. Reasoning 1(2): 141-160(1985) BibTeX
[Zaniolo 1988]: Carlo Zaniolo: Design and Implementation of a Logic Based Language for Data Intensive Applications. ICLP/SLP 1988: 1666-1687 BibTeX

Referenced by

Thomas Eiter, Georg Gottlob, Heikki Mannila: Disjunctive Datalog. ACM Trans. Database Syst. 22(3): 364-418(1997)
Jian Yang, Kamalakar Karlapalem, Qing Li: Algorithms for Materialized View Design in Data Warehousing Environment. VLDB 1997: 136-145
V. S. Subrahmanian, Dana S. Nau, Carlo Vago: WFS + Branch and Bound = Stable Models. IEEE Trans. Knowl. Data Eng. 7(3): 362-377(1995)

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]