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.
In order to set up a list of libraries that you have access to,
you must first login
or sign up.
Then set up a personal list of libraries from your profile page by
clicking on your user name at the top right of any screen.