An Adaptive Algorithm for Incremental Evaluation of Production Rules in Databases
Françoise Fabret, Mireille Régnier, Eric Simon · OpenGrey (Institut de l'Information Scientifique et Technique) · 1993
Several incremental algorithms have been proposed ro evaluate database production rule programs. They all derive from existing incremental algorithms, lke 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 space-time tradeoff. Our major contribution is to propose and 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 space-time 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.