Andreas Herzig, The PMA Revisited

The so-called Possible Models Approach (PMA) is a minimal change semantics for database updates. In this paper we give a sound and complete decision procedure for the PMA which is based on normal forming. We prove complexity results in particular for the case of updates restricted to conjunctions or disjunctions of literals. Finally, we sketch how integrity constraints can be taken into account.
In: L. C. Aiello, S. Shapiro (Eds.), Proc. KR'96, nov. 1996.
Get Postscript