RANK-BASED DATA MATERIALIZATION FOR THE EFFICIENT EVALUATION OF A QUERY IN A MEDIATOR

摘要

This paper proposes an efficient query evaluation scheme for a mediator system intended to integrate heterogeneous computing environment in terms of operating systems, database management systems, and other software. Most of mediator systems transform a global query into a set of sub-queries based on their target remote server. Each sub-query is evaluated by the query modification method to evaluate a global query. However, it is possible to reduce the evaluation cost of a global query when the results of frequently requested sub-queries are materialized in a mediator. The integrating schema of a mediator can be incrementally modified and its evaluation frequency can also be continuously varied. In order to select the optimized set of materialized sub-queries with respect to their current evaluation frequencies, the proposed method applies a decay factor for modeling the recent access behavior of each sub-query. In other words, the latest access of a sub-query gets the highest attention in the selection process of materialized sub-queries. As a result, it is possible to adjust the optimized set of materialized sub-queries adaptively according to the recent changes in the access behavior of sub-queries. Since finding the optimum solution of this problem is NP-complete, it takes too long to be used in practice when the number of queries is large. Consequently, given the size of mediator storage, the rank-based selection algorithm proposed in this paper finds the set of materialized sub-queries which minimizes the total evaluation cost of global queries in linear search complexity.