Publications

Detailed Information

관계형 데이터베이스에서의 키워드 질의 처리를 위한 그래프 기반 프레임워크 : A Graph-based Framework for Processing of Keyword Queries in Relational Databases

Cited 0 time in Web of Science Cited 0 time in Scopus
Authors

박재휘

Advisor
이상구
Major
전기·컴퓨터공학부
Issue Date
2012-02
Publisher
서울대학교 대학원
Abstract
In conventional querying mechanisms for relational databases, users must gain a detailed knowledge of both the query language and the schema of the database. These querying mechanisms have limited the opportunities of the ordinary users who wish to examine databases in depth. To enable the users to more easily query relational databases, flexible retrieval models, such as, keyword search, are required. In a relational database, a keyword query is a set of keywords that allows users to find interconnected tuple sets containing given keywords. Keyword search capabilities in relational databases would enable various applications, e.g., deep web. However, supporting keyword search in relational databases is challenging because keyword queries are inherently ambiguous and may involve expensive database operations to interconnect the tuple sets. In this dissertation, we propose a comprehensive graph-based framework to support keyword search in relational databases. Given a keyword query, our framework deals with structured query generation, query plan optimization and the ranking of query results. The main contributions of the dissertations are summarized as follows: 1) We propose a structured query generation algorithm, Query Generation, to effectively reduce the number of candidate queries. 2) We introduce a general graph model, Weighted Operator Graph to represent the costs of keyword query evaluation plans in a uniform manner. We also propose an efficient greedy heuristic, Maximum Propagation, to avoid exponential time increase when a query plan is determined. 3) We propose a probabilistic ranking model, Correlation-based Ranking, to assign relevance scores between queries and the database using correlation analysis on the set of attribute values. To our knowledge, this work is the first effort in processing and optimizing keyword queries, in relational databases, using a graph-based framework. The experimental evaluations compare our approach with state-of-the-art approaches and show superior or competitive performance in terms of the effectiveness and efficiency.
관계형 데이터베이스에 대한 전통적인 질의 메커니즘은 사용자에게 데이터베이스의 자세한 스키마 뿐만이 아니라 질의 언어를 배우도록 요구한다. 이 질의 메커니즘은 데이터베이스를 자세히 검색하고자 하는 일반적인 사용자의 기회를 제한하여 왔다. 크고 복잡한 데이터베이스에 대한 정확한 질의문을 작성하는것은 전문가에게도 어려운 일이다. 사용자가 관계형 데이터베이스를 더 쉽게 질의하게 하기 위해서는 키워드 검색과 같은 유연한 검색 모델이 요구뒨다. 관계형 데이터베이스에서 키워드 질의는 키워드를 포함하는 서로 연결된 튜플 집합을 사용자가 찾을 수 있도록 하는 키워드 집합이다. 이러한 능력은 딥웹과 같은 다양한 응용을 가능하게 한다. 그러나, 키워드 질의는 근본적으로 모호하며, 그 튜플 집합들을 연결하기 위해 비용이 큰 데이터베이스 연산들을 수반한다. 이러한 어려움 때문에, 관계형 데이터베이스에서의 키워드 검색을 매우 도전적인 과제이다. 이 학위 논문은 관계형 데이터베이스에서 키워드 검색을 제공하는 통합 프레임워크를 제시한다. 키워드 질의가 주어지면, 이 프레임워크는 정형 질의 생성, 질의 계획 최적화, 검색 결과 랭킹을 처리한다. 이 학위 논문의 주요 기여는 아래와 같다. 1) 정형 질의 생성 알고리즘인 Query Generation 을 제시하여 후보 질의의 개수를 효과적으로 줄인다. 2) 일반적인 그래프 모델인 Weighted Operator Graph 를 제시하여 키워드 질의 수행 계획의 비용을 일관성 있게 표현하였다. 그리고 탐욕 휴리스틱 Maximum Propagation 을 제시하여 기하급수적인 시간 증가를 회피하였다. 3) 확률적 랭킹 모델인 Correlation-based Ranking 을 제시하여 질의와 데이터베이스의 관계성을 속성값 상관관계를 분석하여 추정하였다. 조사한 바로는, 이 학위 논문은 그래프 기반 질의 최적화와 랭킹에 있어서 관계형 데이터베이스에서의 키워드 질의 처리를 제시한 첫번째 시도이다. 실험적 검증은 최신의 방식들과의 비교를 수행하였고, 효용성과 효율성 측면에서 향상된 혹은 경쟁적인 성능을 보였다.
Language
eng
URI
https://hdl.handle.net/10371/156629

http://dcollection.snu.ac.kr:80/jsp/common/DcLoOrgPer.jsp?sItemId=000000000715
Files in This Item:
There are no files associated with this item.
Appears in Collections:

Altmetrics

Item View & Download Count

  • mendeley

Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.

Share