On bulk data type constructors and manipulation primitives - a framework for analyzing expressive power and complexity

We present a framework for analyzing the complexity and expressive power of many existing languages for manipulating information in bulk data types. The framework is based on four dimensions: the \cardinality measure " of the underlying data model � procedural vs. declarative� the presence of iteration � and the presence of \invention". Several languages from the literature which correspond to various combinations of these dimensions are categorized into ve families of queries, ranging from QLOGSPACE to a family which is more expressive than the computable queries.