(Un)decidability results for trigger design theories

Active databases are databases extended with production rules or triggers. Triggers have different uses in databases. Originally they were devised as a more flexible method of constraint enforcement.Triggers have found a much wider use however, because it is possible to code all dynamics of an information system in database triggers.Such use results in the presence of large sets of triggers in an active database. The mutual interaction of triggers in a set can lead to undesired results such as non-termination of trigger execution. To enable us to analyse a trigger set in advance for such behaviour we need a design theory for database triggers. In this report we consider a number of predicates on trigger sets. Most important are termination and confluence. We examine the decidability of these predicates in a number of simple trigger languages. We show that these predicates are decidable for very simple triggers that consists of local conditions and replacement of attribute values. We also show that a very small extension of the trigger language, viz. with non-local conditions, makes these predicates undecidable. The extension of the initial language with arithmetic in the form of the successor function preserves the decidability of termination and confluence.