page 1  (19 pages)
2to next section

Extending the Well-Founded and Valid Semantics for Aggregation?

S. Sudarshany

Rm. 2A-212, AT&T Bell Labs.

600 Mountain Ave.

Murray Hill, NJ 07974

sudarsha@research.att.com

tel: (908) 582 7263

fax: (908) 582 5809

Divesh Srivastava

Computer Sciences Department

University of Wisconsin|Madison

Madison, WI 53706

divesh@cs.wisc.edu

Raghu Ramakrishnan

Computer Sciences Department

University of Wisconsin|Madison

Madison, WI 53706

raghu@cs.wisc.edu

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-well-founded semantics, more intuitive than the extension of well-founded models by Van Gelder [Van92]. Our semantics and Van Gelder's semantics agree on many programs, and on others our semantics provides results that Van Gelder says are intuitive and desirable, but that his semantics does not provide. The extended valid semantics, which we call the aggregate-valid semantics, generalizes the intuition behind several semantics presented earlier for aggregation; for instance, our semantics properly subsumes the semantics defined by Ganguly et al. [GGZ91] for cost-monotonic programs.

Keywords: deductive databases, logical extensions, proof theory, non-stratified aggregation

?The work of Raghu Ramakrishnan and Divesh Srivastava was supported by a David and Lucile Packard Foundation Fellowship in Science and Engineering, a Presidential Young Investigator Award with matching grants from DEC, Tandem and Xerox, and NSF grant IRI-9011563. The first author, on behalf of all those alphabetic-order challenged, led a successful crusade to have the names in reverse alphabetical order. The order does not reflect on the degree of contribution by the various authors. Extensions planned for the future include height and weight ordering of authors.
yAll communication may be addressed to the first author.