As Internet technology evolves, there is growing need of Internet queries involving multiple information sources. Efficient processing of such queries necessitates the integrated summary data that compactly represent the data distribution of the entire database scattered over many information sources. The integrated summary data reduce the communication cost and the response time of queries. The Internet query processor generates the optimal query plan for the Internet query using the integrated summary data.
In this dissertation, we first present an efficient method of managing the integrated summary data based on wavelet transform, and then, addresses Internet query processing using the integrated summary data. The simplest method for creating the integrated summary data would be to summarize the integrated data distribution obtained by merging the data distributions in multiple information sources. However, this method suffers from the high cost of transmitting, storing, and merging a large amount of data distributions. To overcome the drawbacks, we propose a new wavelet transform based method that creates the integrated summary data by merging multiple summary data, each of which is maintained in an information source. Wavelet transform represents an arbitrary function as the sum of simple functions with varying cycles. The wavelet transform has advantages of good approximation and fast computation due to the linear-time complexity. We create a wavelet-based summary data using the wavelet transform for the given data distribution. We show that the wavelet-based summary data can easily be converted to satisfy the conditions for merging. Moreover, the merging process is very simple owing to the linearity and shifting properties of wavelet transform.
We formally derive the bounds of errors introduced in merging the integrated summary data. Due to the properties of wavelet transform, we can formally prove the error bounds of the integrated wavelet-based summary data. In particular, we prove that the absolute, square-root, and maximum errors are always smaller than or equal to the sum of the errors in the component summary data to be merged. In general, the updating period of each summary data is different depending on the characteristics of its information source. This fact motivates us to propose an incremental update algorithm for the integrated summary data that reflects the changes in individual summary data in an incremental manner. Integrated summary data can be incrementally updated with a very small cost by using the method of merging multiple sets of summary data.
We also propose a method of creating and managing the multi-dimensional integrated summary data by using the techniques of merging the multi-dimensional summary data. Estimating a joint data distribution using the one-dimensional summary data for each attribute generates a large error since there exist dependencies among multiple attributes. To solve the problem, we extend the method of merging one-dimensional summary data to that of merging multi-dimensional summary data. We then explain the method of maintaining the multi-dimensional integrated summary data thus created. Further, we formally derive the upper bounds of the absolute, square-root, and maximum errors in the multi-dimensional integrated wavelet-based summary data.
As potential applications of the integrated summary data, we identify Internet query optimization and Internet top-N query processing. We then discuss how our method can be applied to these applications in great benefit. For Internet query optimization, we estimate the selectivities of the queries using the integrated summary data, compute the query processing cost from the estimated selectivites, and find the query plan with the minimum cost. The Internet top-N query is defined as the one retrieving only those records that satisfy a given condition in multiple information sources with top-N ranking. We propose an effective method for processing Internet top-N queries using the integrated summary data. The method significantly reduces the processing cost of Internet top-N queries.
To prove the effectiveness of the integrated summary data, we perform extensive experiments. We show that the one-dimensional integrated wavelet-based summary data prove to be 2.3 ~ 7.0 times more accurate when used for selectivity estimation compared with the histogram-based integrated summary data and that the multi-dimensional(two-dimensional) data prove to be 2.2 ~ 23.9 times more accurate than the histogram-based one. We also show that in processing Internet top-N queries involving 56 information sources, using the integrated summary data can reduce the processing cost by up to 50 times for one-dimensional data and 48 times for the multi-dimensional(two-dimensional) data compared with the cases of not using it. The performance gain becomes larger when top-N queries involve a larger number of information sources.
In summary, our method enables easy and accurate maintenance of integrated summary data, which can be effectively used for optimizing Internet queries that become ever more important nowadays.
최근, 인터넷 기술의 급격한 발전으로 인하여 다수의 정보원들을 처리 대상으로 하는 인터넷 질의의 필요성이 점차 확대되고 있다. 효과적인 인터넷 질의처리를 위해서는 여러 정보원들에 분산된 전체 데이타분포를 함축적으로 표현하는 통합 요약정보가 필요하다. 통합 요약정보는 인터넷 질의 처리에 필요한 통신 비용과 응답 시간을 감소 시킨다. 인터넷 질의 처리기는 이러한 통합 요약정보를 사용하여 최적의 인터넷 질의 계획을 생성한다.
본 논문에서는 웨이블릿 변환(wavelet transformation)을 기반으로 한 통합 요약정보의 효과적인 관리 방법을 제안하고, 이를 이용한 인터넷 질의 처리에 관하여 논의한다. 통합 요약정보를 구성하기 위한 가장 단순한 방법은 각 정보원에 분산된 데이타분포들을 합병한 후, 이를 압축하여 통합 요약정보를 구성하는 것이다. 그러나 이 방법은 큰 용량의 데이타분포를 전송, 저장, 통합하는 비용이 매우 크므로 실용적이지 않다. 본 논문에서는 이러한 문제점을 극복하기 위하여 웨이블릿 변환을 기반으로 요약정보들을 합병함으로써 통합 요약정보를 구성하는 새로운 방법을 제안한다. 웨이블릿 변환은 간단한 함수의 주기를 변화시킨 함수들의 합으로 임의의 함수를 표현하는 방법으로, 선형 시간 복잡도(linear-time complexity)를 가져 빠른 변환이 가능하며, 뛰어난 압축 효과가 있다. 데이타분포를 웨이블릿 변환하여 생성하는 웨이블릿 요약정보는 합병 조건을 만족하도록 쉽게 변환된다. 또한, 합병 과정이 웨이블릿의 특성인 선형성(linearity)과 이동성(shift)으로 인하여 매우 단순하다는 장점을 갖는다.
본 논문에서는 웨이블릿 요약정보의 합병으로 구성된 통합 웨이블릿 요약정보의 오차 상한선을 정량적으로 유도한다. 통합 웨이블릿 요약정보는 웨이블릿 변환의 특성으로 인해 오차 한계를 정량적으로 증명할 수 있다. 이에 따라, 본 논문에서는 통합 웨이블릿 요약정보의 절대오차, 제곱근오차, 최대오차가 합병에 참여한 각 요약정보들의 오차들의 합을 항상 넘지 않음을 증명한다. 또한, 인터넷 환경에서 각 요약정보의 갱신 주기는 일반적으로 서로 다르므로 이를 효과적으로 통합 요약정보에 반영하기 위하여 본 논문에서는 점진적 갱신 방법을 제안한다. 통합 요약정보의 점진적 갱신은 요약정보의 합병을 이용하여 적은 비용으로도 수행될 수 있다.
다음으로, 본 논문에서는 다차원 요약정보의 합병 방법을 이용한 다차원 통합 요약정보의 생성 및 관리 방법을 제안한다. 일반적으로 데이타베이스의 각 속성들은 서로 연관성이 있으므로 각 속성에 대한 요약정보로 여러 속성에 대한 데이타분포를 추정할 경우 많은 오차가 발생한다. 이러한 문제를 해결하기 위해 본 논문에서 일차원 요약정보의 합병 방법을 확장하여 다차원 웨이블릿 요약정보의 합병 방법을 제안한다. 그리고, 다차원 통합 웨이블릿 요약정보의 관리 방법에 대해 설명한다. 또한, 다차원 통합 웨이블릿 요약정보의 절대오차, 제곱근오차, 최대오차의 한계를 정량적으로 유도한다.
본 논문에서 통합 요약정보의 응용으로 선택률에 기반한 인터넷 질의 최적화와 인터넷 top-N 질의 처리 방법을 보인다. 통합 요약정보는 다양한 인터넷 질의 처리 과정에서 질의 처리 비용을 줄이는데 사용된다. 인터넷 질의 최적화는 통합 요약정보를 사용하여 선택률을 추정하고, 추정된 선택률로부터 질의 수행 비용을 계산하고, 이중 최소의 처리 비용을 가진 질의 수행 계획을 선택한다. 인터넷 top-N 질의는 여러 정보원에서 주어진 조건을 만족하는 레코드 중에서 상위 N의 레코드를 추출하는 질의이다. 본 논문에서는 통합 요약정보를 사용한 인터넷 top-N 질의 처리 방법을 제안한다. 이 질의 처리 방법은 인터넷 top-N 질의 처리 비용을 크게 감소 시킨다.
다양한 실험을 통하여 제안한 방법의 우수성을 검증하였다. 히스토그램 요약정보의 합병과 웨이블릿 요약정보의 합병을 비교한 선택률 추정 실험에서는 통합 히스토그램에 비해 통합 웨이블릿 요약정보가 일차원의 경우 2.3 ~ 7.0배, 다차원(이차원)의 경우 2.2 ~ 23.9배 더 정확하게 선택률을 추정한다는 결과를 보였다. 또한, 56개 정보원이 참여하는 인터넷 top-N 질의를 처리할 때, 통합 요약정보를 사용하는 경우 사용하지 않는 경우에 비하여 일차원에서는 약 50배, 다차원(이차원)에서는 약 48배의 성능 개선 효과가 있는 것을 보였다. 그리고, 이 효과는 인터넷 top-N 질의에 참여하는 정보원의 수가 증가할수록 더 크게 나타난다.
이러한 결과로 볼때 본 논문은 최근에 매우 중요해지고 있는 인터넷 질의 최적화 방법에 효과적으로 사용될 수 있는 통합 요약정보의 간단하고 정확한 관리 방법을 제시하였다는 데에 큰 의미를 가진다.
