Some Properties of Query Languages for Bags

Leonid Libkin and Limsoon Wong

Proceedings of 4th International Workshop on Database Programming Languages,
New York, August 1993, pp 97-114.

In this paper we study theoretical foundations for programming with bags. We fully determine the strength of many polynomial bag operators relative to an ambient query language. Then picking the strongest combination of these operators we obtain the yardstick nested bag query language BQL. The relationship between 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. We prove some inexpressibility results for BQL. In particular, it cannot test for any property that is simultaneously infinite and co-infinite (for example, parity). Then non-polynomial primitives such as powerbag, structural recursion and bounded loop are studied. Structural recursion on bags is shown to be strictly more powerful than the powerbag primitive and it is equivalent to the bounded loop operator. Finally, we show that the numerical functions expressible in BQL augmented by structural recursion are precisely the primitive recursive functions.

See here for the paper.


Back Back to DB Group Homepage

sharker@saul.cis.upenn.edu