"Query Scheduling and Optimization in Parallel and Multimedia Databases"

by Minos N. Garofalakis. PhD Thesis, University of Wisconsin - Madison, August 1998.


Effective resource management support for parallelism and multimedia data is an important mandate for next-generation information systems. In this thesis, we address a number of resource scheduling issues that arise in the context of query processing and optimization in parallel and multimedia databases. Our contributions to the area of parallel databases include the development of a multi-dimensional framework and provably near-optimal algorithms for scheduling both Time-Shared and Space-Shared resources in hierarchical and shared-nothing architectures. We also present results from the implementation of our algorithms on top of a detailed simulation model that verify their effectiveness in a realistic setting. Based on our scheduling results, we identify a novel cost model for parallel query optimization that manages to capture all the important execution characteristics of a parallel query plan in only three ``bulk'' parameters. In the field of multimedia databases, our contributions span the areas of resource scheduling for composite multimedia objects, on-line admission control for multimedia databases, and scheduling support for periodic (i.e., ``Pay-Per-View''-style) models of user service. In all cases, we propose novel algorithmic formulations and solutions and we study their performance both analytically and experimentally.

[ thesis (ps) (pdf) | defense slides (ps.gz) ]