The semantic structure in relational databases is a structure of relations that are semantically related. The semantic structure has been used to interpret queries. In this dissertation, we propose new semantic structures to interpret queries on the universal relation and keyword queries on relational databases according to the user intention.
In the first part of this dissertation, we propose a new semantic structure, maximal object+, which completely removes cycles in a universal relation and use it to interpret the query according to the user intention. In the universal relation model, a semantic structure called universal relation is defined as a virtual relation that joins all the relations in a relational database. The universal relation model allows us to find the results on the universal relation if the user specifies only selection and projection conditions. It automatically finds actual relations in which the selection and projection conditions are performed and possible join paths among the relations using the database schema. When there are cycles in the database schema graph, the universal relation model may lose some results since it adds an unintentional condition to the interpretation of a query. Here, the unintentional condition is an equality condition that intersects multiple query interpretations by different join paths, and thus, it returns only part of the results that the user intends. The maximal object+ is a largest acyclic connected component in the database schema graph where the entire set of relations in the component has the lossless join property. Here, the important point is that the maximal object+ allows only the lossless join property indicated by functional dependencies excluding the lossless join property indicated by only multivalued dependencies. To show the advantage of the maximal object+, we compare the effectiveness of the query processing method based on maximal object+ with that of the existing query processing method based on the maximal object by performing experiments on the synthetic and real datasets. As a result, we show that our method significantly outperforms the one based on the maximal object in terms of mean recall when a cycle exists in a maximal object while maintaining comparable efficiency. Specifically, our method improves the mean recall by up to 8.15 times for the dataset whose schema involves cycles.
In the second part of this dissertation, we propose a new semantic structure, the strongly related tree (SRT) and use it to improve ranking quality of the top-k keyword query results in relational database. A top-k keyword query in relational databases returns k trees of tuples-where the tuples containing the query keywords are connected via primary key-foreign key relationships-in the order of relevance to the query. Existing works are classified into two categories: 1) the schema-based approach and 2) the schema-free approach. We focus on the former utilizing database schema information for more effective ranking of the query results. Ranking measures used in existing works can be classified into two categories: 1) the size of the tree (i.e., the syntactic score) and 2) ranking measures, such as TF-IDF, borrowed from the information retrieval field. However, these measures do not take into account semantic relevancy among relations containing the tuples in the query results. In this paper, we propose a new ranking method that ranks the query results by utilizing semantic relevancy among relations containing the tuples at the schema level. First, we propose the SRT. An SRT is a tree that maximally connects relations based on the lossless join property. Next, we propose a new ranking method, SRT-Rank, that ranks the query results by a new scoring function augmenting existing ones with the concept of the SRT. SRT-Rank is the first research effort that applies semantic relevancy among relations to ranking the results of keyword queries. To show the effectiveness of SRT-Rank, we perform experiments on synthetic and real datasets by augmenting the representative existing methods with SRT-Rank. Experimental results show that, compared with existing methods, SRT-Rank improves performance in terms of four quality measures-the mean normalized discounted cumulative gain (MNDCG), the number of queries whose top-1 result is relevant to the query, the mean reciprocal rank, and the mean average precision-by up to 46.9%, 160.0%, 61.7%, and 63.8%, respectively. In addition, we show that the query performance of SRT-Rank is comparable to or better than those of existing methods.
We summarize the contribution of this dissertation as follows. First, we have proposed a new semantic structure called maximal object+ that completely removes cycles in a universal relation, which help interpret queries with only selection and projection conditions according to the user intention. Second, we have proposed a new semantic structure called SRT that is a tree maximally connecting relations based on the lossless join property. Then, we proposed the new ranking method called SRT-Rank that utilizes the concept of the SRT, which help improve the ranking quality of the top-k keyword query results. Finally, we have shown the effectiveness of the query processing methods using the proposed semantic structures with various experiments.
관계형 데이터베이스에서 의미구조는 의미적으로 연관되어 있는 릴레이션들의 구조이다. 의미구조는 질의를 해석하는데 사용되어 왔다. 본 학위논문에서는 유니버설 릴레이션에서의 질의와 관계형 데이터베이스에서 키워드 질의를 사용자의 의도에 따라 해석하기 위해 새로운 의미구조를 제안한다.
본 학위논문의 첫 번째 파트에서는 유니버설 릴레이션에서 순환(cycle)을 완전히 제거한 새로운 의미구조인 maximal object+를 제안하고, 이를 사용자 의도에 따라 질의를 해석하는데 사용한다. 유니버설 릴레이션 모델에서 유니버설 릴레이션이라고 불리는 의미구조는 관계형 데이터베이스에서 모든 릴레이션을 조인한 가상의 릴레이션으로 정의된다. 유니버설 릴레이션 모델은 우리가 실렉션 및 프로젝션 조건만을 명시했을 때 유니버설 릴레이션에서 결과를 찾을 수 있게 한다. 유니버설 릴레이션 모델은 실렉션과 프로젝션이 수행되는 실제 릴레이션들과 그 릴레이션들 사이의 가능한 조인 경로를 데이터베이스 스키마를 사용하여 자동으로 찾는다. 데이터베이스 스키마에 순환이 있을 경우, 유니버설 릴레이션 모델은 질의의 해석에 의도하지 않은 조건을 추가하기 때문에 질의의 일부 결과들을 잃어버릴 수 있다. 여기서, 의도하지 않은 조건은 서로 다른 조인 경로에 의해 여러 질의 해석들을 교집합하는 동등(equality) 조건이므로, 유니버설 릴레이션 모델은 사용자가 원하는 결과의 일부만을 반환하게 된다. Maximal object+는 속한 릴레이션들의 집합이 무손실 조인 속성(lossless join property)를 가지면서 데이터베이스 스키마 그래프에서 순환을 가지지 않는 가장 큰 연결된 부분이다. 여기서, 중요한 점은 maximal object+가 다치 종속성(multivalued dependency)에 의한 무손실 조인 속성을 제외하고 함수적 종속성(functional dependency)에 의한 무손실 조인 속성만을 허용한다는 점이다. 본 학위논문에서는 maximal object+의 효과를 보이기 위해 실제 및 합성 데이터 집합에 대한 실험을 수행하여 maximal object+에 기반한 질의 처리 방법의 성능을 maximal object에 기반한 질의 처리 방법의 성능과 비교하였다. 실험 결과, 제안한 방법이 maximal object에 기반한 방법과 비슷한 효율성을 보이면서, recall 측면에서 크게 앞선다는 것을 보였다. 특히, 제안한 방법은 스키마가 순환을 포함하는 데이터 집합에 대해 mean recall을 최대 8.15배까지 증가시켰다.
본 학위논문의 두 번째 파트에서는 새로운 의미구조인 Strongly Related Tree (SRT)를 제안하고 이를 관계형 데이터베이스에서 top-k 키워드 질의 처리의 랭킹 품질을 향상시키는데 사용하였다. 관계형 데이터베이스에서 top-k 키워드 질의는 질의 키워드들을 포함하는 투플들이 주 키-외부 키 관계로 연결된 투플들의 트리 k개를 질의와의 연관성이 있는 순서로 반환한다. 기존 연구들은 1) schema-based 방법과 2) schema-free 방법 다음 두 가지로 분류된다. 본 학위논문에서는 질의 결과들의 좀 더 효과적인 랭킹을 위해서 데이터베이스 스키마 정보를 활용하는 첫 번째 방법을 사용한다. 기존 연구들에서의 랭킹 기준들은 1) 트리의 크기 (즉, syntactic score) 2) 정보 검색 분야에서 유래된 TF-IDF와 같은 랭킹 기준으로 구분된다. 그러나, 이 기준들은 질의 결과에서 투플을 포함하는 릴레이션들 사이의 의미적인 밀접도는 고려하고 있지 않다. 본 학위논문에서는 스키마 수준에서 투플들을 포함하는 릴레이션들 사이의 의미적인 밀접도를 이용하여 질의 결과들을 랭킹하는 새로운 랭킹 방법을 제안한다. 먼저, 무손실 조인 성질에 기반하여 릴레이션들을 최대로 연결한 트리인 SRT를 제안한다. 다음으로, SRT의 개념을 이용하여 기존 scoring function을 수정한 새로운 scoring function으로 질의결과를 랭킹하는 방법인 SRT-Rank를 제안한다. SRT-Rank는 릴레이션들 간의 의미적인 밀접도를 키워드 질의 결과의 랭킹에 적용한 최초의 연구이다. 본 학위논문에서는 SRT-Rank의 효능을 보이기 위해 기존의 대표적인 방법들을 SRT-Rank로 수정한 방법들을 실제 및 합성 데이터 집합에 대해 실험하였다. 실험 결과, 기존 방법들에 비해 SRT-Rank는 네 가지 품질 기준인 mean discounted cumulative gain (MNDCG), top-1 결과가 질의와 연관되어 있는 질의들의 개수, mean reciprocal rank, mean average precision을 최대 46.9%, 160.0%, 61.7%, 63.8%까지 증가시켰다. 또한, SRT-Rank의 질의 처리 성능이 기존 방법들의 성능과 비슷하거나 더 뛰어나다는 것을 보였다.
본 학위논문의 공헌을 요약하면 다음과 같다. 첫째, 유니버설 릴레이션에서 실렉션 및 프로젝션 조건만을 가진 질의를 사용자의 의도대로 해석하기 위해 유니버설 릴레이션에서 순환을 완전히 제거한 maximal object+라는 새로운 의미구조를 제안하였다. 둘째, 무손실 조인 성질에 기반하여 릴레이션들을 최대로 연결한 트리인 SRT라는 새로운 의미 구조를 제안하였다. 그런 다음, top-k 키워드 질의 결과의 랭킹 품질을 향상시키기 위해 SRT 개념을 이용하는 SRT-Rank라는 새로운 랭킹 방법을 제안하였다. 마지막으로, 다양한 실험을 수행하여 제안한 의미 구조들을 사용하는 질의 처리 방법들의 유효성을 입증하였다.
