Preservation of integrity constraints in definite DATALOG programs

Abstract

Given a program P and two sets IC and IC′ of integrity constraints, IC uniformly implies IC′ in P if whenever an (input) database I defined on predicates of P satisfies IC then the (output) database computed by P from I satisfies IC′. P preserves IC if IC uniformly implies IC in P. We consider only definite DATALOG programs. We show that testing preservation of downward-closed integrity constraints can be simplified to the case of single-rule programs that are computed in a "nonrecursive manner". Specially, we present an efficient test algorithm when constraints are equality-generating dependencies. We also show that the uniform implication problem can be similarly simplified if IC is preserved and all given constraints are downward-closed. Our results generalize dependency-preserving database schemes by considering mappings defined by arbitrary definite DATALOG programs and more general integrity constraints. © 1992.