In some modern applications, the increasing usage of databases and integrated information retrieval systems has encouraged the development of file structures suited for partial match retrieval. A partial match query is a query with some number of attributes specified and the rest of them unspecified. In partial match retrieval, the central problems are the partial match file design and the multidisk allocation. The partial match file design problem involves finding a way to arrange a given set of multiattribute records into buckets such that the average number of buckets to be examined, over all possible partial match queries, is minimized. The multidisk problem is a file allocation problem among multiple independently accessible disks so that, for all possible partial match queries, maximal disk access concurrency can be obtained. Since both problems are known to be NP-hard, many heuristic methods are proposed. Some methods are intended to utilize replication of files to obtain attractive improvements in performance.
File designs for partial match queries are considered first. The objective of the first problem is to allocate query-related records in the same bucket. The file systems developed as a result of these efforts are largely based on cartesian product files, which have been shown to be very effective for partial match queries. We are concerned about the file designs based on cartesian product files with the use of replication to improve average performances. Our contribution is to give a method of fold tries, which uses trie structure to map partial match queries onto fold addresses. Two fold design is considered first and then a generalized design is developed. We propose a fold generation algorithm and show that optimal files can be constructed by the algorithm. The performance formula for the algorithm is derived. The results of experiments show that it is possible to improve average performances with modest redundancy.
Recently, many file design schemes use the simultaneously accessed multiple storage units because the efficiency of data retrieval in a single storage unit model is limited. The response time to a given query in this case is no longer proportional to the total number of buckets needed to be examined, but becomes proportional to the maximum number of buckets needed to be examined on a particular disk. Thus, the objective of the second problem is to place query-related buckets on different disks. We propose two multidisk partial match file designs including the problem definitions and historical review.
One is a multidisk partial match file design scheme which reflects a known access pattern to improve disk access concurrency, and thus response time. The proposed method uses bit-oriented distribution parameters, while the previously proposed methods use attribute-oriented distribution parameters with those of other allocation schemes with those of allocation schemes. The comparison shows that our allocation schemes are better than other schemes under the various values of analysis parameters. Also, we consider the vertical partitioning problem in the multidisk system.
The other is an optimal redundant multidisk partial match file design to solve the above problem. Efficient data retrieval is critical for a successful database system. The statistical information are not always known. Even if the statistical information are known, real access pattern may be not the same as the access pattern previously known, which results in serious performance degradation. The optimal strategy is achieved by using partial file replication. Our contribution is to use a graph model to achieve an optimal allocation. Then, the problem of designing optimal redundant files can be reduced to finding disjoint independent sets of the graph. We propose a heuristic algorithm to find disjoint independent sets. We analyze the performance of the algorithm.
The main contribution of this thesis is as follows. We further present bounds on the cardinality of a maximum independent set and propose a partial match file design methodology where all possible techniques are considered. The design steps are (1) design the redundant partial match files using the access patterns and domain sizes; (2) distribute buckets of files designed by using the access patterns; (3) decompose the partial match files by using the attribute retrieval values and attribute size.
최근의 데이타베이스 응용프로그램들은 정보검색에 있어서 Partial Match 질의에 적합한 화일 구조를 필요로 한다. Partial Match 질의란 필요한 정보의 일부분만을 알고 있는 경우에 그러한 정보를 이용하여 관련된 모든 정보를 검색하는 질의를 뜻한다. Partial Match 검색과 관련하여 두가지 중요한 문제가 있다. 첫번째 문제는 Partial Match 화일 설계 문제로, 한개의 디스크를 가진 시스템에서 모든 가능한 질의에 대하여 평균적인 응답 시간을 최소화 하도록 주어진 레코드들을 버킷(Bucket)에 배치하는 것이다. 두번째 문제는 설계된 화일의 버킷들을 멀티디스크 상에 할당하는 문제로, 질의와 관련된 버킷들을 여러개의 디스크 위에 분할하여 할당하므로서 질의의 응답 시간을 최소화하는 것이다. 질의의 응답시간은 검색할 버킷의 수이다. 두 문제는 NP-Hard 이므로 많은 휴리스틱 알고리즘이 연구되었으며, 데이타의 중복을 이용하여 성능향상을 도모하는 방법도 연구되고 있다. 본 논문에서는 위의 두 문제를 풀기 위한 휴리스틱 방법을 제시하고, 이를 통합하여 멀티디스크에 적합한 Partial Match 화일을 설계하는 방법에 대하여 논의하였다.
첫번째로 Partial Match 화일을 설계하는 문제를 논의하였다. 이 문제는 질의와 관련된 레코드들을 가능한한 같은 버킷(bucket)에 배치하여야하는데, Cartesin Product File이 효율적이라고 알려져 있다. 본 논문은 성능향상을 도모하는 방법으로서 레코드의 중복을 이용한 Cartesian Product File을 설계하였고 질의에 대한 응답을 찾기 위하여 Fold Trie라는 그래프 모델이 제안되었다. 또한, Fold Trie를 생성하는 알고리즘을 제시하고, 이 알고리즘을 통하여 최적의 해를 찾을 수 있음을 보였다. 성능에 관한 공식이 유도되었으며, 실험을 통하여 적정한 정도의 중복을 이용하면 상당한 성능향상이 있음을 보였다.
하나의 디스크를 가진 시스템의 성능은 제한적이므로, 최근에는 동시에 억세스할 수 있는 여러개의 디스크를 가진 시스템에 화일의 버킷들을 할당하는 문제가 많이 연구되고 있다. 이 경우의 응답시간은 질의에 관계된 모든 버킷이 아니라, 특정한 디스크에 할당 된 가장 많은 버킷의 수에 비례하게 된다. 따라서 멀티디스크 문제는 질의와 관련된 버킷들을 다른 디스크에 배치하는 문제이고, 본 논문에서는 두가지 방법을 해결책으로 제시하였다.
그 하나는 레코드를 억세스하기 위한 억세스 패턴이 알려진 경우에 그 정보를 이용하여 화일을 할당하는 방법이다. 제안된 방법은 기존의 방법이 애트리뷰트마다 분산변수를 둔 것과는 달리, 각 어드레스의 비트마다 분산변수를 두어 분산변수의 결정을 용이하게 하였다. 제안된 방법의 성능 공식을 유도하였고, 다른 방법과의 비교를 통하여 제안된 방법이 우수함을 보였다.
다른 하나는 모든 질의에 대하여 항상 최적의 응답시간을 보장하는 방법이다. 이는 효율적인 버킷의 할당방법은 억세스패턴같은 통계정보가 필요하지만, 통계정보는 모를 수도 있고 잘못된 값을 알고 있을 수도 있다. 이러한 잘못된 정보를 이용하여 멀티디스크상에 화일을 할당하게되면 심각한 성능의 감소를 가져올 수 있다. 본 논문에서는 화일의 부분적인 중복을 이용하여 모든 질의에 대하여 최적의 응답시간을 하도록 하였다. 제안 된 방법은 그래프 모델(Bucket Connectivity Graph)을 이용하여 화일의 할당 문제를 Independet Set 문제로 변환하고, 여러개의 다른 Independent Set을 찾는 알고리즘을 제시하였다. 제안된 방법의 성능을 해석적인 방법으로 분석하였다.
본 논문의 주된 기여도는 멀티디스크 상에서 Partial Match화일을 설계하는 방법을 제안한 것이다. 이를 위하여 싱글디스크 상에서의 Partial Match화일 설계 문제와 설계된 화일의 버킷들을 멀티디스크 상에 할당하는 문제를 같은 가정하에서 접근하였고, 같은 데이타를 통하여 실험하므로서 성능향상의 과정을 보였다. 본 논문에서 제안한 화일의 설계과정은 다음과 같다. (1) 억세스패턴과 애트리뷰트의 크기를 이용하여 레코드의 중복을 이용한 싱글디스크 상에서의 화일 설계한다. (2) 억세스패턴을 이용하여 화일을 멀티디스크 상에 할당한다. (3) 애트리뷰트에 관한 물리적인 정보를 이용하여 화일을 수직적으로 분해한다. 다른 기여로서는 성능 향상을 도모하기 위하여 사용될 수 있는 중복을 허용하는 방법과 멀티디스크를 사용하는 방법, 화일을 수직적으로 분해하는 방법을 각각 제시하고 성능향상에 대한 실험적 결과를 제시하므로서 각 방법을 선택할 때의 예상되는 성능향상을 예측할 수 있게 한 점이다.
