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.
Type de document :
[Research Report] RR-1870, INRIA. 1993
Liste complète des métadonnées
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 16:27:29
Dernière modification le : vendredi 25 mai 2018 - 12:02:05
Document(s) archivé(s) le : mardi 12 avril 2011 - 19:27:08



  • 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〉



Consultations de la notice


Téléchargements de fichiers