A physical database design method for multidimensional file organizations

Abstract

This paper presents a physical database design methodology for multidimensional file organizations. Physical database design is the process of determining the optimal configuration of physical files and access structures for a given set of queries. Recently, many multidimensional file organizations have been proposed in the literature. However, there has been no effort toward 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 method for finding the optimal configuration of the multidimensional file by controlling the interval ratio of different axes to achieve the similarity. For performance evaluation, we perform extensive experiments with the multilevel grid file, a multidimensional file organization, using various types of queries and record distributions. The results indicate that our proposed method builds optimal multilevel grid files regardless of the query types and record distributions. When the interval ratio of a two-dimensional query region is 1:1024, the performance of the proposed method is enhanced by as much as 7.5 times over that of the conventional method that has an interval ratio of 1:1 employing the cyclic splitting strategy. The performance is further enhanced for 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. (C) Elsevier Science Inc. 1997.