In the data warehouse environment, the concept of a materialized view is common and important for efficient support of OLAP query processing. Materialized views are defined over several source relations. These materialized views need to be updated when source relations change. Since the propagation of updates to the views may impose a significant overhead, it is essential to update the ware-house views efficiently. Though various view maintenance strategies have been discussed in the past, the incremental maintenance of some kinds of views has not been sufficiently investigated.
In the first part of this dissertation, we propose an efficient incremental view maintenance method for the select-project-join(SPJ) views. The proposed method minimizes the total cost of accessing source relations. We define the delta evaluation expression and a delta evaluation tree which are core concepts of our method. Then, a dynamic programming algorithm that can find the optimal delta evaluation tree is proposed. We also present various experimental results that show the usefulness and efficiency of our proposed method.
In the second part, we propose an efficient incremental maintenance method for the data cubes. 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, the data cube computes $2^n$ group-bys, each of which is called a cuboid. To maintain a data cube incrementally, previous methods compute a delta cube, which represents the change of the data cube. We call a cuboid in a delta cube a delta cuboid. For a data cube with $2^n$ cuboids, a delta cube consists of $2^n$ delta cuboids. Thus, as the number of dimension attributes increases, the cost of computing a delta cube increases significantly. In the second part of this dissertation, we propose an incremental cube maintenance method that can maintain a data cube using only $^nC_[n/2]$ delta cuboids. As a result, the cost of computing delta cuboids is substantially reduced. Through various experiments, we show the performance advantages of our method over previous methods.
실체화 뷰(materialized view)는 데이터 웨어하우스에서 OLAP 질의를 효율적으로 처리하기 위해 사용되는 개념이다. 현재 대부분의 상용 데이터 웨어하우스에서는 실체화 뷰의 개념을 제공하고 있다. 실체화 뷰는 몇 개의 소스 릴레이션(source relation)들을 기반으로 정의된다. 이러한 실체화 뷰들은 소스 릴레이션들이 변경된 경우, 이를 반영하기 위해 갱신되어야 한다. 실체화 뷰에 소스 릴레이션들의 변경을 반영하는 작업은 상당한 비용을 요구하기 때문에, 실체와 뷰를 효율적으로 갱신하는 것은 매우 중요한 일이다. 실체화 뷰의 관리에 대해서는 이미 다양한 연구들이 있어왔다. 하지만 일부 형태의 뷰에 대한 점진적 관리(incremental maintenance) 방법에 대해서는 아직 충분한 연구가 이루어지지 않았다.
본 논문의 첫 번째 부분에서는 셀렉트-프로젝트-조인(Select-Project-Join) 뷰에 대한 효율적인 점진적 관리 방법을 제안한다. 제안하는 방법은 소스 릴레이션들에 대한 총 접근 비용을 최소화한다. 본 논문에서는 먼저 제안하는 방법의 핵심 개념인 변경 계산 식(delta evaluation expression)과 변경 계산 트리(delta evaluation tree)를 설명한다. 그 후, 주어진 뷰에 대한 최적의 변경 계산 트리를 구하기 위한 동적 계획 알고리즘(dynamic programming algorithm)을 제안한다. 마지막으로 다양한 실험 결과를 통해 제안하는 방법의 효용성과 효율성을 보인다.
본 논문의 두 번째 부분에서는 큐브(cube) 뷰에 대한 효율적인 점진적 관리 방법을 제안한다. 데이터 큐브는 주어진 차원 애트리뷰트들의 모든 조합에 대한 group-by를 계산하는 집단화 연산자이다. 차원 애트리뷰트의 수가 n일 때, 데이터 큐브는 $2^n$ 개의 group-by를 계산한다. 데이터 큐브의 각 group-by를 큐보이드(cuboid)라 부른다. 실체화 뷰의 형태로 저장된 데이터 큐브를 큐브 뷰라고 한다. 큐브 뷰를 점진적으로 관리하기 위해서, 기존의 방법은 큐브의 변경을 나타내는 변경 큐브를 계산한다. 변경 큐브의 각 큐보이드들을 변경 큐보이드라 부른다. $2^n 개의 큐보이드로 이루어진 큐브 뷰에 대해, 변경 큐브는 $2^n$ 개의 변경 큐보이드를 가진다. 따라서 차원 애트리뷰트의 수가 증가함에 따라 변경 큐브를 계산하는 비용도 크게 증가하게 된다. 본 논문의 두 번째 부분에서는 $2^n$ 개의 변경 큐보이드들을 모두 사용하는 대신, $_nC_{n/2}$ 개의 변경 큐보이드들만으로 전체 큐브 뷰를 갱신할 수 있는 점진적 관리 방법을 제안한다. 그에 따라 변경 큐보이드들을 계산하는 비용이 크게 줄어들게 된다. 마지막으로 다양한 실험을 통해 제안하는 방법과 기존의 방법을 비교하고, 제안하는 방법이 기존의 방법에 비해 좋은 성능을 가지고 있음을 보인다.
