ETRI-Knowledge Sharing Plaform

ENGLISH

성과물

논문 검색
구분 SCI
연도 ~ 키워드

상세정보

학술지 A Graph-Theoretic Approach to Optimize Keyword Queries in Relational Databases
Cited 3 time in scopus Download 0 time Share share facebook twitter linkedin kakaostory
저자
박재휘, 이상구
발행일
201412
출처
Knowledge and Information Systems, v.41 no.3, pp.843-870
ISSN
0219-1377
출판사
Springer
DOI
https://dx.doi.org/10.1007/s10115-013-0690-2
협약과제
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.
키워드
Graph models, Keyword search, Query optimization, Query processing
KSP 제안 키워드
Data sets, Database schema, Experimental study, Graph model, Graph-theoretic, Greedy Heuristic, Keyword query, NP-Hard problem, Optimization problem, Proposed model, Query Language