Mermaid is a testbed system which provides integrated access to multiple databases. Two query optimization algorithms have been developed for Mermaid. The semijoin algorithm tends to reduce the data transmission cost, while the replicate algorithm reduces the processing cost. An algorithm that integrates the features of these two algorithms to optimize the processing cost as well as the transmission cost is presented. A dynamic network environment is considered where processing speeds at each site and transmission speeds at each link can be variable. Moreover, distributed processing of aggregates is considered based on the functional dependency among the fragment attribute, the aggregate attribute, and the group-by attribute. Semantic information is utilized to obtain efficient query processing.>

A partition-and-replicate strategy for processing distributed queries referencing no fragmented relation is sketched. An algorithm is given to determine which relation and which copy of the relation is to be partitioned into fragments, how the relation is to be partitioned, and where the fragments are to be sent for processing. Simulation results show that the partition strategy is useful for processing queries in fast local network environments. The results also show that the number of partitions does not need to be large. The use of semijoins in the partition strategy is discussed. A necessary and sufficient condition for a semijoin to yield an improvement is provided.>

Mermaid is a system that allows the user of multiple databases stored under various relational DBMSs running on different machines to manipulate the data using a common language, either ARIEL or SQL. It makes the complexity of this distributed, heterogeneous data processing transparent to the user. In this paper, we describe the architecture, system control, user interface, language and schema translation, query optimization, and network operation of the Mermaid system. Future research issues are also addressed.

We propose a scheme to make use of semantic information to process distributed queries locally without data transfer with respect to the join clauses of the query. Since not all queries can be processed without data transfer, we give an algorithm to recognize the "locally processable queries." For nonlocally processable queries, a simple "fragment and replicate" algorithm is used. The algorithm chooses a relation to remain fragmented at the sites where they are situated while replicating the other relations at those sites. Our algorithm determines the chosen relation and the chosen copy of every fragment of the chosen relation such that the minimum response time is obtained. The algorithm runs in linear time. If the fragments of the relation are allowed to be processed in other sites, then the problem is NP hard. Two heuristics are given for that situation. They are compared to the optimal situation. Experimental results show that the strategies produced by the heuristics have small errors relative to the optimal strategy.

AIDA is a distributed data management (DDM) front-end system which runs on top of existing databases stored in different data management systems (DBMSs). It appears to the user to be a distributed DBMS, although many of the DBMS functions are actually provided by the underlying DBMS. It currently runs above three relational DBMSs, the IDM database machine connected to a VAX, Ingres on two Suns, and Mistress on a third Sun. One of the key components of the AIDA system is Mermaid which provides query optimization, networking, and system control. Mermaid required research into query optimization where the costs of operations on the different processors and DBMSs is variable, the network cost is variable, and capabilities of the different DBMSs is variable. We extended existing distributed query optimization algorithms to support replicated and fragmented relations. In this paper, we discuss our experiences with the development and testing of the Mermaid system and with the integration of Mermaid with the AIDA translator. We discuss the types of commands, the system controller, and our experiences with distributed debugging. Then we give the results of our initial performance tests.

We propose new adaptive techniques for distributed query optimization. These techniques are divided into two groups: the ones that improve efficiency of query execution (directly) and the ones that improve cost estimations for query execution strategies. Some of the proposed techniques utilize semantic information and knowledge acquisition to adapt to the environment. The latter, in contrast to the former, is not a well-established idea. This is a disturbing fact since knowledge acquisition can give significant improvements in performance of a query optimization algorithm. Performing analysis manually is extrernely time consuming and tedious. Therefore, some learning capacity should be added to the system. Some knowledge acquisition techniques that result in adaptive (dynamic) adjustment to run-time changes are proposed.

This paper describes the query optimizer of the Mermaid system which provides a user with a unified view of multiple preexisting databases which may be stored under different DBMS's. The algorithm is designed for databases which may contain replicated or fragmented relations and for users who are primarily making interactive, ad hoc queries. Although the implementation of the algorithm is a front-end system, not an integrated distributed DBMS, it should be applicable to a distributed DBMS also.

The Mermaid testbed system has been developed as part of an ongoing research program at SDC to explore issues in distributed data management. The Mermaid testbed provides a uniform front end that makes the complexity of manipulating data in distributed heterogeneous databases under various data management systems (DBMSs) transparent to the user. It is being used to test query optimization algorithms as well as user interface methodology.