Termination and Confluence of Rule Execution

• Main Authors: M.H. van der Voort, A.P.J.M. Siebes, Leonie Van Der Voort, Arno Siebes
• Other Authors: The Pennsylvania State University CiteSeerX Archives
• Format: Text
• Language: English
• Published: Springer-Verlag 1993
• Subjects: 1991 CR Categories; H.2.1[Information Systems; Logical Design- data models; H.2.3[Information Systems; Languages- data description languages(DDL; data manipulation languages(DML; DML
• Online Access: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.5400

Rules provide the functionality for constraint enforcement and view maintenance. A provably correct implementation of both issues based on rules, requires confluent and terminating behaviour of the rule set. However, little work has been done so far on the static detection of these properties. In this paper, a design theory for rule sets in an OODBMS is developed. This paper introduces two predicates, viz., Terminate(n) and Independent, which imply respectively termination and confluency. Both predicates are characterised under two kinds of rule execution semantics: set and instance based. The decidability of the predicates is proven and it is shown that set and instance based semantics coincide whenever the rule set is independent and terminates. Moreover, sufficient conditions of low algorithmic complexity for both Terminate(n) and Independent under both kinds of semantics are given. 1991 CR Categories: H.2.1[Information Systems]: Logical Design- data models; H.2.3[Informat.