Join Query Optimization in Nested Relational Databases: A Generalized Query Optimization Algorithm and Its Evaluation

摘要

The nested relational model has been investigated as a promising approach to support new database application domains. Join query optimization is of practical importance in the nested relational database, since join is a costly operation as in the original relational database. In the previous work, we studied query optimization for two join-type operations: nested join and embed, and gave an optimization algorithm. However, in that context, nested joins and embeds in a given query graph were restricted to be applied only at the outermost level of base nested relations. In this paper, we discuss more general cases where nested joins and embeds are applied at arbitrary nested levels of base nested relations. We propose a generalized algorithm to derive a cost effective query execution plan for a given query . We show that the algorithm derives a cost optimal query execution plan under some assumptions. Effectiveness of the algorithm is also evaluated with simulations.