A Logical Framework for Active Rules
Bertram Ludäscher, Ulrich Hamann, Georg Lausen
Abstract. 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.
[.ps.gz]