| In distributed database query processing, the database management system (DBMS) may consider all alternative queries and choose the one with the least cost. However, the number of alternative queries follows the number of relations, attributes, and distributed sites to increase exponentially. Therefore, the problem of finding an optimal query is a well-recognized NP-hard problem [CL84, OV99]. Applying heuristic algorithms to this kind of problem is a commonly used strategy. There are two basic steps in query processing. First, enumerate alternative plans for evaluating a query. Second, estimate the cost of each enumerated plan and choose the plan with the least estimated cost from the result of cost evaluation. In the area of distributed querying processing, the semijoin is a well-recognized operator, which provides efficient query results. There are some heuristic algorithms proposed to solve query-processing problems in distributed database systems. Unfortunately, most of these algorithms do not guarantee the optimality of the result. Therefore, some researchers have been motivated to identify some optimality properties for semijoin programs and have proposed a set of algorithms to improve a non-optimal semijoin program for satisfying those optimality properties. The performance and limitations of this set of algorithms will be evaluated in this thesis. There are some modifications on the algorithms which can improve the performance of improvement algorithms in this thesis. The research work includes the study of modification of the essential operations, such as semijoin, and the interrelationship between the sub-procedures in the algorithms. Different implementation approaches to the algorithms also have been explored. |
