Monotone expansions of updates in logical databases

Abstract. To find a minimal real change after an update of a database with integrity constraints (IC) expressed by an extended logic program is proven to be a Σp2-complete problem. We define a class of operators expanding the input updates correctly with respect to the IC. The par-ticular monotone expansion operator we describe is incrementally com-puted in square time. It provides a practical optimization of the standard complete choice algorithm resolving the update problem.