PARALLEL DATABASES: In hierarchical parallel systems, each site consists of a collection of local time-shared (e.g., CPU(s) or disk(s)) and space-shared (e.g., memory) resources and communicates with remote sites by message-passing. We discuss a novel general approach to the problem of query scheduling in such systems, capturing the full complexity of distributed multi-dimensional resource units, and all forms of parallelism within and across queries and operators. We present a heuristic scheduling algorithm that is provably near-optimal for independent query tasks (i.e., operator pipelines) and very effective for handling general queries as experiments have confirmed. Our findings also lead to a novel efficient cost model for parallel query optimization that captures all the important parameters of parallel execution.
MULTIMEDIA DATABASES: The Enhanced Pay-Per-View (EPPV) service model for Continuous Media (CM) databases associates with each CM clip a display frequency which depends on the clip's popularity. The aim is to increase the number of clients that can be serviced concurrently at any given time beyond the capacity limitations of available resources, while guaranteeing a constraint on the response time. This is achieved by sharing periodic continuous media streams among multiple clients. Maximizing system utilization under EPPV gives rise to NP-hard combinatorial optimization problems that fall within the realm of hard real-time scheduling theory. Given the intractability of the problems, we propose novel heuristic scheduling algorithms with polynomial time complexity. We also present results from an experimental evaluation of the proposed schemes.