Abstract
CORAL is a deductive system that supports a rich declarative language, and an interface to C++, which allows for a combination of declarative and imperative programming. A CORAL declarative program can be organized as a collection of interacting modules. CORAL supports a wide range of evaluation strategies, and automatically chooses an efficient strategy for each module in the program. Users can guide query optimization by selecting from a wide range of control choices. The CORAL system provides imperative constructs to update, insert, and delete facts. 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. CORAL provides support for main-memory data and, using the EXODUS storage manager, disk-resident data. We present a comprehensive view of the system from broad design goals, the language, and the architecture, to language interfaces and implementation details.
- Ait-Kaci, H. Warren's Abstract Machine: A Tutorial Reconstruction. Cambridge, MA: MIT Press, 1991. Google Scholar
- Arni, N. and Ong, K. The LDL++ User's Guide, 2.0 edition, January 1993. MCC Technical Report Carnot-012-93(P), Austin, TX.Google Scholar
- Arora, T., Ramakrishnan, R., Roth, W.G., Seshadri, P., and Srivastava, D. Explaining program evaluation in deductive systems. Proceedings of the International Conference on Deductive and Object-Oriented Databases, Phoenix, AZ, 1993.Google Scholar
- Balbin, I. and Ramamohanarao, K. A generalization of the differential approach to recursive query evaluation. Journal of Logic Programming, 4(3):259-262, 1987. Google Scholar
- Bancilhon, F. Naive evaluation of recursively defined relations. In: Brodie, M. and Mylopoulos, J., eds., On Knowledge Base Management Systems: Integrating Database and AI Systems. Heidelberg, Germany: Springer-Verlag, 1985. Google Scholar
- Bayer, R. Query evaluation and recursion in deductive database systems. Unpublished Memorandum, 1985.Google Scholar
- Beeri, C., Naqvi, S., Shmueli, O., and Tsur, S. Set constructors in a logic database language. Journal of Logic Programming, 10(3/4):181-232, 1991. Google Scholar
- Beeri, C. and Ramakrishnan, R. On the power of Magic. Proceedings of the ACM Symposium on Principles of Database Systems, San Diego, CA, 1987. Google Scholar
- Bry, F. Logic programming as constructivism: A formalization and its application to databases. Proceedings of the ACM SIGACT-SIGART-SIGMOD Symposium on the Principles of Database Systems, Philadelphia, PA, 1989. Google Scholar
- Carey, M., DeWitt, D., Richardson, J., and Shekita, E. Object and file management in the EXODUS extensible database system. Proceedings of the International Conference on Very Large Databases, Kyoto, Japan, 1986. Google Scholar
- Chang, J.H. and Despain, A.M. Semi-intelligent backtracking of Prolog based on static data-dependency analysis. Proceedings of the Symposium on Logic Programming, Boston, MA, 1985.Google Scholar
- Chimenti, D., Gamboa, R., and Krishnamurthy, R. Abstract machine for LDL. Technical Report ACT-ST-268-89, MCC, Austin, TX, 1989.Google Scholar
- Chimenti, D., Gamboa, R., Krishnamurthy, R., Naqvi, S., Tsur, S., and Zaniolo, C. The LDL system prototype. IEEE Transactions on Knowledge and Data Engineering, 2(1):76-90, 1990. Google Scholar
- Derr, M.A. Adaptive optimization in a deductive database system. Proceedings of the Second International Conference on Information and Knowledge Management, Arlington, VA, 1993. Google Scholar
- Freitag, B., Schütz, H., and Specht, G. LOLA: A logic language for deductive databases and its implementation. Proceedings of the Second International Symposium on Database Systems for Advanced Applications (DASFAA), Tokyo, Japan, 1991. Google Scholar
- Giannotti, F., Pedreschi, D., Sacca, D., and Zaniolo, C. Non-determinism in deductive databases. Proceedings of the Second International Conference on Deductive and Object-Oriented Databases, Munich, Germany, 1991.Google Scholar
- Goodman, N., Rozen, S., and Stein, L. Requirements for a deductive query language in MapBase genome-mapping database. Proceedings of the Workshop on Programming with Logic Databases, Vancouver, Canada, 1993.Google Scholar
- Goto, E. Monocopy and associative algorithms in an extended lisp. Technical Report 74-03, Information Science Laboratory, University of Tokyo, Japan, May 1974.Google Scholar
- Greco, S., Zaniolo, C., and Ganguly, S. Greedy by choice. Proceedings of the ACM Symposium on the Principles of Database Systems, San Diego, CA, 1992. Google Scholar
- Horowitz, S., Reps, T., Binkley, D. Interprocedural slicing using dependence graphs. ACM Transactions on Programming Languages and Systems, 12(1):26-60, 1990. Google Scholar
- Jeusfeld, M. and Staudt, M. Query optimization in deductive object bases. In: Freytag, J.C., Vossen, G., and Maier, D., eds. Query Processing for Advanced Database Applications. San Mateo, CA: Morgan-Kaufmann, 1993.Google Scholar
- Kiernan, G., deMaindreville, C., and Simon, E. Making deductive database a practical technology: A step forward. Proceedings of the ACM SIGMOD Conference on the Management of Data, Atlantic City, NJ, 1990. Google Scholar
- Kanellakis, P.C., Kuper, G.M., and Revesz, P.Z. Constraint query languages. Proceedings of the Ninth ACM Symposium on the Principles of Database Systems, Nashville, TN, 1990. Google Scholar
- Kemp, D., Ramamohanarao, K., and Somogyi, Z. Right-, left-, and multi-linear rule transformations that maintain context information. Proceedings of the International Conference on Very Large Databases, Brisbane, Australia, 1990. Google Scholar
- Lefebvre, A. Recursive aggregates in the EKS-V1 system. Technical Report TR KB 34, ECRC, February 1991.Google Scholar
- Lefebvre, A. Towards an efficient evaluation of recursive aggregates in deductive databases. Proceedings of the International Conference on Fifth Generation Computer Systems, Tokyo, Japan, 1992.Google Scholar
- Lewis, P.H. A fast way to discover patterns in vast amounts of data. The New York Times, pp. 16-17, August 1992.Google Scholar
- Lloyd, J.W. Foundations of Logic Programming, 2nd ed. Heidelberg, Germany: Springer-Verlag, 1987. Google Scholar
- Logical Information Machines, 8920 Business Park Drive, Suite 372 Austin, TX 78759. The XMIM Reference Guide, 2.1.1 edition, July 1992.Google Scholar
- Maher, M.J. and Ramakrishnan, R. Dèjá vu in fixpoints of logic programs. Proceedings of the Symposium on Logic Programming, Cleveland, OH, 1989.Google Scholar
- Morris, K., Ullman, J.D., and Van Gelder, A. Design overview of the NAIL! system. Proceedings of the Third International Conference on Logic Programming, London, 1986. Google Scholar
- Mumick, I.S., Pirahesh, H., and Ramakrishnan, R. Duplicates and aggregates in deductive databases. Proceedings of the Sixteenth International Conference on Very Large Databases, Brisbane, Australia, 1990. Google Scholar
- Naughton, J.F., Ramakrishnan, R., Sagiv, Y., and Ullman, J.D. Argument reduction through factoring. Proceedings of the Fifteenth International Conference on Very Large Databases, Amsterdam, The Netherlands, 1989. Google Scholar
- Naqvi, S. and Tsur, S. A Logical Language for Data and Knowledge Bases. Principles of Computer Science. New York: Computer Science Press, 1989. Google Scholar
- Phipps, G., Derr, M.A., and Ross, K.A. Glue-NAIL!: A deductive database system. Proceedings of the ACM SIGMOD Conference on Management of Data, Denver, CO, 1991. Google Scholar
- Przymusinski, T.C. On the declarative semantics of stratified deductive databases. In: Minker, J., ed., Foundations of Deductive Databases and Logic Programming, Washington, DC: Morgan Kaufmann, 1988, pp. 193-216. Google Scholar
- Ramakrishnan, R. Magic templates: A spellbinding approach to logic programs. Proceedings of the International Conference on Logic Programming, Seattle, WA, 1988.Google Scholar
- Ramakrishnan, R., editor. Proceedings of the Workshop on Programming with Logic Databases, Vancouver, BC, Canada, October 1993. Available as Technical Report 1183, Computer Sciences Department, University of Wisconsin-Madison.Google Scholar
- Ramakrishnan, R., Beeri, C., and Krishnamurthy, R. Optimizing existential Datalog queries. Proceedings of the ACM Symposium on Principles of Database Systems, Austin, TX, 1988. Google Scholar
- Ramakrishnan, R., Bothner, P., Srivastava, D., and Sudarshan, S. CORAL: A database programming language. Proceedings of the NACLP Workshop on Deductive Databases, Austin, TX, 1990. Available as Report TR-CS-90-14, Department of Computing and Information Sciences, Kansas State University.Google Scholar
- Ramakrishnan, R. and Sudarshan, S. Top-Down vs. Bottom-Up revisited. Proceedings of the International Logic Programming Symposium, San Diego, CA, 1991.Google Scholar
- Ramakrishnan, R., Srivastava, D., and Sudarshan, S. Controlling the search in bottom-up evaluation. Proceedings of the Joint International Conference and Symposium on Logic Programming, Washington, DC, 1992a.Google Scholar
- Ramakrishnan, R., Srivastava, D., and Sudarshan, S. CORAL: Control, Relations and Logic. Proceedings of the International Conference on Very Large Databases, Vancouver, Canada, 1992b. Google Scholar
- Ramakrishnan, R., Seshadri, P., Srivastava, D., and Sudarshan, S. The CORAL user manual: A tutorial introduction to CORAL. unpublished manuscript, 1993a.Google Scholar
- Ramakrishnan, R., Srivastava, D., Sudarshan, S., and Seshadri, P. Implementation of the CORAL deductive database system. Proceedings of the ACM SIGMOD Conference on the Management of Data, Washington, DC, 1993b. Google Scholar
- Ramakrishnan, R., Srivastava, D., and Sudarshan, S. The Save Module facility in CORAL. unpublished manuscript, 1993c.Google Scholar
- Ramakrishnan, R., Srivastava, D., and Sudarshan, S. Rule ordering in bottom-up fixpoint evaluation of logic programs. IEEE Transactions on Knowledge and Data Engineering, in press (A shorter version appeared in VLDB, 1990). Google Scholar
- Reps, T. Solving demand versions of interprocedural analysis problems. Proceedings of the Fifth International Conference on Compiler Construction, Edinburgh, Scotland, 1994. Google Scholar
- Rohmer, J., Lescoeur, R., and Kerisit, J.M. The Alexander method: A technique for the processing of recursive axioms in deductive database queries. New Generation Computing, 4:522-528, 1986. Google Scholar
- Ross, K. Modular Stratification and Magic Sets for DATALOG programs with negation. Proceedings of the ACM Symposium on Principles of Database Systems, Nashville, TN, 1990. Google Scholar
- Ross, K. Modular acyclicity and tail recursion in logic programs. Proceedings of the ACM Symposium on Principles of Database Systems, Denver, CO, 1991. Google Scholar
- Roth, W.G., Ramakrishnan, R., and Seshadri, P. MIMSY: A system for analyzing time series data in the stock market domain. Proceedings of the Workshop on Programming with Logic Databases, Vancouver, Canada, 1993.Google Scholar
- Sagonas, K., Swift, T., and Warren, D.S. XSB as an efficient deductive database engine. Proceedings of the ACM SIGMOD Conference on Management of Data, Minneapolis, MN, 1994. Google Scholar
- Schmidt, H., Kiessling, W., Güntzer, U., and Bayer, R. Compiling exploratory and goal-directed deduction into sloppy delta iteration. IEEE International Symposium on Logic Programming, San Francisco, CA, 1987.Google Scholar
- Seki, H. On the power of Alexander templates. Proceedings of the ACM Symposium on the Principles of Database Systems, Philadelphia, PA, 1989. Google Scholar
- Shmueli, O., Tsur, S., and Zaniolo, C. Compilation of set terms in the logic data language (LDL). Journal of Logic Programming, 12(1/2):89-120, 1992. Google Scholar
- Srivastava, D., Ramakrishnan, R., Seshadri, P., and Sudarshan, S. Coral++: Adding object-orientation to a logic database language. Proceedings of the International Conference on Very Large Databases, Dublin, Ireland, 1993. Google Scholar
- Stroustrup, B. The C++ Programming Language, (2nd Edition). Reading, MA: Addison-Wesley, 1991. Google Scholar
- Sudarshan, S. Optimizing Bottom-Up query evaluation for deductive databases. PhD thesis, University of Wisconsin, Madison, WI 1992. Google Scholar
- Sudarshan, S. and Ramakrishnan, R. Aggregation and relevance in deductive databases. Proceedings of the Seventeenth International Conference on Very Large Databases, Barcelona, Spain, 1991. Google Scholar
- Sudarshan, S. and Ramakrishnan, R. Optimizations of bottom-up evaluation with non-ground terms. Proceedings of the International Logic Programming Symposium, Vancouver, Canada, 1993. Google Scholar
- Vieille, L., Bayer, P., Küchenhoff, V., and Lefebvre, A. EKS-V1, a short overview. AAAI-90 Workshop on Knowledge Base Management Systems, Boston, MA, 1990.Google Scholar
- Vaghani, J., Ramamohanarao, K., Kemp, D.B., Somogyi, Z., and Stuckey, P.J. Design overview of the Aditi deductive database system. Proceedings of the Seventh International Conference on Data Engineering, Kobe, Japan, 1991. Google Scholar
- Vista, D. and Wood, P. Efficient visual queries for deductive databases. Proceedings of the Workshop on Programming with Logic Databases, Vancouver, Canada, 1993.Google Scholar
Index Terms
- The CORAL deductive system
Recommendations
Implementation of the CORAL deductive database system
SIGMOD '93: Proceedings of the 1993 ACM SIGMOD international conference on Management of dataCORAL 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-...
Implementation of the CORAL deductive database system
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-...
Lore: Educational Deductive Database System
Rules and ReasoningAbstractThis paper introduces Lore, a deductive database implemented as a small extension to PostgreSQL, and Triplelore, a triplestore implementation on top of Lore. Lore introduces relations to PostgreSQL that generalizes tables and views (i.e. relations ...
Comments