Decidability and Undecidability Results for the Termination Problem of Active Database Rules.


James Bailey, King's College London

Guozhu Dong, The University of Melbourne

Ramamohanarao Kotagiri, The University of Melbourne


ACM Symposium on Principles of Database Systems (PODS), Seattle, 1998, pages 264-273.


Abstract

Active database systems enhance the functionality of traditional databases through the use of active rules or `triggers'. One of the principal questions for such systems %for sets of rules is that of {\em termination} -- is it possible for the rules to recursively activate one another indefinitely, given an initial triggering event. In this paper, we study the decidability of the termination problem, our aim being to delimit the boundary between the decidable and the undecidable. We present two families of rule languages, the {\em one literal} languages where each update is permitted to have just one atom in its body, and the {\em unary} languages where only unary relations may be updated, but higher arity relations may be accessed through views. Within each of these, we identify members close to the boundary of (un)decidability. Our context is similar to the {\em while} query language and the dynamics gives an interesting contrast to Datalog with negation; our results shed insights on the power of triggers as well as comparison of the termination problem to boundedness and query containment.