Institute of Computer Science III
University of Bonn
Databases * Information Systems * Software Engineering *
Pattern Recognition * Image Processing * Artificial Intelligence * Robotics
Reflections on Some Fundamental Issues of Rule-Based Incremental Update Propagation
This paper addresses two fundamental aspects of update propagation in deductive databases:
1. How to incrementally compute the sets of updates induced by a deductive rule from the changes of the data sets on which the rule depends? and
2. How to express such incremental definitions by means of deductive rules defining induced updates?
Both problems have already been addressed by many authors in various contexts. The motivation for coming up with yet another such paper comes from the impression that some of the very basic assumptions and justifications of the approaches proposed in literature have not been understood well enough. In this paper we therefore investigate the basic algebraic laws of incremental change computation as well as their direct encoding in form of deductive rules from a new perspective. In addition we address the problems arising when the entire process of update propagation is driven by a (semi-)naive fixpoint procedure applied to the rules encoding the incremental definitions of induced updates.
Click here to obtain the full paper (PS, gzip, 62234 bytes, 22 pages)
webmaster@www.informatik.uni-bonn.de -
16.12.05