Integration of Active and Deductive Database Rules

Bertram Ludäscher
Abstract. Rules are an important paradigm in database programming. In this work, a state-oriented extension of Datalog called Statelog is proposed, which integrates the dynamic capabilities of active rules and the declarative semantics of deductive rules in a unified logical framework. The basic idea of the language is to incorporate state terms, which allow to refer to different database states within the rule language.

In Statelog, database transactions are modeled as a sequence of intermediate transitions, where each transition is declaratively specified by deductive rules. After briefly reviewing basic notions and the state of the art in active, production, and deductive rules, respectively, a number of theoretical properties of Statelog are investigated:

The expressive power of Statelog is characterized wrt. single transitions and transactions using several normal forms of the language. Moreover, it is shown that certain deductive and production rules correspond to special classes of Statelog programs. The complexity of transitions and transactions is determined based on the established expressiveness results: The problem of deciding whether a given tuple is contained in the result of a transition or transaction is complete for PTIME and PSPACE, respectively. Results on the complexity of detecting termination conclude the first part of the work.

In the second more practically oriented part, a framework for active rules is developed, which uses pure Statelog as the underlying core language. This extended framework provides the user with a set of logically specified, predefined operations, thereby facilitating the handling of low-level procedural aspects. For example, the semantics of primitive updates and transaction control is given by system-defined rules. Using so-called delta-monotonic rules, a method for enforcing rule termination for an efficient subclass of Statelog rules (i.e., with PTIME transaction complexity) is presented. Finally, the handling of static and dynamic integrity constraints, and the possibilities and limitations of composite event detection are investigated. © infix-Verlag, Sankt Augustin, Germany