Constructing interpretations of deductive databases using reduction and dynamic stratification

摘要

The family of dynamic interpretations for unstratified deductive databases is introduced and studied. Such interpretations are defined from a base semantics using dynamic stratification (which in turn relies upon any natural stratification of the database), and reduction operators (which eliminate rules and dependencies which spuriously affect the natural stratification). Dynamic interpretations coincide with perfect models in the stratified case, and can also be employed to construct perfect models of disjunctive stratified databases. We characterise precisely those dynamic interpretations that are consistent with the well-founded model, and show that a certain class of dynamic interpretations coincides with stable models. We also present briefly a class of dynamic interpretations that can be regarded as being analogous to extensions of the well-founded model such as WFS, GWFS, EWFS and WFS+.