Deductive databases: achievements and future directions

ABSTRACT

In the recent years, Deductive Databases have been the focus of intense research, which has brought dramatic advances in theory, systems and applications. A salient feature of deductive databases is their capability of supporting a declarative, rule-based style of expressing queries and applications on databases. As such, they find applications in disparate areas, such as knowledge mining from databases, and computer-aided design and manufacturing systems. In this paper, we briefly review the key concepts behind deductive databases and their newly developed enabling technology. Then, we describe current research on extending the functionality and usability of deductive databases and on providing a synthesis of deductive databases with procedural and object-oriented approaches.

REFERENCES

• 1: K. R. Apt , H. A. Blair , A. Walker, Towards a theory of declarative knowledge, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 2: Francois Bancilhon , David Maier , Yehoshua Sagiv , Jeffrey D Ullman, Magic sets and other strange ways to implement logic programs (extended abstract), Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.1-15, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.15399]
• 3: Jorge Bocca, On the evaluation strategy of EDUCE, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.368-378, May 28-30, 1986, Washington, D.C., United States
• 4: 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]
• 5: D. Chimenti , R. Gamboa , R. Krishnamurthy, Towards an open architecture for LDL, Proceedings of the 15th international conference on Very large data bases, p.195-203, July 1989, Amsterdam, The Netherlands
• 6: Stefano Ceri , Georg Gottlob , Letizia Tanca, Logic programming and databases, Springer-Verlag New York, Inc., New York, NY, 1990
• 7: [GeLi] Gelfond, M., Lifschitz, V., "The Stable Model Semantics for Logic Programming", Proc. 5th Int. Conf. and Symp. on Logic Programming, MIT Press, Cambridge, Ma, pp. 1070-1080, 1988.
• 8: Michael Kifer , Georg Lausen, F-logic: a higher-order language for reasoning about objects, inheritance, and scheme, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.134-146, June 1989, Portland, Oregon, United States
• 9: 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
• 10: M. Kifer , J. Wu, A logic for object-oriented logic programming, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.379-393, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73758]
• 11: [KrN1] Krishnamurthy and S. Naqvi, "Non-Deterministic Choice in Datalog," Proc. 3rd Int. Conf. on Data and Knowledge Bases, June 27-30, Jerusalem, Israel, 1988.
• 12: [LeVi] Lefebvre, A. and Vieille, L. "On Deductive Query Evaluation in the DedGin System," Proc. 1st Int. Conf. on Deductive and O-O Databases, Dec. 4-6, Kyoto, Japan, 1989.
• 13: J. W. Lloyd, Foundations of logic programming; (2nd extended ed.), Springer-Verlag New York, Inc., New York, NY, 1987
• 14: [MaSu] Marek, V. and V. S. Subramanian, "The Relationship between Logic Program Semantics and Non-Monotonic Reasoning," Proc. 6th Int. Conference on Logic Programming, pp. 598-616, MIT Press, 1989.
• 15: [Meta] Morris, K. et al. "YAWN! (Yet Another Window on NAIL!), Data Engineering, Vol. 10, No. 4, pp. 28-44, Dec. 1987.
• 16: [Naq] Naqvi, S. "A Logic for Negation in Database Systems," in Foundations of Deductive Databases and Logic Programming, (Minker, J. ed.), Morgan Kaufman, Los Altos, 1987.
• 17: S. Naqvi , S. Tsur, A logical language for data and knowledge bases, Computer Science Press, Inc., New York, NY, 1989
• 18: T. C. Przymusinski, On the declarative semantics of deductive databases and logic programs, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 19: [Prz2] Przymusinski, T., "Non-Monotonic Formalism and Logic Programming," Proc. 6th Int. Conference on Logic Programming, pp. 656-674, MIT Press, 1989.
• 20: [RaSh] Ramamohanarao, K. and J. Sheperd, "Answering Queries in Deductive Databases", Proc. 4th Int. Conference on Logic Programming, pp. 1014-1033, MIT Press, 1987.
• 21: [SaZ1] Saccá D., Zaniolo, C., "Implementation of Recursive Queries for a Data Language based on Pure Horn Logic," Proc. Fourth Int. Conference on Logic Programming, Melbourne, Australia, 1987.
• 22: D. Sacca , C. Zaniolo, The generalized counting method for recursive logic queries, Theoretical Computer Science, v.62 n.1-2, p.187-220, December 1988 [doi>10.1016/0304-3975(86)90015-0]
• 23: Domenico Sacca , Carlo Zaniolo, Stable models and non-determinism in logic programs with negation, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.205-217, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298572]
• 24: Oded Shmueli , Shalom Tsur, Logical diagnosis of LDL programs, Logic programming, MIT Press, Cambridge, MA, 1990
• 25: [Teta] Tryon, D., et al. "System Analysis for Deductive Database Environments: an Enhanced role for Aggregate Entities," Proc. 9th Int. Conference on Entity-Relationship Approach, Lausanne, CH, Oct. 8-10, 1990.
• 26: [Tsur] Tsur S., "Applications of Deductive Database Systems," Proc. IEEE COMCON Spring '90 Conference, San Francisco, Feb. 26-March 2, 1990.
• 27: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• 28: M. H. Van Emden , R. A. Kowalski, The Semantics of Predicate Logic as a Programming Language, Journal of the ACM (JACM), v.23 n.4, p.733-742, Oct. 1976 [doi>10.1145/321978.321991]
• 29: [VG1] Van Gelder, A., "Negation as failure using tight derivations for general logic programs," Proc. IEEE Symp. on Logic Programming, pp. 127-139, 1986.
• 30: A. Van Gelder, The alternating fixpoint of logic programs with negation, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.1-10, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73722]
• 31: Allen Van Gelder , Kenneth Ross , John S. Schlipf, Unfounded sets and well-founded semantics for general logic programs, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.221-230, March 1988, Austin, Texas, United States [doi>10.1145/308386.308444]
• 32: [Zani] Zaniolo, C. "Object Identity and Inheritance in Deductive Databases: an Evolutionary Approach," Proc. 1st Int. Conf. on Deductive and O-O Databases, Dec. 4-6, 1989, Kyoto, Japan.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Deduction (e.g., natural, rule-based)

General Terms:
Design, Management