A graph-theoretic approach to optimize keyword queries in relational databases

Jaehui Park, Sang Goo Lee

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)843-870
Number of pages28
JournalKnowledge and Information Systems
Volume41
Issue number3
DOIs
StatePublished - 7 Nov 2014

Keywords

  • Graph models
  • Keyword search
  • Query optimization
  • Query processing

Fingerprint

Dive into the research topics of 'A graph-theoretic approach to optimize keyword queries in relational databases'. Together they form a unique fingerprint.

Cite this