1990 Reports

Incremental Evaluation of Rules and its Relationship to Parallelism

Wolfson, Ouri; Dewan, Hasanat; Stolfo, Salvatore; Yemini, Yechiam

Rule interpreters usually start with an initial database and perform the inference procedure in cycles, ending with a final database. In a real time environment it is possible to receive updates to the initial database after the inference procedure has started or even after it has ended. We present an algorithm for incremental maintenance of the deductive database in the presence of such updates. Interestingly, the same algorithm is useful for parallel and distributed rule processing in the following sense. \\'hen the processors evaluating a program operate asynchronously. then they may have different views of the database. The incremental maintenance procedure we present can be used to synchronize these views.