Structural totality and constraint stratification
Kenneth Andrew Ross · 1995
In previous work we proposed a condition that generalizes local stratification, that ensures a two-valued well-founded model, and that can be syntactically determined from the rules and some monotonicity constraints on the facts in the program.This condition was called "universal constraint stratification." In this paper we generalize the class of constraints from monotonicity constraints to an arbitrary constraint domain.We generalize universal constraint stratification to the more general case, and prove that the condition always ensures a two-valued wellfounded model for finite databases.We also provide an alternative characterization of local stratification using a version of universal constraint stratification with equality constraints.We extend Papadimitriou and Yannakakis' notion of structural totality.Papadimitriou and Yannakakis proved that a program is structurally total if and only if it is stratified.We extend their notion of structural totality so that schema-level constraint information about the variables in the rules is considered part of the "structure."We prove that, for constraints expressed in certain "exact" constraint domains, a program satisfies our extended notion of structural totality if and only if it is universally constraint stratified.