Abstract
Update propagation in deductive databases can be implemented by combining rule rewriting and fixpoint computation, analogous to the way how query answering is performed via Magic Sets. For efficiency reasons, bottom-up propagation rules have to be subject to Magic rewriting, thus possibly loosing stratifiability. We propose to use the soft stratification approach for computing the well-founded model of the magic propagation rules (guaranteed to be two-valued) because of the simplicity and efficiency of this technique.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Apt, K.R., Blair, H.A., Walker, A.: Towards a theory of declarative knowledge. Foundations of Deductive Databases and Logic Programs, pp. 89–148. M. Kaufmann, San Francisco (1988)
Balbin, I., Port, G.S., Ramamohanarao, K., Meenakshi, K.: Efficient bottom-up computation of queries. JLP 11(3&4), 295–344 (1991)
Baralis, E., Widom, J.: A rewriting technique for using delta relations to improve condition evaluation in active databases. Technical Report CS-93-1495, Stanford University (November 1993)
Behrend, A.: Soft stratification for magic set based query evaluation in deductive databases. In: PODS 2003, New York, June 9–12, pp. 102–110 (2003)
Ceri, S., Widom, J.: Deriving incremental production rules for deductive data. Information Systems 19(6), 467–490 (1994)
Griefahn, U.: Reactive Model Computation–A Uniform Approach to the Implementation of Deductive Databases. PhD Thesis, University of Bonn (1997)
Griffin, T., Libkin, L.: Incremental maintenance of views with duplicates. In: SIGMOD 1995, San Jose, May 23-25, pp. 328–339 (1995)
Gupta, A., Mumick, I.S., Ross, K.A.: Adapting materialized views after redefinitions. In: SIGMOD 1995, vol. 24(2), pp. 211–222 (1995)
Gupta, A., Mumick, I.S., Subrahmanian, V.S.: Maintaining views incrementally. In: SIGMOD, vol. 22(2), pp. 157–166 (1993)
Küchenhoff, V.: On the efficient computation of the difference between consecutive database states. In: Delobel, C., Masunaga, Y., Kifer, M. (eds.) DOOD 1991. LNCS, vol. 566, pp. 478–502. Springer, Heidelberg (1991)
Levy, A.Y., Sagiv, Y.: Queries Independent of Updates. In: VLDB 1993, pp. 171–181. Morgan Kaufmann, San Francisco (1993)
Manthey, R.: Reflections on some fundamental issues of rule-based incremental update propagation. In: DAISD 1994, September 19-21, pp. 255–276 (1994)
Martens, B., Bruynooghe, M.: Integrity constraint checking in deductive databases using a rule/goal graph. In: EDS 1988, pp. 567–601 (1988)
Moerkotte, G., Karl, S.: Efficient consistency control in deductive databases. In: Gyssens, M., Van Gucht, D., Paredaens, J. (eds.) ICDT 1988. LNCS, vol. 326, pp. 118–128. Springer, Heidelberg (1988)
Mumick, I.S., Pirahesh, H.: Implementation of magic-sets in a relational database system. In: SIGMOD, vol. 23(2), pp. 103–114 (1994)
Naughton, J.F., Ramakrishnan, R., Sagiv, Y., Ullman, J.D.: Efficient Evaluation of Right-, Left-, and Multi-Linear Rules. In: SIGMOD 1989, pp. 235–242 (1989)
Olivé, A.: Integrity constraints checking in deductive databases. In: VLDB, pp. 513–523 (1991)
Sadri, F., Kowalski, R.A.: A theorem proving approach to database integrity. In: Foundations of Deductive Databases and Logic Programs, pp. 313–362. M. Kaufmann, San Francisco (1988)
T. Urpí, A. Olivé. A method for change computation in deductive databases. In: VLDB 1992, Vancouver, August 23-27, pages 225–237 (1992)
van Gelder, A.: The alternating fixpoint of logic programs with negation. Journal of Computer and System Sciences 47(1), 185–221 (1993)
Vieille, L., Bayer, P., Küchenhoff, V.: Integrity checking and materialized views handling by update propagation in the EKS-V1 system. Technical Report TR-KB-35, ECRC, München (June 1991)
Wüthrich, B.: Detecing inconsistencies in deductive databases. Technical Report 1990TR-123, Swiss Federal Institute of Technology, ETH (1990)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Behrend, A., Manthey, R. (2004). Update Propagation in Deductive Databases Using Soft Stratification. In: Benczúr, A., Demetrovics, J., Gottlob, G. (eds) Advances in Databases and Information Systems. ADBIS 2004. Lecture Notes in Computer Science, vol 3255. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30204-9_2
Download citation
DOI: https://doi.org/10.1007/978-3-540-30204-9_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-23243-8
Online ISBN: 978-3-540-30204-9
eBook Packages: Springer Book Archive