Declarative expression of deductive database updates

ABSTRACT

An update can be specified as a single database state transition, or as a sequence of queries and database state transitions. We give an extension of Datalog for expressing both types of update specifications on a logic database. The extension supports the simple and intuitive expression of basic update operations, hypothetical reasoning and update procedures. The extension possesses a possible-world semantics, and a sound and complete proof theory. Soundness and completeness is proved by showing that an update procedure can be mapped into a semantically equivalent Pure Prolog program. This means that the semantic and proof-theoretic results of Pure Prolog can be mapped into similar results for the Datalog extension.

REFERENCES

• Abi88: S. Abiteboul, Updates, a new frontier, Lecture notes in computer science on ICDT '88, p.1-18, October 1988, Bruges, Belgium
• ABW87: 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
• AV87: S. Abiteboul , V. Vianu, A translation language complete for database update and specification, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.260-268, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28688]
• AV88: Serge Abiteboul , Victor Vianu, Procedural and declarative database update languages, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.240-250, March 1988, Austin, Texas, United States [doi>10.1145/308386.308448]
• Bac88: Hamid Bacha. Meta-Prolog Design and Implementation. In Proceedings of the Fifth International Conference and Symposium of Logic Programming, pages 1371--1402, M1T Press, 1988.
• BK82: K.A. Bowen and R. A. Kowalski. Amalgamating Language and Metalanguage in Logic Programming. In K. L. Clark and S. A. Taemlund, editors, Logic Programming, Academic Press, 1982.
• Bon88: A. J. Bonner, Hypothetical datalog: complexity and expressibility, Lecture notes in computer science on ICDT '88, p.144-160, October 1988, Bruges, Belgium
• CH85: A. Chandra and D. Harel. Horn Clause Queries and Generalizations. Journal of Logic Programming, 1:1- -15, 1985.
• dS88: 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
• GR84: D.M. Gabbay and U. Reyle. N-Prolog: An Extension of Prolog with Hypothetical Implications. Journal of Logic Programming, 1(4), December 1984.
• Har79: David Harel, First-Order Dynamic Logic, Springer-Verlag New York, Inc., Secaucus, NJ, 1979
• JW84: J. W. Lloyd, Foundations of logic programming, Springer-Verlag New York, Inc., New York, NY, 1984
• Kri63: S. Kripke. Semantical Considerations on Modal Logic. Acta Philosophica Fennica, 16:83--94, 1963.
• Mil86: Dale Miller. A Theory of Modules for Logic Programming. In Proceedings of the 1986 Symposium on Logic Programming, Salt Lake City, Utah, September 1986.
• MSW86: Sanjay Manchanda, Soumtira Sengupta, and David S. Warren. Concurrent Updates in a Prolog Database System. Technical Report 86/28, SUNY at Stony Brook, StonyBrook, NY 11794, December 1986.
• MW87: S. Manchanda , D. S. Warren, A logic-based language for database updates, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• NK88: Shamim Naqvi , Ravi Krishnamurthy, Database updates in logic programming, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.251-262, March 1988, Austin, Texas, United States [doi>10.1145/308386.308451]
• NTR87: Lee Naish, James A. Thorn, and Kotagiri Ramamohanarao. Concurrent Database Updates in Prolog. In International Conference on Logic Programming, pages 178--195, Melbourne, 1987.
• Rei84: R. Reiter. Towards a Logical Reconstruction of Relational Database Theory. In M.Brodie, J. Myopoulos, and J. Schmidt, editors, On Conceptual Modelling, Springer-Verlag, 1984.
• Tho88: James A. Thorn. A Declarative Approach to Database Updates. Technical Report 1/88, Department of Comuter Science, Royal Melbourne Institute of Technology, Melbourne 3001, 1988.
• Ull88: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• War84: David Scott Warren. Database Updates in Pure Prolog. In Proceedings of the International Conference on Fifth Generation Computer Systems, pages 244--253, ICOT, 1984.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS

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

          Nouns: Prolog

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

  H. Information Systems
  H.2 DATABASE MANAGEMENT

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Design