Aggregate functions, conservative extension, and linear orders

Practical database query languages are usually equipped with some aggregate functions. For example, \ nd mean of column " can be expressed in SQL. However, the manner in which aggregate functions were introduced in these query languages leaves something to be desired. Breazu-Tannen, Buneman, and Wong [3] introduced a nested relational languageNRC(=) based on monads [16, 24] and structural recursion [1, 2]. It was shown in Wong [27] that this language is equivalent to the nested relational algebras of Thomas and Fischer [22], Schek and Scholl [20], and Colby [4]. NRC(=) enjoys certain advantages over these languages: it is naturally embedded in functional languages, it is readily extensible, and it has a compact equational theory. Therefore, it is used in this report as a basis for investigating aggregate functions. In section 2, the nested relational calculus NRC(=) is described. It is then endowed with rational numbers, rational arithmetic, and a summation operator. The augmented language,NRC(Q; +; ; ; ; P; =), is able to express a variet