Abstract
When updating a knowledge base, several problems may arise. One of the most important problems is that of integrity constraints satisfaction. The classic approach to this problem has been to develop methods forchecking whether a given update violates an integrity constraint. An alternative approach consists of trying to repair integrity constraints violations by performing additional updates thatmaintain knowledge base consistency. Another major problem in knowledge base updating is that ofview updating, which determines how an update request should be translated into an update of the underlying base facts. We propose a new method for updating knowledge bases while maintaining their consistency. Our method can be used for both integrity constraints maintenance and view updating. It can also be combined with any integrity checking method for view updating and integrity checking. The kind of updates handled by our method are: updates of base facts, view updates, updates of deductive rules, and updates of integrity constraints. Our method is based on events and transition rules, which explicity define the insertions and deletions induced by a knowledge base update. Using these rules, an extension of the SLDNF procedure allows us to obtain all possible minimal ways of updating a knowledge base without violating any integrity constraint.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Abiteboul, S. Updates, a new frontier.Proceedings of the International Conference on Database Theory, Bruges, Belgium, 1988.
Atzeni, P. and Torlone, R. Updating intensional predicates in datalog.Data and Knowledge Engineering, 8:1–17, 1992.
Bancilhon, F. and Ramakrishnan, R. An amateur's introduction to recursive query processing.Proceedings of the International ACM SIGMOD Conference on the Management of Data, Washington D.C., 1986.
Bancilhon, F and Spyratos, N. Update semantics of relational views.ACM Transactions on Database Systems, 6(4):557–575, 1981.
Bol, R.N. Loop checking and negation.Journal of Logic Programming, 15:147–175, 1993.
Bol, R.N., Apt, K.R., and Klop, J.W. An analysis of loop checking mechanisms for logic programs.Theoretical Computer Science, 86:35–79, 1991.
Bry, F. Intensional updates: Abduction via deduction.Proceedings of the Seventh ICLP, Jerusalem, 1990.
Bry, F., Manthey, R., and Martens, B. Integrity verification in knowledge bases.ECRC Report D.2.1.a, Munich, 1990.
Cavedon, L. and Lloyd, J. A completeness theorem for SLDNF resolution.Journal of Logic Programming, 7:177–191, 1989.
Ceri, S., Fraternali, P., Paraboschi, S., and Tanca, L. Integrity maintenance systems: An architecture.Third International Workshop on the Deductive Approach to Information Systems and Databases, Roses, Catalonia, 1992.
Ceri, S. and Widom, J. Deriving production rules for constraint maintenance.Proceedings of the Sixteenth VLDB Conference, Brisbane, Australia, 1990.
Clark, K.L. Negation as failure. In: Gallaire, H. and Minker, J., eds.,Logic and Databases. New York: Plenum Press, 1978, pp. 293–322.
Cosmadakis, S. and Papadimitriou, C. Updates of relational views.Journal of the Association for Computing Machinery, 31(4):742–760, 1984.
Date, C.J. Updating views. In:Relational Databases: Selected Writings, Reading, MA: Addison-Wesley, 1986, pp.367–395.
Dayal, U. and Bernstein, P.A. On the correct translation of update operations on relational views.ACM Transactions on Database Systems, 8(3):381–416, 1982.
Decker, H. The range form of databases or: How to avoid floundering.Proceedings of the Fifth ÖGAI, Innsbruck, Austria, 1989.
Decker, H. Drawing updates from derivations.Proceedings of the Third International Conference on Database Theory, Paris, 1990.
Decker, H. and Cavedon, L. Generalizing allowedness while retaining completeness of SLDNF resolution.Proceedings of the Third Workshop on Computer Science Logic, Kaiserslautern, 1990.
Fagin, R., Kuper, G.M., Ullman, J.D., and Vardi, M.Y. Updating logical databases.Advances in Computing Research, 3:1–18, 1986.
Fagin, R., Ullman, J.D., and Vardi, M.Y. On the semantics of updates in databases.Proceedings of the ACM PODS, 1983.
Furtado, A.L. and Casanova, M.A. Updating relational views. In: Kim, W., Reiner, D.S., and Batory, D.S., eds.,Query Processing in Database Systems, Berlin: Springer-Verlag, 1985, pp. 127–142.
Gallaire, H., Minker, J., and Nicolas, J.M. Logic and databases: A deductive approach.ACM Computing Surveys, 16(2):153–185, 1984.
Gärdenfors, P.Knowledge in Flux: Modeling the Dynamics of Epistemic States. Cambridge, MA: MIT Press, 1988.
Guessoum, A. and Lloyd, J.W. Updating knowledge bases.New Generation Computing, 8(1):71–89, 1990.
Guessoum, A. and Lloyd, J.W. Updating knowledge bases II.New Generation Computing, 10:73–100, 1991.
Kakas, A. and Mancarella, P. Database updates through abduction.Proceedings of the Sixteenth VLDB Conference, Brisbane, Australia, 1990.
Keller, A.M. Algorithms for translating view updates to database updates for views involving selection, projections, and joins.Proceedings of the Fourth ACM SIGACTSIGMOD Symposium on the Principles of Database Systems, Portland, OR, 1985.
Keller, A.M. Choosing translator at view definition time.Proceedings of the Twelfth VLDB Conference, Kyoto, Japan, 1986.
Kowalski, R. Database updates in the event calculus.Journal of Logic Programming, 12:121–146, 1992.
Kunen, K. Signed data dependencies in logic programs.Journal of Logic Programming, 7:231–245, 1989.
Langerak, R. View updates in relational databases with an independent schema interface.ACM Transactions on Database Systems, 15(1):40–66, 1990.
Larson, J. and Sheth, A. Updating relational views using knowledge at view definition and view update time.Information Systems, 16(2):145–168, 1991.
Lloyd, J.W.Foundations on Logic Programming, 2nd edition, New York: Springer, 1987.
Lloyd, J.W. and Shepherdson, J.C. Partial evaluation in logic programming.Journal of Logic Programming, 8(11):217–247, 1991.
Lloyd, J.W. and Topor, R.W. Making Prolog more expressive.Journal of Logic Programming, 1(3):225–240, 1984.
Manchanda, S. and Warren, D.S. A logic-based language for database updates. In: Minker, J., ed.,Foundations of Deductive Databases and Logic Programming. Los Altos, CA: Morgan-Kaufmann, 1988, pp. 363–394.
Masunaga, Y. A relational database view update translation mechanism.Proceedings of the Tenth VLDB Conference, Singapore, 1984.
Moerkotte, G. and Lockemann, P.C. Reactive consistency control in deductive databases.ACM Transactions on Database Systems, 16(4):670–702, 1991.
Nicolas, J.M. Logic for improving integrity checking in relational data bases. Technical report, ONERA-CERT, 1979. Also in:Acta Informatica, 18(3):227–253, 1982.
Olivé, A. On the design and implementation of information systems from deductive conceptual models.Proceedings of the Fifteenth VLDB Conference, Amsterdam, 1989.
Olivé, A. Integrity checking in deductive databases.Proceedings of the Seventeenth VLDB Conference, Barcelona, 1991.
Reiter, R. Towards a logical reconstruction of relational database theory. In: Brodie, M.L., Mylopoulos, J., and Schmidt, J.W., eds.,On Conceptual Modelling, New York: Springer-Verlag, 1984, pp. 191–233.
Sadri, F. and Kowalski, R. A theorem-prover approach to database integrity. In: Minker, J., ed.,Foundations of Deductive Databases and Logic Programming, Los Altos, CA: Morgan-Kaufman, 1988, pp. 313–362.
Teniente, E. El Mètode dels Esdeveniments per a l'actualització de vistes en bases de dades deductives. PhD Thesis, Universitat Politècnica de Catalunya, Barcelona, 1992 (in Catalan).
Teniente, E. and Olivé, A. The events method for view updating in deductive databases.International Conference on Extending Database Technology, Vienna, 1992.
Teniente, E. and Olivé, A. Updating knowledge bases while maintaining their consistency. Research Report LSI-94-25-R, UPC, Barcelona, 1994.
Tomasic, A. View update annotation in definite deductive databases.Proceedings of the International Conference on Database Theory, Bruges, Belgium, 1988.
Torlone, R. and Atzeni, P. Updating deductive databases with functional dependencies.Second International Conference on Deductive and Object Oriented Databases, Munich, 1991.
Ullman, J.D.Principles of Database and Knowledge-Base Systems. New York: Computer Science Press, 1988.
Urpí, T. El Mètode dels Esdeveniments per al càlcul de canvis en bases de dades deductives. PhD Thesis, Universitat Politècnica de Catalunya, Barcelona, 1993 (in Catalan).
Urpí, T. and Olivé, A. A. method for change computation in deductive databases.Proceedings of the Eighteenth VLDB Conference, Vancouver, Canada, 1992.
Winslett, M. Updating logical databases.Cambridge Tracts in Theoretical computer Science, 9, 1990.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Teniente, E., Olivé, A. Updating knowledge bases while maintaining their consistency. VLDB Journal 4, 193–241 (1995). https://doi.org/10.1007/BF01237920
Received:
Revised:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF01237920