Data warehouse and On-Line Analytical Processing (OLAP) have become essential elements of Decision Support System nowadays. OLAP systems must enable users immediately to access and analyze data stored in data warehouse. For the purpose of such multidimensional data analysis, CUBE operator was suggested.
However, CUBE operator is very expensive, because it contains many group-by operators. Various CUBE computation researches have been proposed lately. One of those researches is a partition-based method that is especially suitable for sparse data in OLAP. Although current partition-based methods consider I/O cost in the view of data sparseness, they are still inefficient because they re-read data for partitioning operation.
In this thesis, we propose a more efficient method, called early-ranged-partition method (ERP method), to substitute partitioning operation in partition-based method. ERP is also one of the partition-based methods, but it adopts the concept of data reusing at each CUBE computation stage. It can provide some efficiency to the next partitioning stage, so that it can consequently reduce the total amount of I/O required for CUBE operator processing. We evaluate the proposed ERP method compared with existing partition-based methods through simulation experiments and show that our ERP method performs better.
데이타웨어하우스와 OLAP은 최근 의사결정 지원 시스템의 중요한 구성요소로 인식되고 있다. OLAP 시스템은 데이타웨어하우스에 저장된 데이터를 직접 접근하여 분석할 수 있도록 여러 기능을 제공해야 한다. 이러한 다차원적인 데이터 분석을 위해 CUBE 연산자가 제안되었다. 그러나 CUBE 연산자는 여러 group-by 연산자를 포함하기 때문에 매우 비용이 많이 드는 연산자이며 최근 이에 대한 효율적인 처리를 위한 연구가 많이 이루어졌다. 이러한 연구 중 하나가 특히 OLAP의 희박한 데이터에 적합한 분할-기반 방법이다. 기존의 분할-기반 방법들이 데이터 희박성 관점에서 I/O의 비용을 고려하였지만 분할 연산시에 매번 데이터를 다시 읽기 때문에 여전히 비효율적이다. 본 논문에서는 분할-기반 방법에서 분할 연산을 대체하기 위해 early-ranged-partitioning(ERP)라 불리며 좀 더 효율적인 방법을 제안한다. ERP 역시 방법 분할-기반 방법의 하나이지만 매 단계의 CUBE 계산에 데이터 재사용 관점을 적용시켜 좀 더 효율적인 처리가 가능해진다. 결과적으로 CUBE 연산자를 처리하기 위해 요구되는 전체 I/O의 양을 줄일 수 있다. 본 논문에서는 제안한 ERP 방법을 좀 더 자세히 살펴보고 실험을 통하여 기존의 분할-기반 방법과 비교하여 ERP 방법의 성능이 더 좋음을 보인다.
