Welcome to DiSC 2003
SIGMOD 2002
PODS 2002
SIGMOD RECORD 2002
ADBIS 2002
CIKM 2002
CoopIS 2002
EDBT 2002
ER 2002
Data Engineering Bul
DEXA_EC-WEB 2002
DMKD 2002
DPDJ 2002
HYPERTEXT 2002
ICDE 2002
ICDM 2002
JCDL 2002
KDD 2002
KDD_EXPLORATIONS 20
KRDB 2002
MDM 2002
MIS 2002
RIDE 2002
SBBD 2002
SIGIR 2002
SIGIR FORUM 2002
SSDBM 2002
TODS 2002
<<< = TODS'02 Issues>>>
TIME 2002
VLDB 2002
VLDBJ 2002

Understanding the global semantics of referential actions using logic rules


Wolfgang May and Bertram Ludäscher

  View Paper (PDF)  

Return to Number 4, December 2002


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 yet been defined.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---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 the 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.


DiSC'03 © 2003 Association for Computing Machinery