Investigating Termination in Active Database

Systems with Expressive Rule Languages

Anca Vaduva, Stella Gatziu, Klaus R. Dittrich

Technical Report 97.03, April 97

Institut f?r Informatik, Universit?t Z?rich
{vaduva, gatziu, dittrich}@ifi.unizh.ch

Abstract
The powerful functionality that active mechanisms add to database management systems presents, besides many advantages, a number of problems related to the control of their behavior. This paper deals with one of these problems: the termination of rule execution. We explain the termination aspect and the aim of termination analysis. Then, we present our approach for investigating the termination of rule execution. In contrast to others, this approach also addresses expressive rule languages as they have been proposed for various recent active database management system prototypes.

1 Introduction

Many applications from areas like workflow management, network management, finance, medicine and transportation show some sort of active behavior and are thus well-suited for support by active database management systems (active DBMS). Accordingly, much research has been done in the area so far, e.g., towards the integration of active mechanisms into relational and object-oriented database management systems, the support of language constructs for the modeling of reactive behavior, the development of concepts for rule execution, or the investigation of architectural issues for the construction of an active DBMS. A number of prototypes have been built, including Starburst [19], POSTGRES [16], ACCOD [5], REACH [6], Sentinel [7], NAOS [8], Ode [11], Ariel [13], TriGS [14], Chimera [19], and SAMOS [10].

Although the advantages of active DBMS are nowadays well-known, they are still not widely used in practice. This is even true for simple active mechanisms like triggers in relational systems which are commercially available since several years. One main problem is that especially for large rule sets, defined by different people at different points in time, rule behavior and potential conflicts and dependencies between rules are hard to predict. One critical aspect is how to guarantee the termination of rule execution, i.e., how to avoid the faulty behavior when rules trigger each other indefinitely (?nontermination?).

There are two ways to approach this problem. One way is to handle termination just during rule execution. This means that the system would stop rule execution if it assumes that an infinitely cascading triggering is taking place (e.g., if a specific upper bound of triggered rules has