On cyclic covers and perfect models

摘要

Cyclic covers represent the complex relationships between predicates lying within, and outside of , a perfect model of an indefinite stratified deductive database, and are shown to facilitate the solution to a variety of problems under the perfect model semantics. Cyclic covers are shown to characterise view updates, and this yields a top-down method for solving the view in- sertion problem via the computation of partially cyclic covers and a simple closure operation. Weakly cyclic covers and cyclic trees are shown to yield methods of partially evaluating (i.e., pre-processing) the intensional database to facilitate query compilation, the identification of redundant rules, the removal of recursion and the removal of positive or negative intensional sub-goals. Such pre-processing is immune to future changes in the extensional database. The notion of a conjunctive answer to a database query is introduced. Such answers do not suffer from the problems of redundancy as seen with (the more commonly studied) “disjunctive” answers. In addition, conjunctive answers yield more information about their query than do their disjunctive counterparts, and in particular the set of disjunctive answers can be computed from the set of conjunctive answers, whereas the converse does not hold. Cyclic covers are shown to characterise conjunctive answers, thus yielding a top-down method of computing such answers. The problem of computing conjunctive answers is shown to be a special case of the view update problem.