As databases get more and more complex, exact answers of queries by the database alone get less and less helpful, and hence the ability of the database system to cooperate with the user is emphasized. The purpose of Cooperative query answering, in database systems, is to provide relevant information of a wider scope or even approximate answers as well as exact answers. Typical steps for the cooperative query answering consist of query analysis, query relaxation and provision of information that is relevant to or associated with the query. To facilitate the query relaxation, a knowledge representation framework has been widely adopted, which uses a data abstraction to represent semantic relationships, or which uses distance metric to represent quantitative similarities among data values. However, in terms of knowledge representation framework, previous studies on cooperative query answering have limitations in accommodating the data abstraction and distance metric together.
In this dissertation, we design a query processor that accommodates the data abstraction and distance metric together to efficiently support cooperative query answering. First, we propose a metricized knowledge abstraction hierarchy (MKAH) that integrates multi-level data abstraction hierarchy with distance metric among data values. To develop the distance metric, we introduce basic distance that is assigned between two directly linked nodes in the MKAH, and the distance between two arbitrary nodes is calculated by incorporating the basic distances. The calculated distances are grouped by level differences, and they are precisely discriminated according to the similarity. In terms of cooperative query answering, the MAKH can support more interactive and flexible query relaxation processes with the abstraction level information. Since the MKAH supports the distance metric, it is appropriate to handle the quantitative similarity of categorical data, and query results with the MKAH can be ranked according to the distances from query conditions.
Second, we propose a new high-dimensional index structure, called OR (Content-based Image Retrieval)-tree, for efficient calculation of the referential metric that the metric interprets the distance between two arbitrary records as the sum of differences between their attributes. We consider a record in a relation as a high dimensional vector, and then construct the CIR-tree with these vectors. The CIR-tree uses dynamically contracting and extending vectors, i.e., it uses as little attributes as possible that are necessary to discriminate among the records. This makes the number of internal nodes small, and eventually speeds up the search time of records. Since the CIR-tree makes the vectors clustered by Euclidean distance, it can find the nearest neighbor efficiently. This results in an adequate index structure for the referential metric.
The proposed query processor can handle various data types with the help of the distance metric and the MKAH, and it can yield ranked results sorted by the semantic distance. The ranked results can help the user to fully take advantage of the information contained in the results. Also the referential metric can be efficiently calculated using the CIR-tree. To verify the practicality and effectiveness of the proposed query processor, we implemented a prototype system in the area of career job search. Through various experiments, we showed that the integration of the distance metric with the MKAH is appropriate to build up scalable and extendible cooperative query answering system.
데이터베이스 시스템에서 처리하는 자료가 점점 복잡해 짐에 따라, 질의문과 정확히 일치하는 자료만을 검색하여 반환하는 것은 사용자에게 도움을 주지 못하는 경우가 많다. 따라서 사용자와 협력할 수 있는 데이터베이스 시스템의 중요성이 더욱 높아지고 있다. 데이터베이스 시스템에서 협력적 질의 처리란 질의 내용과 정확히 일치하는 자료 뿐만 아니라 좀 더 넓은 범위의 자료 또는 근사적인 자료를 검색해 주는 것을 말한다. 협력적 질의 처리는 질의 분석, 질의 유연화, 유연화된 질의에 따른 근사적 자료 제공의 세 단계로 이루어져 있다. 두 번째 단계인 질의 유연화를 수행하기 위해 의미적 관계를 표현하는 지식추상화 방법과 자료 사이의 정량적인 유사도를 거리로 표현하는 방법들이 지식표현 방법으로서 사용되어 진다. 그러나 지식표현에 대한 기존 연구는 지식추상화와 거리 표현을 통합하는 효과적인 방법을 제시하지 못하였다.
본 논문은 협력적 질의를 효과적으로 지원하기 위해 지식추상화 및 거리 표현을 통합하는 질의 처리기를 설계한다. 첫째, 우리는 자료 사이의 거리 정보를 표현할 수 있는 다단계 지식추상화 구조인 정량화된 지식추상화 계층 (MKAH: Metricized Knowledge Abstraction Hierarchy)을 제안한다. 지식추상화 계층에 거리 개념을 접목하기 위해, 바로 연결된 두 노드 사이의 거리를 표현하는 기본거리를 도입하며, 임의의 두 노드의 거리는 이 기본거리를 이용하여 계산된다. 계산된 거리는 지식추상화 계층의 수준 차이에 따라 그룹지어지며 유사 정도에 따라 정밀하게 구분되어 진다. 협력적 질의 처리면에서 보면 MAKH는 추상화 수준 정보를 이용하여 보다 대화적이며 융통성 있는 질의 유연화 처리를 제공한다. 또한 MKAH는 거리 표현이 가능하기 때문에 그룹화 될 수 있는 자료의 정량적인 유사성을 표현하는데 적당하며, 질의의 결과는 질의 조건과 일치하는 순서대로 정렬될 수 있다.
둘째, 본 논문은 각 컬럼의 의미적 거리 차이의 합으로 계산되어지는 레코드 사이의 거리를 효율적으로 계산하기 위해 CIR (Content-based Image Retrieval) 트리라는 고차원 자료 인덱스 구조를 제안한다. 테이블에 있는 레코드는 고차원 벡터로 생각할 수 있으며 이 벡터를 이용하여 CIR 트리를 만들 수 있다. CIR 트리는 레코드의 구분을 위해 필요한 만큼의 컬럼을 사용하며, 사용하는 컬럼의 개수는 융통성 있게 늘어나고 줄어든다. 이러한 특징은 트리에서 내부노드의 크기를 작게 하며 결과적으로 검색 시간을 줄여준다. CIR 트리를 이용하면 최근접 이웃을 빠르게 검색할 수 있고 이러한 특징은 두 레코드의 거리 계산을 효율적으로 지원해 준다.
제안하는 질의 처리기는 기본 자료형 및 MKAH에 대해 의미적 거리 계산을 할 수 있으며, CIR 트리를 이용하여 두 레코드 사이의 거리를 빠르게 계산할 수 있고, 의미적 거리에 따라 정렬된 질의 결과를 만들어 준다. 질의 조건과의 의미적 거리에 따라 정렬된 질의 결과는 사용자가 원하는 정보를 보다 쉽게 얻어낼 수 있게 한다. 제안하는 질의 처리기의 실용성과 효과성을 검증하기 위해, 본 논문에서는 실험적인 직업 검색 시스템을 구현했다. 다양한 실험을 통하여 MKAH와 거리 개념의 통합이 확장성 있고 효율적인 협력적 질의 처리기 시스템에 적당함을 보였다.
