Abstract
We define a new property of steady behavior of dynamic deductive data bases interacting with their active medium. This property is in fact the homeostaticity, i.e. the ability of the database to restore its integrity constraints after ruinous disturbances of its medium. The formal model we use is based on a new concept, that of bounded disturbance of an active medium. We explore the computational complexity of this property in various classes of dynamic deductive data bases.
This work was sponsored by INTAS (Grant 94-2412) and by the Russian Foundation for Basic Research (Grant 95-01-01321).
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abiteboul, S., Vianu, V., Datalog extensions for database queries and updates, I.N.R.I.A. Technical Report No. 900, 1988.
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.
Bonner, A.J., Hypothetical Datalog: complexity and expressibility. Theoretical Computer Science, 76, 3–51, 1990.
Bonner, A.G., Kifer, M., Transaction logic programing, In Proc. of the Tenth Intern. Conf. on Logic Programming. The MIT Press, 257–279, 1993.
Chandra, A.K., Kozen, D.C., Stockmeyer, L.J., Alternation. J. Ass. Comput. Mach., v.28, n.1, 114–133, 1981.
Dekhtyar, M.I., Dikovsky, A.Ja., Dynamic deductive databases. Izvestiya of Russian Acad. of Sci. Technical Cybernetics, n.5, 1994, (Russ).
Dekhtyar, M.I., Dikovsky, A.Ja., Dynamic Deductive Data Bases with Steady Behavior. In Proc. of The 12th International Conf. on Logic Programming, (Ed. L. Sterling), The MIT Press, 183–197, 1995.
Dekhtyar, M.I., Dikovsky, A.Ja., Properties of Steady Behavior of Dynamic De-ductive Data Bases. Part I. ∃∃-stability and Promise. Technical rept. 95-07, Universite Paris XII-Val de Marne, Septembre 1995, 1–26.
Dung, P.M., Representing actions in logic programming and its application in database updates. In Proc. of the Tenth Intern. Conf. on Logic Programming. The MIT Press, 222–238, 1993.
Eiter, T., Gottlob, G., On the complexity of propositional knowledge base revision, updates, and counterfactuals. Artificial Intelligence, vol. 57, 227–270, 1992.
Gallaire, H., Minker, J., Nicolas, J.-M., Logic and databases: a deductive approach. ACM Computing Surveys, vol. 16, n.2, 153–185, 1984.
Halfeld Ferrari Alves, M., Laurent, D., Spyratos, N., Stamate, D., Update rules and revision programs. Rapport de Recherche n. 1010, 12 / 1995, 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.
Manchanda, S., Warren, D.S., A logic-based language for database updates. In J. Minker, editor, Foundations of Deductive Databases and Logic Programming, Morgan-Kaufmann, Los Altos, CA, 363–394, 1988.
Marek, V.W., Truszcińsky, M. Revision programming, database updates and integrity constraints. In International Conference on Data Base theory, ICDT, LNCS n. 893.
Naqvi, S., Krishnamurthy, R., Database updates in logic programming. In ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 251–262, 1988.
Sadri, F., Kowalski, R., A theorem proving approach to database integrity. In J. Minker, editor, Foundations of Deductive Databases and Logic Programming, Morgan-Kaufmann, Los Altos, CA, 313–362, 1988.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dekhtyar, M.I., Dikovsky, A.J. (1996). On homeostatic behavior of dynamic deductive data bases. In: Bjørner, D., Broy, M., Pottosin, I.V. (eds) Perspectives of System Informatics. PSI 1996. Lecture Notes in Computer Science, vol 1181. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-62064-8_35
Download citation
DOI: https://doi.org/10.1007/3-540-62064-8_35
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-62064-8
Online ISBN: 978-3-540-49637-3
eBook Packages: Springer Book Archive