Referential actions are specialized triggers for automatically
maintaining referential integrity in databases. While the
local effects of referential actions can be grasped easily,
it is far from obvious what the global semantics of a set of
interacting referential actions should be. In particular, when
using procedural execution models, ambiguities due to the execution
ordering can occur. No global, declarative semantics of
referential actions has been defined yet.
We show that the well-known logic programming semantics provide a
natural global semantics of referential actions that is
based on their local characterization: To capture the
global meaning of a set RA of referential actions, we first
define their abstract (but non-constructive) intended
semantics. Next, we formalize RA as a
logic program PRA. The declarative, logic
programming semantics of PRA then provide the
constructive, global semantics of the referential actions.
So, we do not define a semantics for referential actions,
but we show that there exists a unique natural
semantics if one is ready to accept (i) the intuitive local
semantics of local referential actions, (ii) the formalization of
those and of the local "effect-propagating" rules, and (iii) the
well-founded or stable model semantics from logic programming as
"reasonable" global semantics for local rules.
We first focus on the subset of referential actions for deletions
only. We prove the equivalence of the logic programming
semantics and the abstract semantics via a game-theoretic
characterization, which provides additional insight into the meaning
of interacting referential actions. In this case a
unique maximal admissible solution exists, computable by a
PTIME algorithm.
Second, we investigate the general case, i.e. including
modifications. We show that in this case there can be multiple
maximal admissible subsets and that all maximal admissible
subsets can be characterized as 3-valued stable models of
PRA. We show that for a given set of user
requests, in presence of referential actions of the form ON
UPDATE CASCADE, the admissibility check and the computation of
the subsequent database state, and (for non-admissible updates) the
derivation of debugging hints all are in PTIME. Thus, full
referential actions can be implemented efficiently.
