Extending the Well-Founded and Valid Semantics for Aggregation

Abstract

We present a very general technique for defining semantics for programs that use aggregation. We use the technique to extend the well-founded semantics and the valid semantics, both of which were designed to provide semantics for programs with negation, to handle programs that contain possibly recursive use of aggregation. The generalization is based on a simple but powerful idea of aggregation on three-valued multisets. The use of three-valued multisets makes our extended well-founded semantics, which we call aggregate-wellfounded semantics, easier to understand and more intuitive, in our opinion, than the extension of well-founded models by Van Gelder [14]. 1 Introduction In recent years there has been much interest in defining semantics for deductive databases/logic programs that use negation and aggregation. We call such programs extended logic programs. Early approaches restricted the class of programs to those that are stratified in some fashion [1, 8, 12]. More recent approache...