Query languages for bags and aggregate functions

Theoretical foundations for querying databases based on bags are studied in this paper. We fully determine the strength of many polynomial-time bag operators relative to an ambient query language. Then we obtain BQL, a query language for bags, by picking the strongest combination of these operators. The relationship between the nested relational algebra and various fragments of BQL is investigated. The precise amount of extra power that BQL possesses over the nested relational algebra is determined. It is shown that the additional expressiveness of BQL amounts to adding aggregate functions to a relational language. The expressive power of BQL and related languages is investigated in depth. We prove that these languages possess the conservative extension property. That is, the expressibility of queries in these languages is independent of the nesting height of intermediate data. Using this result, we show that recursive queries, such as transitive closure, are not denable in BQL. A new tool for analyzing expressibility, called the bounded degree property, is also introduced and we show how it can be used on relational languages. To enhance the expressiveness of BQL, we consider non-polynomial primitives such as powerbag, structural recursion, and bounded loop. Structural recursion on bags is shown to be equivalent to the bounded loop operator and strictly more powerful than the powerbag primitive. We show that the class of numerical functions expressible in BQL augmented by structural recursion is precisely the class of primitive recursive functions.