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.