A Region Splitting Strategy for Physical Database Design of Multidimensional File Organizations

摘要

This paper presents a region splitting strategy for physical database design of multidimensional file organizations. Physical database design is the process of determining the optimal configuration of physical files for a given set of queries. Recently, many multidimensional file organizations for supporting mul-tiattribute access have been proposed in the literature. However, there has been no effort for their physical database design. We first show that the performance of query processing is highly affected by the similarity between the shapes of query regions and page regions in the domain space, and then propose a new region splitting strategy that finds the optimal configuration of the multidimensional file by controlling the interval ratio of different axes to achieve the similarity. We also present the results of extensive experiments using the multilevel grid file (MLGF), a multidimensional file organization, and various types ofrnqueries and record distributions. The results indicate that our proposed strategy builds optimal MLGFs regardless of query types and record distributions. When the interval ratio of a two-dimensional query region is 1:1024, the performance of the proposed strategy is enhanced by as much as 7.5 times over that of the conventional cyclic splitting strategy. The performance is further enhanced for the query types having higher interval ratios. The result is significant since interval ratios can be far from 1:1 for many practical applications, especially when different axes have different domains.