SEMANTICS FOR UPDATE RULE PROGRAMS AND IMPLEMENTATION IN A RELATIONALDATABASE-MANAGEMENT SYSTEM

In this paper we present our research on defining a correct semantics for a class of update rule (UR) programs, and discuss implementing the se programs in a DBMS environment. Update rules execute by updating re lations in a database which may cause the further execution of rules. A correct semantics must guarantee that the execution of the rules wil l terminate and that it will produce a minimal updated database. The c lass of UR programs is syntactically identified, based upon a concept that is similar to stratification. We extend the strict definition of stratification and allow a relaxed criterion for partitioning of the r ules in the UR program. This relaxation allows a limited degree of non determinism in rule execution. We define an execution semantics based upon a monotonic fixpoint operator T-UR, resulting in a set of fixpoin ts for UR. The monotonicity of the operator is maintained by explicitl y representing the effect of asserting and retracting tuples in the da tabase. A declarative semantics for the update rule program is obtaine d by associating a normal logic program UR to represent the UR program . We use the stable model semantics which characterize a normal logic program by a set of minimal models which are called stable models. We show the equivalence between the set of fixpoints for UR and the set o f stable models for UR. We briefly discuss implementing the fixpoint s emantics of the UR program in a DBMS environment. Relations that can b e updated by the rules are updatable relations and they are extended w ith two flags. An update rule is represented by a database query, whic h queries the updatable relations as well as database relations, i.e., those relations which are not updated by rules. We describe an algori thm to process the queries and compute a fixpoint in the DBMS environm ent and obtain a final database.