Data cubes provide a powerful data analysis tool called the range-sum query. The range-sum query is very popular and becomes important in finding trends and in discovering relationships between attributes in diverse database applications. It sums over the selected cells of an OLAP data cube where target cells are decided by the specified query ranges. The direct method to access the data cube itself forces too many cells to be accessed, therefore it incurs a severe overhead. The response time is very crucial for OLAP applications which need interactions with users. In the recent dynamic enterprise environment, data elements in the cube are frequently changed. The response time is affected in such an environment by the update cost as well as the search cost of the cube. Existing techniques for range-sum queries on data cubes use an additional cube called the prefix sum cube (PC), to store the cumulative sums of data, causing a high space overhead. This space overhead not only leads to extra costs for storage devices, but also causes additional propagations of updates and longer access time on physical devices.
In this thesis, we first propose an efficient algorithm to reduce the update cost significantly while maintaining reasonable search efficiency, by using an index structure called the d-tree. In addition, we propose a hybrid method to provide either an approximate result or a precise one to reduce the overall cost of queries. It is useful for various applications that need a quick approximate answer rather than an accurate one, such as decision support systems.
Next, we present a new cube representation called `the PC Pool' which drastically reduces the space of the PC in a large data warehouse. The PC Pool decreases the update propagation caused by the dependency between values in cells of the PC. We develop an effective algorithm which finds dense sub-cubes from a large data cube. We perform an extensive experiment with diverse data sets, and examine the space reduction and performance of our proposed method with respect to various dimensions of the data cube and query sizes. Experimental results show that our method reduces 82 - 93% of the space of the PC while having a reasonable query performance.
Finally, we propose a general technique to provide tight error bounds for approximate results to OLAP range-sum queries. It is very important to provide analysts with guaranteed error bounds for approximate results to aggregation queries in many current enterprise applications. We perform an extensive experiment on diverse data sets, and examine the effectiveness of our proposed method with respect to various dimensions of the data cube and query sizes.
데이터 큐브는 영역-합 질의로 불리는 강력한 자료분석 툴을 제공한다. 영역-합 질의는 잘 알려진 대로 추세를 발견하고 다양한 응용에서 애트리뷰트들 간의 관계를 찾는 데 있어서 그 중요성이 높아져 가고 있다. 이는 OLAP 데이터 큐브의 선택된 셀들 상에서 합을 구하는데 여기서의 대상 셀들은 명시된 질의 영역에 의해 결정된다. 데이터 큐브 자체를 엑세스하는 직접적인 방법은 너무 많은 셀들을 엑세스해야 하므로 심각한 오버헤드를 초래하게 된다. 특히, 사용자와 상호작용이 필요한 OLAP 응용에서는 응답시간이 매우 중요하다. 최근에 다이나믹한 기업환경에서는 큐브 내의 데이터 요소가 자주 바뀐다. 이러한 환경에서 응답시간은 큐브의 검색 비용만 아니라 업데이트 비용에 의해서도 영향을 받게 된다. 데이터 큐브상에서 영역-합 질의를 위한 기존의 기법들은 프리픽스 섬 큐브(Prefix sum cube, PC)라 불리는 부가적인 큐브를 사용한다. PC는 데이터의 누적된 합을 저장하므로 심각한 저장공간 오버헤드를 초래하게 된다. 이러한 저장공간 오버헤드는 기억장치의 추가적인 비용과 갱신에 의한 부가적인 증식만 아니라 물리적인 장치로의 더 긴 접근시간을 유발한다.
이 논문에서 첫째로, 우리는 질의 시간을 적절히 유지하면서 업데이트 시간을 상당히 줄이는 효율적인 알고리즘을 제안한다. 이를 위해 우리는 Δ-트리로 불리는 인덱싱 구조를 사용한다. 덧붙여서 OLAP 질의의 전체 비용을 줄이기 위해 정확한 값 또는 근사 값을 구하는 하이브리드 방법을 제안한다. 이것은 의사 결정 지원 시스템과 같이 정확한 값보다는 빠른 근사 값을 요구하는 다양한 응용에 유용하다.
둘째로, 우리는 대용량 데이터 웨어하우스에서 PC의 저장공간을 엄청나게 줄일 수 있는 ‘PC Pool’이라는 새로운 큐브을 제안한다. PC Pool은 PC 내의 셀들간의 값들의 종속성에 의해 유발되는 갱신증식을 감소시킨다. 우리는 대용량 데이터 큐브에서 밀집된 서브큐브를 찾아내는 효율적인 알고리즘을 개발한다. 다양한 데이터 큐브에서의 폭넓은 실험을 통해 저장공간의 감소 효과를 보여주고 다양한 차원과 질의 크기에 대해서 제안된 방법의 성능의 우수성을 검증한다. 실험결과는 PC의 저장공간의 82-93%를 감소하면서도 적절한 질의 성능을 나타냄을 보여준다.
마지막으로, 우리는 OLAP 영역-합 질의에 대한 근사 값에 대한 타이트 에러 바운드(Tight error bound)를 제공하는 일반적인 방법을 제안한다. 현재의 많은 기업 응용에서 분석가에게 질의에 대한 근사 값에 대해 보장된 에러 바운드를 제공하는 것은 매우 중요하다. 광범위한 실험에 대한 결과는 본 논문에서 제시한 방법의 우수성을 보여 주고 있다.
