Design of a cooperative query processor using the knowledge abstraction hierarchy and the high dimensional index structure

Abstract

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...