Institute for Informatics
Georg-August-Universität Göttingen

Databases and Information Systems

Uni Göttingen

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

Referential Actions: From Logical Semantics to Implementation

Bertram Ludäscher, Wolfgang May


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 PRA, 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 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 of user requests is not admissible, a maximal admissible subset of U is suggested.


This paper elaborates on the practical aspects of

An extended version can be found in