ABSTRACT This work presents efficient algorithms to update knowledge bases in the presence of integrity constraints. The algorithms ensure that the changes to the knowledge bases are minimal. We use the deductive database paradigm to represent knowledge. Minimality is defined as a natural partial order over possible models of the database and expresses a preference for data explicity stored in the database over the data deduced by default. This requirement seems rational for many applications and yet it is hard to (...) be expressed with a set of integrity constraints. We handle safe negation and local variables in the bodies of the rules. We tackle the issue of modifying the active domain (i.e. adding new constants or removing some of the constants which are present in the knowledge base), and we demonstrate how interaction with the user can be used to handle recursive definitions. (shrink)