The Multilevel Grid File(MLGF) is a multidimensional dynamic hashed file organization that gracefully adapts to dynamic environments. In this dissertation we implement the MLGF and analyze the asymptotic growth of its directory size. The asymptotic directory growth is an important factor for evaluating the storage overhead of a multidimensional file organization. We derive that the asymptotic directory growth of the MLGF is linearly dependent on the number of records inserted. To justify this derivation, we perform extensive experiments with various distributions of data: uniform, normal, and exponential distributions. We further perform experiments for more complicated cases where the distributions are highly-skewed or highly-correlated. The results show that the directory size of the MLGF increases linearly in the number of records independently of data distributions, data skew, or correlation. The results also show that the rates of increase are nearly constant in all cases.
We also propose a new dynamic method for multidimensional selectivity estimation for range queries that works accurately independent of data distribution. Accurate estimation of selectivity is essential for query optimization and physical database design. Our method employs the MLGF for dynamic estimation of multidimensional distribution of data in a file. We show that each level of the MLGF directory naturally maintains a multidimensional data distribution. We then extend it for further refinement and propose the selectivity estimation method based on the information of the data distribution. A major advantage of the proposed method is that the information is maintained dynamically in the MLGF. In contrast, other static methods such as the histogram method employ static data structures, which require periodic restructuring. Extensive experiments have been performed to test the accuracy of the proposed method for selectivity estimation. We use uniform, normal, exponential distributions, ones with data-skew and others having correlations among different organizing attributes. The results show that estimation errors are very small regardless of data distributions even with correlated and highly-skewed ones. Finally, we analyze the cause of errors in estimation and investigate the effects of various parameters on the accuracy of estimation.
계층 그리드 화일은 동적인 환경에서도 잘 적응할 수 있는 다차원 동적 해쉬 화일 구조의 하나이다. 본 논문에서는 계층 그리드 화일을 구현하고, 디렉토리 크기의 증가 특성을 규명한다. 디렉토리 크기의 증가 특성은 저장 공간의 오버헤드 측면에서 다차원 동적 화일 구조의 성능을 평가하는 중요한 요소이다. 먼저 계층 그리드 화일의 디렉토리 크기의 증가가 삽입되는 레코드 수에 대한 선형 함수로 나타남을 이론적으로 유도하고, 이를 실험을 통하여 검증한다. 실험에서는 균일 분포, 정규 분포, 지수 분포를 취하는 데이타의 집합, 특정 영역내 편중 현상을 갖는 데이타의 집합, 그리고 서로 다른 애트리뷰트간의 상관 관계를 갖는 데이타의 집합 등의 다양한 데이타를 사용하였다. 실험 결과에 의하면, 계층 그리드 화일의 디렉토리 증가는 데이타의 분포나 특정 영역내의 데이타 편중, 그리고 서로 다른 애트리뷰트간의 상관 관계에 영향을 받지 않고, 삽입되는 레코드 수에 대한 선형 함수로 증가하는 것으로 나타났다. 또한 선형 함수의 기울기도 각 실험 결과에서 일정한 것을 알 수 있었다. 본 논문에서는 또한 저장된 데이타의 분포에 영향을 받지 않고 범위 질의에 대한 다차원 선택률을 정확하게 추정하는 새로운 동적 다차원 선택률 추정 기법을 제안한다. 선택률의 정확한 추정은 질의 최적화 과정 및 물리적 데이타베이스 설계 작업시의 필수적이다. 제안된 기법은 저장된 다차원 데이타의 분포를 동적으로 추정하기 위한 자료 구조로서 계층 그리드 화일을 이용한다. 먼저, 계층 그리드 화일의 각 단계 디렉토리가 저장된 데이타의 분포를 동적으로 관리할 수 있음을 보이고, 분포 추정의 정확도를 높이기 위하여 이를 확장한다. 그리고 계층 그리드 화일의 디렉토리내에서 관리되는 데이타 분포 정보를 이용하는 선택률 추정 기법을 제안한다. 제안된 기법의 가장 큰 장점은 데이타의 분포 정보가 계층 그리드 화일내에서 동적으로 관리된다는 것이다. 따라서 히스토그램과 같은 기존의 정적인 기법에서 나타나는 데이타 분포 정보의 주기적인 재구성에 드는 오버헤드를 해결할 수 있다. 제안된 기법의 정확성을 보이기 위하여 다양한 실험을 수행하였다. 사용된 데이타는 균일 분포, 정규 분포, 지수 분포를 취하는 데이타의 집합, 특정 영역내 편중 현상을 갖는 데이타의 집합, 그리고 서로 다른 애트리뷰트간의 상관 관계를 갖는 데이타의 집합 등이다. 실험 결과에 의하면, 제안된 기법은 이러한 다양한 데이타 집합의 특성에 크게 영향을 받지않고 정확하게 선택률을 추정하는 것으로 나타났다. 끝으로 제안된 기법에서 발생하는 추정 오차의 원인을 규명하였으며, 추정값의 정확성에 영향을 미치는 인자들의 효과를 제시하였다.
