Towards a Theory of Bulk Types

A database programming language can model application domains most naturally if it supports several bulk types, e.g., lists, sets, and relations. Indeed some persistent programming languages permit the programmer to define new bulk types that are appropriate to the application domain. Such a richly typed language tends to be complex, since constructs must be provided to declare, construct, inspect, and update instances of every bulk type. The collection theory presented here controls the complexity of such richly typed languages by exploiting operations and properties common to a variety of bulk types. The theory is based on four operations -- three constructor operations and one iterator -- that obey certain algebraic laws. In addition, a rich set of additional operations can be defined in terms of the basic operations. Sets, bags, lists, certain trees, relations, and finite mappings are all encompassed by the collection theory. Conversely, types that we would not intuitively classify..