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
Complete list of metadatas

https://hal.inria.fr/inria-00074803
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 4:27:29 PM
Last modification on : Friday, May 25, 2018 - 12:02:05 PM
Long-term archiving on : Tuesday, April 12, 2011 - 7:27:08 PM

Identifiers

  • HAL Id : inria-00074803, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

167

Files downloads

66