Improving integrity constraint checking in deductive databases

In this paper the description of a new method for integrity constraints checking in deductive databases is given and its correctness is proved. Our method extends and integrates two well known approaches to the literature, namely [Lloyd&Topor 85], [Lloyd&Topor 86], [Lloyd et al. 87] that has been proposed for stratified databases [Apt et al. 87], and [Nicolas 82] that was instead proposed for relational databases. Like in the other approaches we assume that the database satisfies the integrity constraints before the update and, therefore, any new violation of the constraints must involve the update, so that, it Wi11 be sufficient to check the instances of those constraints which could be invalidated by the update. Our method tries to minimize, as much as possible the number of constraint instances to be checked, it works on stratified databases, thus including definite and hierarchical databases, and on the same kind of constraint formulas of [Lloyd et al. 87].