Implementation of the CORAL deductive database system

ABSTRACT

CORAL is a deductive database system that supports a rich declarative language, provides a wide range of evaluation methods, and allows a combination of declarative and imperative programming. The data can be persistent on disk or can reside in main-memory. We describe the architecture and implementation of CORAL. There were two important goals in the design of the CORAL architecture: (1) to integrate the different evaluation strategies in a reasonable fashion, and (2) to allow users to influence the optimization techniques used so as to exploit the full power of the CORAL implementation. A CORAL declarative program can be organized as a collection of interacting modules and this modular structure is the key to satisfying both these goals. The high level module interface allows modules with different evaluation techniques to interact in a transparent fashion. Further, users can optionally tailor the execution of a program by selecting from among a wide range of control choices at the level of each module. CORAL also has an interface with C++, and users can program in a combination of declarative CORAL, and C++ extended with CORAL primitives. A high degree of extensibility is provided by allowing C++ programmers to use the class structure of C++ to enhance the CORAL implementation.

REFERENCES

• 1: I. Balbin , K. Ramamohanarao, A generalization of the differential approach to recursive query evaluation, Journal of Logic Programming, v.4 n.3, p.259-262, Sept. 1987 [doi>10.1016/0743-1066(87)90004-5]
• 2: M. J. Carey , David J. DeWitt , G. Graefe , D. M. Haight , J. E. Richardson , D. T. Schuh , E. J. Shekita , S. L. Vandenberg, The EXODUS extensible DBMS project: an overview, Readings in object-oriented database systems, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1989
• 3: D. Chimenti , R. Gamboa , R. Krishnamurthy , S. Naqvi , S. Tsur , C. Zaniolo, The LDL System Prototype, IEEE Transactions on Knowledge and Data Engineering, v.2 n.1, p.76-90, March 1990 [doi>10.1109/69.50907]
• 4: Burkhard Freitag , Heribert Schütz , Günther Specht, LOLA - A Logic Language for Deductive Databases and its Implementation, Proceedings of the Second International Symposium on Database Systems for Advanced Applications, p.216-225, April 02-04, 1991
• 5: E. Goto. Monocopy and associative algorithms in an extended lisp. Technical Report 74-03, information Science Laboratory, Univ. of Tokyo, Tokyo, Japan, May 1974.
• 6: M. Jeusfeld and M. Staudt. Query optimization in deductive object bases. In G. J.C. Freytag, G. Vossen and D. Mater, editors, Query Processing }or Advanced Database Applications. Morgan-Kaufmann, 1993.
• 7: David B. Kemp , Kotagiri Ramamohanarao , Zoltan Somogyi, Right-, left-, and multi-linear rule transformations that maintain context information, Proceedings of the sixteenth international conference on Very large databases, p.380-391, September 1990, Brisbane, Australia
• 8: G. Kiernan , C. de Maindreville , E. Simon, Making deductive databases a practical technology: a step forward, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.237-246, May 23-26, 1990, Atlantic City, New Jersey, United States
• 9: Werner Kießling , Helmut Schmidt , Werner Strauß , Gerhard Dünzinger, DECLARE and SDS: early efforts to commercialize deductive database technology, The VLDB Journal — The International Journal on Very Large Data Bases, v.3 n.2, April 1994
• 10: A. Lefebvre. Towards an efficient evaluation of recursive aggregates in deductive d#tabases. In Proceedings of the International Conference on Fifth Generation Computer Systents, June 1992.
• 11: Katherine Morris , Jeffrey D Ullman , Allen Van Gelder, Design overview of the NAIL] system, Proceedings on Third international conference on logic programming, p.554-568, September 1986, London, United Kingdom
• 12: Inderpal Singh Mumick , Hamid Pirahesh , Raghu Ramakrishnan, The magic of duplicates and aggregates, Proceedings of the sixteenth international conference on Very large databases, p.264-277, September 1990, Brisbane, Australia
• 13: S. Naqvi , S. Tsur, A logical language for data and knowledge bases, Computer Science Press, Inc., New York, NY, 1989
• 14: J. F. Naughton , R. Ramakrishnan , J. D. Ullman, Argument reduction by factoring, Proceedings of the 15th international conference on Very large data bases, p.173-182, July 1989, Amsterdam, The Netherlands
• 15: Geoffrey Phipps , Marcia A. Derr , Kenneth A. Ross, Glue-Nail: a deductive database system, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.308-317, May 29-31, 1991, Denver, Colorado, United States
• 16: R. Ramakrishnan. Magic Templates: A spellbinding approach to logic programs. In Proceedings of the International Conference on Logic Programming, pages 140-159, Seattle, Washington, August 1988.
• 17: Raghu Ramakrishnan , Catriel Beeri , Ravi Krishnamurthy, Optimizing existential datalog queries, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.89-102, March 1988, Austin, Texas, United States [doi>10.1145/308386.308420]
• 18: R. Ramakrishnan, P. Bothner, D. Srivastava, and S. Sudarshan. CORAL: A database programming language. In J. ChoraleS, editor, Proceedings of the NA CLP '90 Workshop on Deductive Databases, October 1990. Available as Report TR-CS-90-14, Department of Computing and Information Sciences, Kansas State University.
• 19: R. Ramakrishnan, P. Seshadri, D. Srivastava, and S. Sudarshun. The CORAL user manual: A tutorial introduction to CORAL. Manuscript, 1993.
• 20: Raghu Ramakrishnan , Divesh Srivastava, Rule ordering bottom-up fixpoint evaluation of logic programs, Proceedings of the sixteenth international conference on Very large databases, p.359-371, September 1990, Brisbane, Australia
• 21: R. Ramakrislman, D. Srivastava, and S. Sudarshan. Controlling the search in bottom-up evaluation. In Proceedings of the Joint International Conference and S#/mposium on Logic Programming, 1992.
• 22: Raghu Ramakrishnan , Divesh Srivastava , S. Sudarshan, CORAL - Control, Relations and Logic, Proceedings of the 18th International Conference on Very Large Data Bases, p.238-250, August 23-27, 1992
• 23: R. Ramakrishnan, D. Srivastava, and S. Sudarshan. Efficient bottom-up evaluation of logic programs. In J. Vandewane, editor, The State of the Art in Computer Systems and Software Engineering. Kluwer Academic Pubfishers, 1992.
• 24: R. Ramakrishnan and S. Sudarshan. Top-Down vs. Bottom- Up Revisited. In Proceedings of the International Logic Programming Symposium, 1991.
• 25: D. Srlvastava, R. Ramakrishnan, P. Seshadri, and S. Sudarshan. CORAL++: Adding object-orientation to a logic database language. Submitted.
• 26: S. Sudarshan and #ghu Ramakrlshnan. Optimizations of bottom-up evaluation with non-ground ter#s. In JICSLP'9# Post-Conference Workshop on Deductive Databases, 1992.
• 27: Shalom Tsur , Carlo Zaniolo, LDL: A Logic-Based Data Language, Proceedings of the 12th International Conference on Very Large Data Bases, p.33-41, August 25-28, 1986
• 28: J. Vaghani, K. Ramamohanarao, D. Kemp, Z. Somogyi, and P. Stuckey. The Aditi deductive database system. In Proceedings of the NA CLP'90 Workshop on Deductive Database Systems, 1990.
• 29: L. Vieille, P. Bayer, V. Kfichenhoff, and A. Lefebvre. EKS- V1, a short overview. In AAAI-90 Workshop on Knowledge Base Management Systems, 1990.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: CORAL; C++

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models

General Terms:
Design, Languages