Technical Report No. 70, September 1995 - Abstract

Bertram Ludäscher, Ulrich Hamann, Georg Lausen:
Reconciling Active and Deductive Databases by States

We propose a state-oriented extension to Datalog called Statelog which comprises two kinds of rules, passive query rules and active transition rules within a simple, yet flexible logical framework. Statelog programs have deterministic model-theoretic semantics for queries and updates thus reconciling active and deductive databases. Using the Statelog framework we prove that termination of active rules is undecidable in general and introduce the class of Delta-monotone programs for which termination is guaranteed. This class provides a generalization to previous results for Statelog and is of practical importance as it includes self-triggering recursive rules. Formal results characterizing the expressiveness and complexity are established which carry over to related state-oriented extensions of Datalog.