Many recent proposals for extensions of database management systems advocate the use of a variety of unformatted data types; possible types include text, audio, and image. These data types are proposed in order to support the management of multimedia databases, including document databases and office databases. A distinction between unformatted character data and formatted character data is generally assumed. However, the distinction between these two data types is usually implicit rather than explicit.
Examples of proposals for multimedia information systems or extended database management systems to handle information retrieval applications are presented in Biller (1983), Bancilhon and Richard (1984), Desai, Goyal, and Sadri (1986), Gibbs and Tsichritzis (1983), Harper et al. (1986), Macleod and Reuber (1987), Schek andPistor (1982), andStonebraker et al. (1983). A variety of different approaches have been taken. Often an unformatted character type to handle textual data is provided in addition to a formatted character type; the operations provided generally include some form of pattern matching or full text searching. However, it is sometimes assumed that the textual data has been indexed, and that the critical problem is the management of sets of index terms.
Both formatted and unformatted character data is composed of sequences of characters. However, different operations are appropriate. We consider the following two prototypical operations: sorting and indexing. Sorting involves putting a set of data values in order. Relational operators such as equal to, less than, and greater than must be defined on the data domain in order for an order to be well defined. Indexing involves selecting one or more terms to describe the content