An Adaptive Algorithm for Incremental Evaluation of Production Rules in Databases

摘要

Several incremental algorithms have been proposed to evaluate database production rule programs. They all derive from existing incremental algorithms, like RETE and TREAT, developed for rule-based systems in the framework of Artificial Intelligence. In this paper, we address a specific but crucial problem that arises with these incremental algorithms: how much data should be profitably materialized and maintained in order to speed-up program evaluation ? We show that the answer exposes to a well known tradeoff. Our major contribution is to propose an adaptive algorithm that takes as input a program of rules and returns for each rule, the set of most profitable relational expressions that should be maintained in order to obtain a good compromise. A notable feature of our algorithm is that it works for both set-oriented and instance-oriented rules. We compare our algorithms with existing incremental algorithms for database production rule programs.