Making deductive databases a practical technology: a step forward

ABSTRACT

Deductive databases provide a formal framework to study rule-based query languages that are extensions of first-order logic. However, deductive database languages and their current implementations do not seem appropriate for improving the development of real applications or even sample of them. Our goal is to make deductive database technology practical. The design and implementation of the RDL1 system, presented in this paper, constitute a step toward this goal. Our approach is based on the integration of a production rule language within a relational database system, the development of a rule-based programming environment and the support of system extensibility using Abstract Data Types. We discuss important practical experience gained during the implementation of the system. Also, comparisons with related work such as LDL, STARBURST and POSTGRES are given.

REFERENCES

• Abiteboul89: Serge Abiteboul , Eric Simon, Fundamental properties of deterministic and nondeterministic extensions of Datalog, Theoretical Computer Science, v.78 n.1, p.137-158, Jan. 21, 1991
• Brownston85: Lee Brownston , Robert Farrell , Elaine Kant , Nancy Martin, Programming expert systems in OPS5: an introduction to rule-based programming, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1985
• Cheiney89: Jean-Pierre Cheiney , Christophe de Maindreville, Relational Storage and Efficient Retrieval of Rules in a Deductive DBMS, Proceedings of the Fifth International Conference on Data Engineering, p.644-651, February 06-10, 1989
• Chimenti89: 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
• Dayal88: U. Dayal , B. Blaustein , A. Buchmann , U. Chakravarthy , M. Hsu , R. Ledin , D. McCarthy , A. Rosenthal , S. Sarin , M. J. Carey , M. Livny , R. Jauhari, The HiPAC project: combining active databases and timing constraints, ACM SIGMOD Record, v.17 n.1, p.51-70, March, 1988 [doi>10.1145/44203.44208]
• Delcambre88: L M Delcambre, J N Etheredge "The Relational Production Language a Productlon Language for Relational Database" Proc of Int Conf on Expert Database System, April 1988
• Guttag77: Guttag J V et al, 'The Design of Data Type Specifications", Current Trends zn Programmzng Methodology, Vol IV Data Structuring, Raymond T Yeh, ed, 1977
• Haas89: L. M. Haas , J. C. Freytag , G. M. Lohman , H. Pirahesh, Extensible query processing in starburst, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.377-388, June 1989, Portland, Oregon, United States
• Kee85: Intelhcorp "KEE Software Development System User's Manual", lntelhcorp Mountain Vzew, 1985
• Kiernan89: G. Gardarin , J.-P. Cheiney , G. Kiernan , D. Pastre , H. Stora, Managing complex objects in an extensible relational DBMS, Proceedings of the 15th international conference on Very large data bases, p.55-65, July 1989, Amsterdam, The Netherlands
• Kiernan90: G Klernan, C de Mamdrewlle, E Simon "Making Deductive Database a Practical Technology a Step Forward", INRIA Research Report N~ 1153, Jan 1990
• Maindreville88: Christophe de Maindreville , Eric Simon, A Production Rule-Based Approach to Deductive Databases, Proceedings of the Fourth International Conference on Data Engineering, p.234-241, February 01-05, 1988
• Maindreville88b: Christophe de Maindreville , Eric Simon, Modelling Non Deterministic Queries and Updates in Deductive Databases, Proceedings of the 14th International Conference on Very Large Data Bases, p.395-406, August 29-September 01, 1988
• McCarthy89: Dennis McCarthy , Umeshwar Dayal, The architecture of an active database management system, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.215-224, June 1989, Portland, Oregon, United States
• Naqvi89: S. Naqvi , S. Tsur, A logical language for data and knowledge bases, Computer Science Press, Inc., New York, NY, 1989
• Osborn86: Sylvia L. Osborn , T. E. Heaven, The design of a relational database system with abstract data types for domains, ACM Transactions on Database Systems (TODS), v.11 n.3, p.357-373, Sept. 1986 [doi>10.1145/6314.6461]
• Regnier89: M Rdgmer, E Simon "Efficient Evaluation of Production Rules m a DBMS", Proc of Advances zn Databases, edited by INRIA, Geneva, Sept 1989
• Stonebraker88: Michael Stonebraker, Inclusion of New Types in Relational Data Base Systems, Proceedings of the Second International Conference on Data Engineering, p.262-269, February 05-07, 1986
• Stonebraker88b: Michael Stonebraker , Eric N. Hanson , Spyros Potamianos, The POSTGRES Rule Manager, IEEE Transactions on Software Engineering, v.14 n.7, p.897-907, July 1988 [doi>10.1109/32.42733]
• Stonebraker89: M. Stonebraker , M. Hearst , S. Potamianos, A commentary on the POSTGRES rules system, ACM SIGMOD Record, v.18 n.3, p.5-11, Sep. 1989 [doi>10.1145/71031.71032]
• Tsur86: 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
• Ullman88: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• Valduriez89: Patrick Valduriez , Georges Gardarin, Analysis and Comparison of Relational Database Systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• Widom89: J Wldom, S Fmkelstem "A Syntax and Semantics for Set Omented Production Rules ~n Relational Databases, " IBM Research Report, RJ 6880, Almaden Research Center, June 1989
• Wilms88: P F Wflms et al "Incorporating data types m an extendible database architecture", IBM Research Report, RJ 6405, Almaden Res Center, Aug 1988 Also in Proc of Int Conf on Improwng Data Responswness and Usabzhty, June 1988

INDEX TERMS

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

          Nouns: Datalog

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

          Nouns: LISP
      D.3.3 Language Constructs and Features
          Subjects: Abstract data types

  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

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

General Terms:
Design, Languages, Performance, Theory