Handling Termination in a Logical Language for Active Rules

Issue title: Programming Theory, Information System Engineering, Software Engineering, and Artificial Intelligence

Article type: Research Article

Authors: Ludäscher, Bertram | Lausen, Georg

Affiliations: Institut für Informatik Albert-Ludwigs-Universität Freiburg, Am Flughafen 17, 79110 Freiburg i.Br., Germany. E-mail: [email protected]

Abstract: Statelog is a Datalog extension integrating the declarative semantics of deductive rules with the possibility to define updates in the style of active and production rules. The language is surprisingly simple, yet captures many essential features of active rules. After reviewing the basics of active rules, production rules, and deductive rules, we elaborate on the problem of handling rule termination in the context of Statelog: It is undecidable whether a Statelog program terminates for all databases, and PSPACE-complete for a given database. The latter can be accomplished within the logical language: for every Statelog program P, there is a terminating program P↓ which decides for any given database 𝒟, whether P ∪ 𝒟 terminates.

Keywords: active databases, deductive databases, production rules, termination

DOI: 10.3233/INF-1998-9105

Journal: Informatica, vol. 9, no. 1, pp. 65-84, 1998