On bulk data type constructors and manipulation primitives: a framework for analyzing expressive power and complexity
Richard A. Hull, Jianwen Su · 1989
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. 1