A Multimedia Presentation Algebra

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 querying multimedia presentation databases. In contrast to the relational algebra, an algebra for interactive multimedia presentations must operate on trees whose branches reflect different possible playouts of a family of presentations. The query language supports selection type operations for locating objects and presentation paths that are of interest to the user, join type operations for combining presentations from multiple databases into a single presentation, and finally set theoretic operations for comparing different databases. The algebra operations can be used to locate presentations with specific properties and also for creating new presentations by borrowing different components from existing ones. We prove a host of equivalence results for queries in this algebra which may be used to build query optimizers for interactive presentation databases.