An algebra for creating and querying multimedia presentations

Over the last few years, there has been a tremendous increase in the number of interactive multimedia presentations prepared by different individuals and organizations. In this paper, we present an algebra for creating and qu erying interactive multimedia presentation databases. This algebra operates on trees whose branches reflect different possible playouts of a set of pr esentations. The algebra not only extends all the classical relational oper ators to such databases, but also introduces a variety of novel operators f or combining multiple presentations. As our algebra supports merging parts or all of existing presentations, this algebra can also be used as an autho ring tool for creating multimedia presentations. We prove a host of equival ence results for queries in this algebra, which may be used to build query optimizers for interactive presentation databases.