"Query Scheduling and Optimization in Parallel and Multimedia Databases"
by Minos N. Garofalakis. PhD Thesis, University of Wisconsin - Madison, August 1998.
Abstract
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.