Accessing and processing distributed data sources have become important factors for businesses today. This is especially true for the emerging virtual enterprises with their data and processing capabilities spread across the Internet. Unfortunately, however, query processing on the Internet is not predictable and robust enough to meet the requirements of many business applications. For instance, the response time of a query can be unexpectedly high; or the monetary cost might be too high if the partners charge for the usage of their data or processing capabilities; or the result of the query might be useless because it is based on outdated data or only on parts (rather than all) of the available data. In this work, we show how a distributed query processor can be extended in order to support quality of service (QoS) guarantees. We propose ways to integrate QoS management into the various phases of query processing: (1) Query optimization uses a multi-dimensional assessment (cost, time and result quality) of query plans, (2) query plan instantiation comprises an admission control for sub-plans, and (3) during query plan execution the QoS of the query is monitored and a fuzzy controller initiates repairing actions if needed. The goal of our work is to provide an initial step towards QoS management in distributed query processing systems and do significantly better than current distributed database systems, which are based on a best-effort policy.

Semi-join reducers were introduced in the late 1970s as a means to reduce the communication costs of distributed database systems. Subsequent work in the 1980s showed, however, that semi-join reducers are rarely beneficial for the distributed systems of that time. This paper shows that semi-join reducers can indeed be beneficial in modern client-server or middleware systems - either to reduce communication costs or to better exploit all the resources of a system. Furthermore, we present and evaluate alternative ways to extend state-of-the-art (dynamic programming) query optimizers in order to generate good query plans with semi-join reducers. We present two variants, called Access Root and Join Root, which differ in their implementation complexity, running times and the quality of the plans they produce. We present the results of performance experiments that compare both variants with a traditional query optimizer.

Naturally, data processing requires three kinds of resources: