Unrolling Cycles to Decide Trigger Termination
Sin Yeung Lee, Tok Wang Ling · Very Large Data Bases · 1999
Active databases have gained a substantial interest in recent years in enforcing database integrity, however, its current implementations suffer many problems such as running into an infinite loop. While deciding termination is an undecidable task, several works have been proposed to prove termination under certain situations. However, most of these algorithms cannot conclude termination if a cyclic execution actually presents during run-time. This is rather limited. The trigger system can still terminate if these cycles can only be executed a finite number of times. Adopting the trigger graph approach, we propose a method to detect if some cycles can only be executed finitely. We then present a cycleunrolling algorithm to remove those cycles that can only be executed finitely from a trigger graph. Similarly, we present the concept of finitelyupdatable predicate to further improve most existing detection methods. Finally, we conclude with an algorithm to detect if a given trigger system will terminate. ————————————————————— Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantages, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment. Proceedings of the 25th VLDB Conference, Edinburgh, Scotland, 1999.