A PHYSICAL DATABASE DESIGN METHOD FOR MULTIDIMENSIONAL FILE ORGANIZATIONS

This paper presents a physical database design methodology for multidi mensional 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, the re has been no effort toward their physical database design. We first show that the performance of query processing is highly affected by th e similarity between the shapes of query regions and page regions in t he domain space, and then propose a method for finding the optimal con figuration of the multidimensional file by controlling the interval ra tio of different axes to achieve the similarity. For performance evalu ation, 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 metho d builds optimal multilevel grid files regardless of the query types a nd record distributions. When the interval ratio of a two-dimensional query region is 1:1024, the performance of the proposed method is enha nced 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 int erval ratios. The result is significant since interval ratios can be f ar from 1:1 for many practical applications, especially when different axes have different domains. (C) Elsevier Science Inc. 1997.