Abstract
A new concept is introduced of globally stable behavior of a deductive data base reacting to stimuli of its active medium. Various problems of integrity constraints restoration after updates fit this general frame. We explore the computational complexity of the problem of stability of a deductive data base in a given DB state with respect to its medium.
This work was sponsored by INTAS (Grant 94-2412) and the Russian Fundamental Studies Foundation (Grants 96-01-00086 and 96-01-00395).
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Apt, K.R., Blair, H. and Walker A., Towards a theory of declarative knowledge. in: J. Minker (ed.) Foundations of deductive databases and logic programming. Morgan Kaufman Pub., Los Altos, 89–148, 1988.
Chandra, A.K., Kozen, D.C., Stockmeyer, L.J., Alternation. J. Ass. Comput. Mach., v.28, n.1, 114–133, 1981.
Dayal, U., Hanson,E., and Widom, J., Active database systems. In W. Kim (ed.) Modern Database Systems. 436–456, Addison Wesley, 1995.
Dekhtyar, M.I., Dikovsky, A.Ja., Dynamic Deductive Data Bases with Steady Behavior. In L. Sterling (ed.) Proc. of the 12th International Conf. on Logic Programming, The MIT Press, 183–197, 1995.
Dekhtyar, M.I., Dikovsky, A.Ja., On Homeostatic Behavior of Dynamic Deductive Data Bases. In: D. Bjorner, M.Broy, I.Pottosin (eds.) Proc. 2nd Int. A.P.Ershov Memorial Conference “Perspectives of System Informatics”. Lecture Notes in Computer Science. 1996, Vol. 1181, 420–432.
Eiter, T., Gottlob, G., On the complexity of propositional knowledge base revision, updates, and counterfactuals. Artificial Intelligence, vol. 57, 227–270, 1992.
Gelfond, M., Lifschitz, V., The stable semantics for logic programs. In: R.Kovalsky and K.Bowen (eds.) Proc. of the 5th Intern. Symp. on Logic Programming. 1070–1080, Cambridge, MA, 1988, MIT Press.
Gottlob, G., Moercotte, G., Subrahmanian, V.S., The PARK semantics for Active Databases. In Proc. of EDBT'96. Avignon, France, 1996.
Halfeld Ferrari Alves, M., Laurent, D., Spyratos, N. Update rules in Datalog programs. Rapport de Recherche n. 1024, 01 / 1996, Université de Paris-Sud, Centre d'Orsay, LRI.
Katsuno, H., Mendelzon, A. O., Propositional knowledge base revision and minimal change. Artificial Intelligence, vol. 52, 253–294, 1991.
Marek, V.W., Truszcińsky, M. Revision programming, database updates and integrity constraints. In: International Conference on Data Base theory, ICDT, LNCS n. 893, 368–382, 1995.
Przymusinski, T.C., Turner, H., Update by Means of Inference Rules. In: V.W.Marek, A.Nerode, M.Truszczyński (eds.) Logic Programming and Nonmonotonic Reasoning, Proc. of the Third Int. Conf. LPNMR'95, Lexington, KY, USA, 166–174, 1995.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dekhtyar, M.I., Ja. Dikovsky, A. (1997). Recognition of deductive data base stability. In: Adian, S., Nerode, A. (eds) Logical Foundations of Computer Science. LFCS 1997. Lecture Notes in Computer Science, vol 1234. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-63045-7_8
Download citation
DOI: https://doi.org/10.1007/3-540-63045-7_8
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63045-6
Online ISBN: 978-3-540-69065-8
eBook Packages: Springer Book Archive