During the last few years, the advent of the CD-Rom, and the introduction of high bandwidth communications networks has caused a spectacular explosion in the availability of large video- libraries. While a great deal of effort has been invested in problems of how to effectively utilize bandwidth to communicate large bodies of data across the network, relatively little effort has gone into how to organize, and access, video databases. In this paper, we describe how video data may be organized and structured so as to facilitate queries. We develop a formal model of video data and show how spatial data structures, suitably modified, provide an elegant way of storing such data. We develop algorithms to process various kinds of video queries and show that in most cases, the complexity of these algorithms is linear. We develop algorithms to update these video databases. A prototype system called AVIS ("Advanced Video Information System") has been designed at the University of Maryland based on these concepts.