상세정보
학술지
A Graph-Theoretic Approach to Optimize Keyword Queries in Relational Databases
- 저자
- 박재휘, 이상구
- 발행일
- 201412
- 출처
- Knowledge and Information Systems, v.41 no.3, pp.843-870
- ISSN
- 0219-1377
- 출판사
- Springer
- 협약과제
- 13PC1200, 맞춤형 모바일 지식 서비스를 위한 지식스토어 핵심기술 개발, 박윤경
- 초록
- Keyword search can provide users an easy method to query large and complex databases without any knowledge of structured query languages or underlying database schema. Most of the existing studies have focused on generating candidate structured queries relevant to keywords. Due to the large size of generated queries, the execution costs may be prohibitive. However, existing studies lack the idea of a generalized method to optimize the plan of the large set of generated queries. In this paper, we introduce a graph-theoretic optimization approach. We propose a general graph model, Weighted Operator Graph, to address the costs of keyword query evaluation plans. The proposed model is flexible to integrate all of the cost-based plans in a uniform way. We define a Keyword Query Optimization Problem based on a theoretical cost model as a graph-theoretic problem and show it to be a NP-hard problem. We propose a greedy heuristic Maximum Propagation that reduces the size of the intermediate result as early as possible. The proposed algorithm allows us to achieve efficiency in terms of query evaluation costs. The experimental studies on both synthetic and real data set results show that our work outperforms the existing work.
- KSP 제안 키워드
- Data sets, Database schema, Experimental study, Graph model, Graph-theoretic, Greedy Heuristic, Keyword query, NP-Hard problem, Optimization problem, Proposed model, Query Language