In general, traditional database management systems are well suited for a variety of business-processing applications in the commercial world. These applications typically use formatted data. However many new applications require to support records(or documents) containing free texts as well as formatted fields. Such new applications include library systems, medical information systems, office information systems, geographical database systems, CAD/CAM systems, and a variety of military applications.
In this thesis, we propose new signature-based multikey access methods based on a term discrimination property in order to support such new applications. Using the property, we differentiate highly discriminatory terms(primary terms) from lowly discriminatory terms (secondary terms) and constuct a new, efficient access structure, e.g. inverted files and hash-table files, for primary terms so that we may achieve good retrieval performance.
Due to the two-path structure of new multikey access methods, we propose a multi-term query processing strategy which gains entire accesses to primary terms and partial accesses to secondary terms. The strategy makes it possible to access the constant number of blocks, regardless of the number of secondary terms. In order to provide better performance on retrieval, we cluster similar record signatures in a small number of blocks. To make the clustering easy and effective, we construct clusters by means of the similarity of primary terms rather than all the terms. This still keeps clustering benefits to a high degree.
To evaluate the space-time performance of new signature-based multikey access methods, we provide an analytic model to estimate them in terms of retrieval time, storage overhead, and insertion time. In addition, to verify the analytic model, we implement new multikey access methods and acquire experimental results which agree with theoretical results. We show from the performance results that new multikey access methods achieve about 20-80% gains on retrieval performance compared with conventional signature file methods when a medium database with 100,000 records is used and the ratio of term discrimination follows 80-20 rule. However new multikey access methods require about 5-10% more storage overhead.
Finally we provide a selection guideline to find the most cost-effective multikey access method according to a trade-off between retrieval time and storage overhead on a given environment. We also show that new signature-based multikey access methods are superior to conventional methods on the cost-effectiveness when the ratio of term discrimination exceeds the 70-30 rule.
일반적으로 기존 데이타베이스 시스템은 정형화된 데이타를 사용하는 여러 상업적인 응용에 널리 사용되어 왔다. 그러나 최근의 여러 응용들은 기존의 정형화된 데이타 뿐만 아니라 비정형화된 데이타인 텍스트를 지원하는 것을 요구하고 있으며, 그러한 응용으로는 도서검색, 의학정보 자동화, 사무 자동화, 지도제작, CAD/CAM, 다수의 군사응용을 들 수 있다.
본 논문에서는 이러한 응용을 지원하기 위해 단어 분별도 개념을 이용한 새로운 요약 다중키 접근기법을 제안한다. 제안하는 방법은 단어를 그들의 중요성에 따라 고분별력 단어 (highly discriminatory terms) 와 저분별력 단어 (lowly discriminatory terms) 로 구분하고, 이들 고분별력 단어에 대해 역화일이나 해쉬화일등과 같은 효율적인 접근구조를 구성하여 전체적인 성능향상을 도모한다. 한편 제안하는 요약 다중키 접근기법들은 2경로의 구조를 지니므로, 효율적인 경로 선택에 의해 다중 단어를 처리하는 새로운 다중 단어 처리기법을 제안한다. 이 기법은 저분별력 단어의 개수에 관계없이 항상 상수개의 블럭 접근만을 필요로 한다. 또한 보다 나은 검색 성능을 위해, 고분별력 단어의 유사성에 따라 요약(signature)을 결집하는 휴리스틱 그래프 병합 기법에 근거한 새로운 요약 결집 알고리즘을 제시한다.
한편 제안하는 다중키 접근기법의 성능을 분석하기 위하여 검색 시간, 부가 저장공간, 삽입 시간의 측면에서 이들을 평가하는 분석적 모델을 사용한다. 아울러 이들의 분석적 모델의 타당성을 증명하기 위해 이들 접근기법을 구현하여 실험적 결과를 얻었다. 이들 결과로부터, 제안하는 요약 다중키 접근기법들이 검색 성능의 측면에서 20-80% 의 이득을 얻었고 반면 5-10% 의 부가 저장 공간을 더 요구함을 보였다. 마지막으로 검색 시간과 부가 저장공간의 측면에서 가장 비용-이득의 효율성이 큰 기법을 선택하는 지침을 제시한다. 이를 통해서, 단어 분별도가 70-30 의 규칙을 초과할 경우, 제안하는 다중키 접근기법이 비용-이득 측면에서 기존의 기법들보다 더 효율적임을 보였다.
