Skip to Main content Skip to Navigation
New interface
Reports (Research report)

An Adaptative algorithm for incremental evaluation of production rules in databases

Françoise Fabret 1 Mireille Regnier 2 Eric Simon 1 
1 RODIN - Database Systems
Inria Paris-Rocquencourt
2 ALGO - Algorithms
Inria Paris-Rocquencourt
Abstract : 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.
Document type :
Reports (Research report)
Complete list of metadata
Contributor : Rapport De Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 4:27:29 PM
Last modification on : Wednesday, October 26, 2022 - 8:16:51 AM
Long-term archiving on: : Tuesday, April 12, 2011 - 7:27:08 PM


  • HAL Id : inria-00074803, version 1



Françoise Fabret, Mireille Regnier, Eric Simon. An Adaptative algorithm for incremental evaluation of production rules in databases. [Research Report] RR-1870, INRIA. 1993. ⟨inria-00074803⟩



Record views


Files downloads