A Logic Approach to Database Dynamic Updating

Authors: Daniel Stamate

Abstract:

We introduce a logic-based framework for database updating under constraints. In our framework, the constraints are represented as an instantiated extended logic program. When performing an update, database consistency may be violated. We provide an approach of maintaining database consistency, and study the conditions under which the maintenance process is deterministic. We show that the complexity of the computations and decision problems presented in our framework is in each case polynomial time.

Keywords: Databases, knowledge bases, constraints, updates, minimal change, consistency.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1071528

References:

[1] J. J. Alferes, P. Dell-Acqua, L. M. Pereira., A compilation of updates plus preferences, Technical report, LiTH-ITN-R-2002-7, Dept. of Science and Technology, Linkoping University, Sweden, 2002
[2] J. J. Alferes, J. A. Leite, L. M. Pereira, H. Przymusinska, T. C. Przymusinski, Dynamic updates of non-monotonic knowledge base, J. of Logic Programming, 45:1-3, 2000
[3] J. J. Alferes, L. M. Pereira, Updates plus Preferences, Procs. of JELIA-00, 2000.
[4] A. Borgida, Language features for flexible handling of exceptions in information systems., J. ACM Trans. Database Syst. 10, 1985
[5] G. Brewka, T. Eiter, Preferred Answer Sets for Extended Logic Programs, Proc. of KR-98: Principles of Knowledge Representation and Reasoning, 1998
[6] M. Dalal, Updates in propositional databases. Tech. Report DCS-TR- 222, Dept. of Comp. Science, Rutgers University, New Brunswick, 1988
[7] M. Dekhtyar, A. Dikovsky, N. Spyratos, On Conservative Enforced Updates. Proc. of 4th Int. Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR-97, 1997
[8] J. Delgrande, T. Schaub, H. Tompits, A Framework for Compiling Preferences in Logic Programs J. Theory and Practice of Logic Programming, 2002
[9] M. Halfeld Ferrari Alves, D. Laurent, N. Spyratos, Update Rules in Datalog programs. Proc. of 2nd Int. Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR-95, 1995
[10] H. Katsuno, A. Mendelzon Propositional Knowledge Base Revision and Minimal Change. J. Artifi cial Intelligence, 1991:52
[11] V.W. Marek, M. Truszcy'nski, Revision Programming, Database Updates and Integrity Constraints. Proc. of International Conference on Database Theory, ICDT, 1995
[12] E. Mayol, E. Teniente, Structuring the Process of Integrity Maintenance, Proc. of 8th Database and Expert Systems Applications - DEXA-97, 1997