Databases with integrity constraints (IC) are considered. For each DB update, i.e. a set of facts to add and of facts to delete,
the IC implies its
correct expansion: new facts to add and new facts to delete. Simultaneously, each expanded update induces a
correct simplification of the IC. In the limit this sequence of expansions and simplifications converges to the maximal correct update expansion
independent from the initial DB state.
We show that such maximal expansion is computed in square time for partial databases, and that its computation is a co-N P-complete problem in classical databases. However, it is also square time computable in classical DBs under ICs with some
restrictions on the use of negation. Computing the real change of the initial DB state after accomplishing an update is a
hard problem. The use of maximal update expansion in the place of initial update can substantially simplify computation of
a new correct DB state.
This work was sponsored by the Russian Fundamental Studies Foundation (Grants 97-01-00973, 98-01-00204, 99-01-00374).