Reflections on Some Fundamental Issues of Rule-Based Incremental Update Propagation

Abstract

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 t...