데이타 웨어하우스에서 데이타 큐브를 위한 효율적인 점진적 관리 기법 = An Efficient Incremental Maintenance Method for Data Cubes in Data Warehouses

국문 초록 (Abstract)

데이타 큐브는 차원 애트리뷰트의 모든 가능한 조합에 대해 데이타를 집단화하는 연산자이다. 차원 애트리뷰트의 수가 n일 때, 데이타 큐브는 2ⁿ개의 group-by를 계산한다. 데이타 큐브에 포함된 각각의 group-by를 큐보이드(cuboid)라 부른다. 데이타 큐브는 흔히 미리 계산되어 형태 뷰(materialized view)의 형태로 데이타 웨어하우스에 저장된다. 이러한 데이타 큐브는 소스 릴레이션이 변경되면 이를 반영하기 위해 갱신되어야 한다. 데이타 큐브의 점진적 관리는 데이타 큐브의 변경될 내용만을 계산하여 이를 데이타 큐브에 반영하는 방법을 의미한다. 2n개의 큐보이드로 이루어진 큐브의 변경될 내용을 계산하기 위하여, 기존의 방법들은 데이타 큐브와 동일한 개수의 큐보이드를 가지는 변경 큐브를 계산한다. 따라서, 차원 애트리뷰트의 수가 증가할수록 변경 큐브를 계산하는 비용이 매우 커지게 된다. 변경 큐브에 포함된 각 큐보이드들을 변경 큐보이드(delta cuboid)라 부른다. 본 논문에서는 2ⁿ개의 변경 큐보이드 대신 <SUB>n</SUB>C<SUB>[n/2]</SUB>개의 변경 큐보이드만을 사용하여 데이타 큐브를 갱신하는 방법을 제안한다. 이에 따라 제안하는 방법은 변경 큐브를 계산하는 비용을 크게 줄일 수 있다. 성능 평가 결과는 제안하는 방법이 기존의 방법에 비해 더 좋은 성능을 가지고 있음을 보여준다.

다국어 초록 (Multilingual Abstract)

The data cube is an aggregation operator that computes group-bys for all possible combination of dimension attributes. When the number of the dimension attributes is n, a data cube computes 2ⁿ group-bys. Each group-by in a data cube is called a cuboid. Data cubes are often precomputed and stored as materialized views in data warehouses. These data cubes need to be updated when source relation change. The incremental maintenance of a data cube is to compute and propagate only its changes. To compute the change of a data cube of 2ⁿ cuboids, previous works compute a delta cube that has the same number of cuboids as the original data cube. Thus, as the number of dimension attributes increases, the cost of computing a delta cube increases significantly. Each cuboid in a delta cube is called a delta cuboid. In this paper, we propose an incremental cube maintenance method that can maintain a data cube by using only <SUB>n</SUB>C<SUB>[n/2]</SUB> delta cuboids. As a result, the cost of computing a delta cube is substantially reduced. Through various experiments, we show the performance advantages of our method over previous methods.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 관련 연구
• 3. 접근 방법
• 4. 문제 정의 및 해결 방법
• 5. 성능 평가
• 6. 결론
• 참고문헌
• 저자소개

참고문헌 (Reference)

1 "Transaction Processing Council"

2 "The Steiner Problem in Phylogeny is NP-Complete" 3 : 43-49, 1982.

3 "Range CUBE : Efficient Cube Computation by Exploiting Data Correlation" 2004.

4 "Query Evaluation Techniques for Large Databases" 25 (25): 73-169, 1993.

5 "On the Computation of Multidimensional Aggregates" 1996.

6 "Maintenance of Data Cubes and Summary Tables in a Warehouse" 1997.

7 "Maintenance of Cube Automatic Summary Tables" 2000.

8 "Maintenance expressions for views with aggregation" 110-118, 1996.

9 "Maintaining views incrementally" 157-166, 1993.

10 "Maintaining Data Cubes under Dimension Updates" 1999.

11 "Incremental maintenance of aggregate and outerjoin expressions" 1999.

12 "Including Group-By in Query Optimization." 354-366, 1994.

13 "Implementing Data Cubes Efficiently" 1996.

14 "Fast Computation of Sparse Datacubes" 1997.

15 "Efficient Computation of Multiple Group By Queries" 2005.

16 "Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross- Tab, and Sub-Totals" 1996.

17 "Cubetree: Organization of and Bulk Incremental Updates on the Data Cube" 1997.

18 "Computers and Intractability" 208-209,

19 "Combinatorial Optimization" 11 : 247-254, 1982.

20 "Bottom-Up Computation of Sparse and Iceberg CUBEs" 1999.

21 "Aggregate View Management in Data Warehouses" Handbook of Massive Data Sets 711-741, 2002.