An algebraic approach to static analysis of active database rules

Rules in active database systems can be very difficult to program due to th e unstructured and unpredictable nature of rule processing. We provide stat ic analysis techniques for predicting whether a given rule set is guarantee d to terminate and whether rule execution is confluent (guaranteed to have a unique final state). Our methods are based on previous techniques for ana lyzing rules in active database systems. We improve considerably on the pre vious techniques by providing analysis criteria that are much less conserva tive: our methods often determine that a rule set Will terminate or is conf luent when previous methods could pot make this determination; Our improved analysis is based on a "propagation" algorithm, which uses an extended rel ational algebra to accurately determine when the action of one rule can aff ect the condition of another, and determine when rule actions commute. We c onsider both condition-action rules and event-condition-action rules, makin g our approach widely applicable to relational active database rule languag es and to the trigger language in the SQL:1999 standard.