Technical Report No. 78, March 1996 - Abstract

Bertram Ludäscher, Ulrich Hamann, Georg Lausen:
A Logical Framework for Active Rules

We present a state-oriented extension to Datalog called Statelog which comprises two kinds of rules within a simple, yet flexible unified framework, i.e. (i) passive query rules used to express queries and static integrity constraints, and (ii) active transition rules for defining state-changing operations. We show that Statelog is powerful enough to capture many typical active rule applications (including complex updates, integrity enforcement and incremental view maintenance strategies) while retaining a declarative, set-oriented, and deterministic semantics thus reconciling active and deductive databases. Using the Statelog framework, formal results on termination, expressiveness and complexity of active rules are established which carry over to related state-oriented languages like XY-stratified Datalog. We prove that it is undecidable for general Statelog programs whether a program terminates on all databases. We then develop syntactic criteria which guarantee program termination and investigate the impact of these restrictions on expressive power. The class of Delta-monotone programs extends previous results on Statelog and is of practical importance since it includes self-triggering active rules and expresses all fixpoint transformations. In addition, our syntactic conditions yield an alternative static analysis technique based on the logical notion of monotony whereas previous approaches use execution and triggering graphs.