Limitations of rule triggering systems for integrity maintenance in the context of transition specifications

Integrity Maintenance is considered one of the major application fields of rule triggering systems (RTSs). In the case of a given integrity constraint being violated by a database transition these systems trigger repairing actions. Then it is necessary to guarantee the termination of the RTS, its de...

Full description

Saved in:
Bibliographic Details
Main Authors: Schewe Klaus-Dieter
Thalheim Bernhard
Format: Article
Published: 1998
Series:Acta cybernetica 13 No. 3
Kulcsszavak:Számítástechnika, Kibernetika
Subjects:
Online Access:http://acta.bibl.u-szeged.hu/12591
Description
Summary:Integrity Maintenance is considered one of the major application fields of rule triggering systems (RTSs). In the case of a given integrity constraint being violated by a database transition these systems trigger repairing actions. Then it is necessary to guarantee the termination of the RTS, its determinacy and the consistency of final states. Transition specifications provide some kind of dynamic semantics requiring certasin effects on database states to occur. In the context of transition specifications integrity maintenance has to cope with the additional problem of effect preservation. Limitations of RTSs with respect to this extended problems are investigated. It will be shown tha t for any set of constraints there exist nonrepairable transitions, which depend on the closure of the constraint set. This implies tha t integrity maintenance by RTSs is only possible, if the constraint implication problem is decidable. Even if unrepairable transitions are excluded, this does not prevent the RTS to produce undesired behaviour. Analyzing the behaviour of RTSs leads to the definition of critical paths in associated rule hypergraphs and the requirement of such paths being absent. It will be shown tha t this requirement can be satisfied if the underlying set of constraints is stratified, but this notion turns out to be too strong to be also necessary. A sufficient and necessary condition for the absence of critical paths is obtained, if sets of constraints are required to be locally stratified.
Physical Description:277-304
ISSN:0324-721X