Understanding the Global Semantics of Referential Actions using Logic Rules
Wolfgang May , Bertram Ludäscher
Abstract:
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.