Optimal Query Search Algorithms in Query Reformulation System using Aggregate Materialized Views

Materialized views which are stored views of the database offer opportunities for significant performance gain in query evaluation by providing fast access to pre-computed data. Whether a materialized view can be used in answering a query depends on the relationship between the view and the query. In previous works, only one-to-one or containment mapping from views to a query has been used and, as a result, certain potentially useful materialized views were excluded from consideration. In our earlier work, we proposed an extended technique for utilizing materialized views in answering an aggregate query. Based on this result, we propose in this paper the algorithms to search for an optimal query in query reformulation system. We first show an exhaustive search algorithm which generates all possible reformulated queries, and then present an improved version of the exhaustive search algorithm and a greedy algorithm to reduce search space. Also we present a simulation result to prove their efficiency.