With the rapid growth in the use of computers to manipulate, process, and reason about multimedia data, the problem of how to store and retrieve such data is becoming increasingly important. Thus, although the field of multimedia database systems is only about 5 years old, it is rapidly becoming a focus for much excitement and research effort. Multimedia database systems are intended to provide unified frameworks for requesting and integrating information in a wide variety of formats, such as audio and video data, document data, and image data. Such data often have special storage requirements that are closely coupled to the various kinds of devices that are used for recording and presenting the data, and for each form of data there are often multiple representations and multiple standards – all of which make the database integration task quite complex. Some of the problems include: – what a multimedia database query means – what kinds of languages to use for posing queries – how to develop compilers for such languages – how to develop indexing structures for storing media on ancillary devices – data compression techniques – how to present and author presentations based on user queries. Although approaches are being developed for a number of these problems, they have often been ad hoc in nature, and there is a need to provide a princi- pled theoretical foundation.