Data warehouses integrate information from multiple operational databases and are often used to support On-Line Analytical Processing (OLAP). OLAP queries involve a lot of aggregations on a large amount of data in data warehouses. A commonly used approach for efficient processing of OLAP queries is to store the results of frequently issued queries in materialized views and to make use of them in evaluating other queries. This approach involves selecting views to materialize and rewriting queries using materialized views. In this dissertation, we propose a new method to rewrite a given OLAP query using various kinds of materialized views that are available in data warehouses. We also propose dynamic management schemes for materialized views based on the past and future usability of the materialized views.
We first define the canonical forms of OLAP queries and materialized views based on the selection and aggregation granularities, which are derived from the lattice of dimension hierarchies. Conditions for usability of materialized views in rewriting a given query are specified by relationships between the components of their canonical forms. We present a rewriting algorithm for OLAP queries that can effectively utilize materialized views having different selection granularities, selection regions, and aggregation granularities together. We propose algorithms to find an optimal and a near-optimal set of materialized views that results in a rewritten query which can be executed efficiently. We show the effectiveness and performance of the algorithms experimentally.
We then propose caching schemes for materialized views in OLAP systems based on the usability of the query results in rewriting and processing other queries. For effective admission and replacement of materialized views, we consider the benefit of query results not only for recently issued queries but also for the expected future queries of the current query. We investigate the interactive and navigational nature of OLAP query workloads and exploit semantic relationships between successive queries in an OLAP session to classify and predict subsequent future queries. We present a method for estimating the usability of query results for a set of representative future queries, using a probability model for them. Experimental evaluation shows that our caching scheme using the past and future usability of query results can reduce the cost of processing OLAP query workloads effectively only with a small size of the MV pool and outperforms the previous caching strategies for OLAP systems.
데이터 웨어하우스는 여러 운영 데이터베이스들로부터 수집된 데이터를 통합하여 저장하며, 주로 의사 결정을 위한 온라인 분석 처리(OLAP)를 지원하기 위해 이용된다. 일반적으로 OLAP 질의는 많은 양의 데이터들에 대한 분류 및 집계 연산으로 이루어 진다. OLAP 질의들을 효율적으로 처리하기 위해서 자주 발생되는 질의의 결과를 실체 뷰로 저장하고 그것들을 이용하여 새로 주어지는 질의의 결과를 계산하는 방법이 제안되었다. 이 방법을 효과적으로 구현하기 위해서는 웨어하우스에 저장할 실체 뷰들을 적절히 선택해야 하고, 그것들을 이용해서 다른 질의를 효율적으로 재작성 해야 한다. 본 논문에서는 주어진 OLAP 질의를 여러 종류의 실체 뷰들을 이용하여 효과적으로 재작성 하는 방법과 실체 뷰들의 과거 유용도 및 미래 유용도에 기반한 효율적인 동적 실체 뷰 관리 기법을 제안한다.
본 논문에서는 먼저 질의의 선택 단위, 집계 단위, 선택 영역 등에 기반하여 OLAP 질의 및 실체 뷰의 정규형을 정의한다. 그리고 특정 실체 뷰가 주어진 질의의 재작성에 이용가능한지를 검사하기 위한 실체 뷰의 이용가능성 조건을 제시한다. 이 조건은 실체 뷰와 질의의 정규형을 구성하는 요소들 사이의 관계에 의해 기술된다. 제안하는 질의 재작성 알고리즘은 서로 다른 선택 단위, 선택 영역, 그리고 집계 단위를 가진 여러 실체 뷰들을 함께 이용하여 효과적으로 재작성을 수행한다. 이 알고리즘은 다음과 같이 크게 세 단계로 구성된다. 첫번째 단계에서는 질의 재작성에 이용될 실체 뷰들을 선택하고 각각에 대한 질의 영역을 결정한다. 두 번째 단계에서는 선택된 실체 뷰들과 질의 영역들을 이용하여 각 실체 뷰에 대한 질의 블록을 생성한다. 마지막으로 세 번째 단계에서는 이 질의 블록들을 통합하여 하나의 최종 재작성 질의를 생성한다. 이 때, 실체 뷰의 선택 단위와 질의의 집계 단위 사이의 관계에 따라 UNION 통합 방법이나 UNION ALL-GROUP BY 통합 방법을 사용한다. 더 나아가 본 논문에서는 질의 재작성 과정에서 최적의 실체 뷰 집합 및 질의 영역들을 선택하는 최적화 문제를 정의하고, 이를 해결하기 위해 두 가지 경험적 알고리즘, 즉, A* 알고리즘과 그리디 알고리즘을 제안하였다. 실험을 통해 평가 분석한 결과, 제안한 방법은 빠른 시간 내에 효율적으로 실행될 수 있는 재작성 질의를 생성하며, 실체 뷰의 수가 증가함에 따라 확장성을 갖음을 보였다.
두 번째 연구 주제로서, 본 논문에서는 데이터 웨어하우스 내의 많은 실체 뷰들을 효과적으로 관리하기 위한 실체 뷰 캐쉬 기법을 제안한다. 먼저 특정 실체 뷰가 다른 질의들을 재작성하고 처리하는데 있어서 얼만큼 유용한가를 의미하는 유용도 척도를 정의하고, 이를 기반으로 한 세 가지 실체 뷰 저장 허가 및 교체 정책을 제안한다. LUF-Past 정책은 최근에 실행된 질의들에 대한 각 실체 뷰의 과거 유용도에 기반하여 교체할 실체 뷰들을 선택한다. LUF-Future 정책은 현재 실행된 질의로부터 앞으로 발생될 질의들을 예측하고 그것들에 대한 각 실체 뷰의 재작성 이득을 계산한다. 이를 위해 OLAP 질의 워크로드의 상호작용적이고 항해적인 특성을 고려하고 OLAP 세션 내의 연속된 질의들 사이의 일반적인 의미 관계를 이용하여 대표 후속 질의들을 결정한다. 그리고 이들에 대한 각 실체 뷰의 미래 유용도를 추정하는 방법을 제시하였다. 마지막으로, 이 두 정책을 통합하여 과거 유용도와 미래 유용도를 함께 활용한 LUF 교체 정책을 정의하였다. 실험 결과, 제안한 동적 실체 뷰 관리 기법은 변화하는 OLAP 질의 워크로드에 대해 유용하게 이용될 수 있는 실체 뷰들을 효과적으로 유지함으로써 작은 크기의 실체 뷰 저장 공간으로도 OLAP 질의의 처리 비용을 크게 줄일 수 있음을 보였다. 특히 LUF 교체 정책은 다양한 OLAP 질의 워크로드에 대해 기존의 데이터 웨어하우스를 위한 질의 결과 캐쉬 방법들보다 더 우수한 성능을 가짐을 실험을 통해 증명하였다.
