Model Theoretic Approach to View Updates in Deductive Databases

Jose Alberto Fernandez, John Grant and Jack Minker

• DVI
• PostScript

Abstract

The view update problem for deductive databases has been defined as the problem of accomplishing the update of an intensional predicate by modifying appropriately the extensional database. A previous paper by Grant, Horty, Lobo, and Minker developed algorithms for the insertion and the deletion of an intensional predicate in certain important classes of stratified disjunctive deductive databases. This paper introduces a model theoretic approach which encompasses a wide class of Herbrand semantics, including the perfect model and stable model semantics, for disjunctive databases including negation. This generalizes the earlier results: now the intensional database may contain disjunctive and denial rules, and the database may be required to satisfy integrity constraints. As in the previous paper, the algorithms are proved to be correct and best according to the criterion of causing minimal change to the database, where the first priority is to minimize deletions.

Bibliography

• [1] K.L. Clark. Negation as Failure. In H. Gallaire and J. Minker, editors, Logic and Data Bases, pages 293--322. Plenum Press, New York, 1978.
• [2] J.A. Fernandez. Disjunctive Deductive Databases. PhD thesis, University of Maryland, Department of Computer Science, College Park, 1994.
• [3] J.A. Fernandez, Z.A. Khandakar, and J. Minker. A tractable class of disjunctive deductive databases. In Proc. Workshop on Deductive Databases, Joint International Conference and Symposium on Logic Programming (JICSLP'92), Washington, D.C., Nov. 1992.
• [4] J.A. Fernandez, J. Lobo, J. Minker, and V.S. Subrahmanian. Disjunctive {LP} $+$ integrity constraints = stable model semantics. {\em Annals of Mathematics and Artificial Intelligence}, 8(3--4):449--474, 1993.
• [5] R.Fagin, J.D. Ullman, and M.Y. Vardi. On the semantics of updates in databases. In Proc. 7th ACM SIGACT/SIGMOD Symposium on Principles of Database Systems}, pages 352--365, 1983.
• [6] J. Grant, J. Horty, J. Lobo, and J. Minker. View updates in stratified disjunctive databases. Journal of Automated Reasoning, 11:249--267, 1993.
• [7] M. Gelfond and V. Lifschitz. The Stable Model Semantics for Logic Programming. In R.A. Kowalski and K.A. Bowen, editors, Proc. 5th International Conference and Symposium on Logic Programming}, pages 1070--1080, Seattle, Washington, August 15-19 1988.
• [8] M. Gelfond and V. Lifschitz. Logic programs with classical negation. In D.H.D. Warren and P. Szeredi, editors, Proceedings of the Seventh International Conference on Logic Programming}, pages 579--597, Jerusalem, Israel, June 1990. The MIT Press.
• [9] R.A. Kowalski. Logic for data description. In H. Gallaire and J. Minker, editors, Logic and Data Bases, pages 77--102. Plenum Press, New York, 1978.
• [10] J. Minker. On indefinite databases and the closed world assumption. In {\em Lecture Notes in Computer Science 138}, pages 292--308. Springer-Verlag, 1982.
• [11] J. Minker and C. Ruiz. Semantics for disjunctive logic programs with explicit and default negation. {\em Fundamenta Informaticae}, 20(3/4):145--192, 1994. Anniversary Issue edited by H. Rasiowa.
• [12] T.C. Przymusinski. On the declarative semantics of deductive databases and logic programming. In J. Minker, editor, Foundations of Deductive Databases and Logic Programming, chapter 5, pages 193--216. Morgan Kaufmann Pub., Washington, D.C., 1988.
• [13] P. Pearce and G. Wagner. Logic programming with strong negation. In P. Schroeder-Heister, editor, Proceedings of the International Workshop on Extensions of Logic Programming, pages 311--326, Tubingen, FRG, Dec. 1989. Lecture Notes in Artificial Intelligence, Springer -Verlag.
• [14] R. Reiter. Towards a logical reconstruction of relational database theory. In M.L. Brodie, J.L. Mylopoulos, and J.W. Schmit, editors, On Conceptual Modelling, pages 163--189. Springer-Verlag Pub., New York, 1984.
• [15] R.~Reiter. What should a database know? In Proceedings of the 7th International Conference on Logic Programming}, page 765, Jerusalem, 1990. Abstract of Invited Talk.