While database applications require more complex and sophisticated tasks, common and important database features tend to be implemented within database system. Processing of aggregate operations is crucial in that they are basic operators for analytical processing and have serious impact on system performance. In this thesis, we focus on processing of aggregate operation in database systems. Most commercial products have been supporting these operators. However, their implementations are straightforward and hence degrade system performance in many cases. This is because they deal with only general cases. By exploiting the application specific knowledge, these operations can be processed more efficiently.
In active databases, aggregate operations are usually used in active rules to describe complicated business semantics. In these cases, efficient condition evaluation is crucial for high performance of active database systems. Most previous works used the incremental evaluation techniques, whose operations are relatively expensive due to the processing based on the exact calculation of the condition expression. We propose a new filtering technique that effectively identifies false condition in an early stage of condition monitoring. Since the results of condition evaluation tend to be false in most practical cases, an efficient filtering method can highly facilitate fast condition evaluation. The proposed filtering technique is developed based on the new perspective of database state and database operations, i.e., a vector space model. We first present vector representations of database states, database operations, and complex condition expressions. Then, we propose two filtering methods based on the properties of vector space, called the sphere containment test and the hyperplane test. Our proposed methods determine the truth value of the rule conditions only with the delta vectors maintained in main memory and they can be used at the same time to increase the filtering effects.
On-Line Analytical Processing(OLAP) is another application domain where efficient processing of aggregate operations is required. Since historical, summarized and consolidated data is used in OLAP, the concept of data cube is often used to provide multidimensional views for such information. We provide efficient processing of range-MAX and range-MIN operations over data cube by introducing the notion of a maximal cover, which is an effective representation of data distribution information with respect to range-max and range-min processing. We show that the maximum and the minimum value of a given query range can be effectively computed by an appropriate maximal cover. Thus, the problem of processing range-MIN/MAX is transformed into the problem of finding an appropriate maximal cover. To speed up the search process, we propose the maximal cover tree that is a search tree based on the containment relation between two maximal covers. Being different from the hierarchical tree proposed earlier, the search process in our maximal cover tree completes when the first matching node is found. This property mainly contributes to the outperformance of our maximal cover tree where the number of accessed nodes is significantly reduced.
데이타베이스 시스템이 발달하고 응용 분야가 더욱 확대되면서 보다 복잡한 작업과 높은 수준의 처리가 요구되고 있다. 이와 같은 요구 조건을 충족하기 위하여 공통적인 중요한 기능들이 데이타베이스 시스템 내부에서 구현되어 제공되고 있다. 집단화 연산은 분석적 작업에는 기본이 되는 중요한 연산이며 시스템 성능에 지대한 영향을 끼치므로, 신중히 검토되고 효율적으로 설계되어야 한다. 본 논문에서는 데이타베이스 시스템에서 집단화 연산의 효율적인 처리 방법에 대해 제안한다. 능동 데이타베이스와 OLAP의 분야에서 각각의 분야 특성을 이용한 최적화 방법을 제안한다.
능동 데이타베이스 시스템에서 능동 규칙의 조건부 평가는 성능에 직접적인 영향을 주는 부분으로서 효율적인 처리가 요구된다. 기존에 발표된 많은 연구들은 점진적 평가 기법을 기반으로 하여 조건부 평가 과정을 간소화시켰으나, 조인이나 집계 함수와 같은 연산의 경우에는 여전히 많은 처리 시간이 필요하다. 조건부에 나타난 표현의 값을 항상 정확하게 계산하여 조건부의 진위를 판별하는 방식을 사용했기 때문이다. 본 논문에서는 조건부 평가 초기에 거짓의 진리값을 가지는 조건들을 미리 찾아내는 여과 기법을 제안한다. 실제 응용 환경에서 대부분의 경우에 능동 규칙의 조건은 거짓의 값을 가지므로, 여과 기법을 통해 조건부를 효율적으로 처리할 수 있다. 본 여과 기법은 데이타베이스 상태와 데이타베이스 연산을 새로운 방법으로 표현함으로써 얻을 수 있다. 데이타베이스 상태, 데이타베이스 연산 그리고 복잡한 조건 표현을 벡터로 표현한 후에, 벡터 공간의 특성을 이용하여 여과한다. 본 알고리즘의 방법과 기존에 제안된 점진적 평가 방법의 조건부 처리 성능을 비교하여, 본 여과 기법이 많은 성능 향상 효과를 가져온다는 것을 보인다.
OLAP은 의사결정 시스템(decision support system : DSS)의 핵심적인 기능을 수행하는 부분이다. 기존의 시스템과는 달리 OLAP에서는 주로 통계적인 정보와 요약 정보들이 사용되기 때문에, 데이타 큐브와 같은 다차원적 데이타 모델이 이용된다. 본 논문에서는 데이타 큐브의 전형적인 연산인 구간-집합(range-aggregate) 연산들 중에 구간-최대/최소(range-MAX/MIN) 연산자에 대한 효율적인 처리 방법을 제안한다. 데이타 큐브의 구간-최대/최소 연산에 대한 정보를 미리 계산하여 함축적으로 표현하는 최대 커버(maximal cover)의 개념을 도입한다. 임의의 모든 주어진 질의 구간에 대하여, 최대 커버들로부터 질의 결과를 효과적으로 계산할 수 있다는 것을 보인다. 따라서, 구간-최대/최소 질의 문제는 적합한 최대 커버를 찾는 문제로 변환된다. 최대 커버 검색 속도를 증대시키기 위하여, 최대 커버들을 계층적으로 구성한 최대 커버 트리를 제안한다. 기존에 제안된 계층 트리(hierarchical tree)와는 달리 최대 커버 트리의 검색은 적합한 최대 커버를 하나 발견하는 순간에 완료하며, 이와 같은 특성은 최대 커버 트리의 효율성에 직접적인 원인이 된다.