Improving the performance of heterogeneous databases and agents

Today's applications require the ability to access and query multiple heterogeneous data sources. Heterogeneous databases (HDB) and heterogeneous agent systems provide the necessary means to attain this goal. A common characteristics of such HDB and agent systems is that they simultaneously process large numbers of queries/requests. The ability to efficiently handle large volumes of simultaneous queries is critical in many such applications.; In this thesis, we present various query optimization techniques to improve the performance of such heavily loaded HDB and agent systems. Since cost models play a key role in query optimization, we first propose a framework through which a heterogeneous system can obtain cost and cardinality information required for optimization. Our approach is the first to adapt a traditional System-R style optimizer to perform costing in a heterogeneous environment.; Another important problem in a heterogeneous system deployed over wide area networks, such as the Internet, is the duplication of data and services. Since different sources have varying characteristics, choosing the right set of sources to answer a user query has critical performance implications. In this thesis, we first formalize this problem as the source selection problem and show that it is NP-hard. We then propose one optimal and two heuristic based algorithms to address source selection problem.; As the next step to optimize the performance of HDB and agent systems, we propose a set of cost-based multiple query optimization (MQO) algorithms which exploit commonalities between multiple queries submitted to such systems.; Finally, as an HDB or an agent system may have a vast number of pending queries and MQO algorithms can handle relatively smaller sets of queries, the final step in optimizing the performance of such systems is to group a large number of queries into classes of manageable size, so that each class can be optimized by the MQO techniques we developed earlier (or by third party MQO techniques). In this thesis, we formalize this partitioning problem and show that it is NP-hard. We then provide two exact and several heuristic based algorithms for query partitioning.