6th. Intl. Conference on Extending Database Technology (EDBT'98) ,
Valencia, Spain, 23-27 March, 1998; LNCS 1377, Springer.

Referential Actions: From Logical Semantics to Implementation

Bertram Ludäscher, Wolfgang May
Abstract. Referential actions (\rac's) are specialized triggers used to automatically maintain referential integrity. While their local effects can be grasped easily, it is far from obvious what the global semantics of a set $RA$ of interacting \rac's should be. To capture the intended meaning of $RA$, we first present an abstract non-constructive semantics. By formalizing $RA$ as a logic program $P_{RA}$, a constructive semantics is obtained. The equivalence of the logic programming semantics and the abstract semantics is proven using a game-theoretic characterization, which provides additional insight into the meaning of \rac's. As shown in previous work, for general \rac's it may be infeasible to compute all \emph{maximal admissible} solutions. Therefore, we focus on a tractable subset, i.e., \rac's without modifications. We show that in this case a unique maximal admissible solution exists, and derive a \ptime\ algorithm for computing this solution. In case a set $U_\rhd$ of user requests is not admissible, a maximal admissible subset of $U_\rhd$ is suggested.