Aggregation in Functional Query Languages ∗

We consider the problem of improving the computational efficiency of a functional query language. Our focus is on aggregate operations which have proven to be of practical interest in database querying. Since aggregate operations are typically non-monotonic in nature, recursive programs making use of aggregate operations must be suitably restricted in order that they have a well-defined meaning. In a recent paper we showed that partial-order clauses provide a well-structured means of formulating such queries. The present paper extends earlier work in exploring the notion of declarative pruning. By “declarative pruning ” we mean that the programmer can specify declarative information about certain functions in the program without altering the meanings of these functions. Using this information, our proposed execution model provides for more efficient program execution. Essentially we require that certain domains must be totally-ordered (as opposed to being partially-ordered). Given this information, we show how the search space of solutions can be pruned efficiently. The paper presents examples illustrating the language and its computation model, and also presents a formal operational semantics.