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.
[edbt98.ps.gz]