Model generation in disjunctive normal databases

Abstract

Algorithms for computing several classes of models for disjunctive normal databases are presented. We show how to e ciently compute minimal, restricted minimal, perfect, and stable models. The common feature of the advanced algorithms is that they are based on augmenting a model generating procedure with a set of hypotheses to guide its search for acceptable models and/or to interpret negation in clause bodies. The approach is shown to be useful for di erent database applications including query answering under di erent semantics and integrity constraint enforcement. The developed algorithms are easy to implement and compare favorably with others advanced in the literature for the same purpose